[유형]백트래킹 [문제링크]https://www.acmicpc.net/problem/15650 [요약]자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열고른 수열은 오름차순이어야 한다. [문제풀이]앞의 N과 M(1),15649번과 다른 조건은 고른 수열은 오름 차순이어야한다는 것이다.따라서 start를 추가해서, 첫번째 수가 두번째 수보다 크거나 같지 않도록 코드를 변경한다.import sysdef input(): return sys.stdin.readline().rstrip()def dfs(start,lst): # 종료조건 if len(lst) == M: ans...

[유형]백트래킹 [문제링크]https://www.acmicpc.net/problem/15649 [요약]자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 [문제풀이]백트래킹이란?알고리즘 기법 중 하나로 재귀적으로 문제를 해결하되 현재 재귀를 통해 확인 중인 상태가 제한조건에 위배되는지 판단하고, 해당 상태가 위배되는 경우 해당 상태를 제외하고 다음 상태로 넘어간다. 더 이상 탐색할 필요가 없는 상태가 제외한다는 것인데, 이를 가지치기라고 한다. 백트래킹 특성에서 조건에 부합하지 않으면 이전 수행으로 돌아가야 함으로 BFS보다는 DFS이 구현하기 더 편하기 때문에 주로 DFS를 사용한다. DFS..

[유형]구현 [문제링크]https://www.acmicpc.net/problem/18111 [요약]목재를 충분히 모은 lvalue는 집을 짓기로 하였다. 하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다.lvalue는 세로 N, 가로 M 크기의 집터를 골랐다. 집터 맨 왼쪽 위의 좌표는 (0, 0)이다. 우리의 목적은 이 집터 내의 땅의 높이를 일정하게 바꾸는 것이다. 우리는 다음과 같은 두 종류의 작업을 할 수 있다.좌표 (i, j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다.인벤토리에서 블록 하나를 꺼내어 좌표 (i, j)의 가장 위에 있는 블록 위에 놓는다.1번 작업은 2초가 걸리며, 2번 작업은 1초가 걸린다. 밤에는 ..

[유형]dp [문제링크]https://www.acmicpc.net/problem/14501 [요약]오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오. [문제풀이]dp 테이블을 정의해보자.i = 근무 가능한 일수dp[i] = 근무 가능한 일수가 i만큼 남았을 때의 최대 비용dp[n] = 첫째날부터 마지막날까지 상담을 골라서 했을 때 얻을 수 있는 최대 수익 점화식을 정의해보자.근무가능한 일수 i 근무가능한 일수 >= 해당 날짜의 상담소요시간이라면, dp[i] = ..

[유형]완전탐색 [문제링크]https://www.acmicpc.net/problem/1436 [요약]종말의 숫자란 어떤 수에 6이 적어도 3개 이상 연속으로 들어가는 수를 말한다.즉, 666, 1666,2666,3666...은 종말의 숫자이다.N번째 종말의 숫자를 구하는 프로그램을 작성하시오. [문제풀이]666을 기준으로 1씩 더해서 666이 들어간 숫자를 찾는다.import sysdef input(): return sys.stdin.readline().rstrip()n = int(input())cnt = 0result = 666while True: if '666' in str(result): cnt+=1 if cnt == n: break result+=1p..

[유형]자료구조 [문제링크]https://www.acmicpc.net/problem/2696 [요약]각 테스트 케이스에 대해 첫째 줄에 출력하는 중앙값의 개수를 출력하고, 둘째 줄에는 홀수 번째 수를 읽을 때 마다 구한 중앙값을 차례대로 공백으로 구분하여 출력한다. 이때, 한 줄에 10개씩 출력해야 한다. [문제풀이]먼저, 특정 N번째 원소까지의 중앙 값을 AkAk라고 가정한다면, 우리는 다음과 같이 이분화를 할 수 있게 된다.A1 ... An = {Ak 보다 작은 원소들의 집합 } + { Ak 보다 크거나 같은 원소들의 집합 }이 때, n이 홀수 일 때 유일한(unique) 중앙값이 하나가 정의가 되고 이 때 이것을 출력하고자 한다. { Ak 보다 작은 원소들의 집합 } 과 { Ak 보다 크거나 같은 ..