본문 바로가기

Dynamic Programming

[DP] 백준 28218 격자 게임 어떤 알고리즘으로 문제를 풀어야 할까? 문제의 크기는 300 * 300에, 말의 위치가 다시 원위치로 돌아가는 방법이 없다. 문제를 하위 문제로 나누어 풀어도 문제가 없다는 이야기. 즉, dynamic programming이 가능한 문제라는 뜻이다. 점화식을 어떻게 수립해야 할까? $$ dp[x][y][turn] $$ (x, y)의 위치에서 현재 turn(한국 or 정올)의 차례일 때 이기는 사람의 번호로 점화식을 정의할 수 있다. 그렇다면, 최선을 다한다는 것은 어떻게 표현할까? 현재 첫번째 한국이가 이길 때를 0으로 표시하고, 두번째 정올이가 이길 때를 1로 설정한다. 그리고, 첫번째 한국이의 turn일 때는 정올이가 이긴다고(=1) 초기값을 설정하고 가능한 케이스에서 최소값(=0, 한국이가 이기는 .. 더보기
[DP 응용] BJ_1398, 동전 문제 이 문제를 Greedy하게만 풀수 있을까? 즉 큰수로 나누어 지면 계속 빼면서 숫자를 구하면 해답일까? 직관적으로 알기 어렵다면 반례를 생각해 보면 된다. 예는 31이 되겠다. 31은 Greedy하게 풀면 25, 1, 1, 1, 1, 1, 1 로 구성되어 총 6개지만, 10, 10, 10, 1로 구성하면 4개로 구성할 수 있다. 따라서 Greedy하게만은 안된다. 그렇다면 DP로만 풀수 있을까? 값의 범위가 $10^{15}$ 로 매우 크기 때문에 배열을 이용해서 단순하게 확장하는 방법으로는 해법에 다가가기 어렵다. 그럼 어떻게 해야한다? 규칙성을 발견해야 한다. 규칙성을 바탕으로 문제를 단순하게 만들 수 있어야 한다. 아래의 글이 도움이 될것 같다. 생각보다 간단하게 작성할 수 있는데, 1부터 100까지.. 더보기
[DP] BJ_24416, 알고리즘 수업 의사코드를 보고 코드로 풀어낼 수 있으냐를 체크하는 문제. 사실 피보나치 수열의 경우는 Dynamic Programming을 설명하는데 있어서 고전이라고 부를 수 있을 정도로 많이 인용되는 문제다. 한번이라도 들어 보았다면 위의 의사코드를 작성하는 부분은 크게 어렵지 않다고 생각한다. 의사코드를 구현한다. 다만, 한가지 주의해야 할 부분은 함수 호출 부분을 코드의 어디에 위치 시키느냐 인데, 동적 프로그래밍의 경우는 for 문 안에 넣어주면 되고, recursive하게 구하는 경우는 n==1 or n==2의 경우에 리턴되는 경우를 세어주면 된다. def recur(n): global cnt1 if (n ==1) or (n==2): cnt1 += 1 return 1 else: return recur(n-1.. 더보기
[DFS & DP] BJ_1937, 욕심쟁이 판다 [문제의 접근] 500 X 500의 배열이 주어지고, 동서남북으로 이동이 가능하다. 당신이 제일 먼저 생각하게 되는 풀이법은? 바로 BFS일 것이다. 그런데 이 문제는 잘 읽어보게 되면, 시작하는 위치와 더불어 방문의 순서가 매우 중요하다는 것을 깨달을 수 있다. 간단한 예시로 아래의 배열을 보자. 가장 작은 대나무의 위치인 5에서 시작한다고 가정했을 때 DFS로 탐색하는 경우는 한번에 한 위치만 방문하기 때문에 위와 같이 최대거리 4를 찾아낼 수 있지만, BFS로 탐색할 경우 최대 거리를 3밖에 찾을 수 없다. 거리 4를 도출하기 위해서는 한번 방문한 위치를 다시 방문해야 하고, 이는 가장 기본적인 BFS탐색 원리를 위배하는 일이다. 즉, 이문제는 DFS로 풀어야 하는 문제다. 보통 DFS로 풀기 위한.. 더보기
[DP] BJ_2775, 부녀회장이 될테야 [문제의 접근] 이 문제에서의 핵심은 바로 다음 글귀이다. "a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다." 이 것을 읽고 어떤 생각을 해야할까? 특이한 조건이네 이렇게? 특이한 조건인건 맞다. ㅎㅎ. 많은 알고리즘 문제에서는 스토리를 만들어내기 위해 사실 별로 필요없는 문구들도 많이 넣기는 하는데, 위의 문구를 보면 아래와 같은 수식을 떠올려야 한다. 우리는 알고리즘 문제를 풀고 있고 알고리즘은 수식으로 이루어지니 말이다. arr[a][b] = arr[a-1][1] + arr[a-1][2] + ... arr[a-1][b] 그럼 이 문제를 위의 수식 그대로 풀어내면 될까? test case의 T의 숫자가 주어지지 않아서 명확하진 않지만.. 더보기

티스토리툴바