동적 프로그래밍의 5단계
동적 프로그래밍으로 문제를 해결하는 단계를 일반화하면 다음과 같다. (괄호 안은 소요 시간을 계산하기 위한 툴이다.)
- 하위 문제를 정의한다 (하위 문제의 개수도 센다).
- 해의 일부를 추측한다 (선택지의 개수도 센다).
- 재귀로 하위 문제의 해를 연관짓는다 (하위 문제당 걸리는 시간을 계산한다).
- 하위 문제가 비순환이고 위상 순서가 있다는 것을 확인한다. (전체 시간 = (하위 문제의 수) $\cdot$ (하위 문제당 소요 시간))
- 기존 문제를 푼다. (추가 시간이 걸린다.)
이 순서를 적용해서 앞선 강의의 피보나치와 최단 거리 문제를 풀면 다음과 같다.
글 정렬하기
Microsoft Word 같은 워드 프로세서를 사용하다 보면 한 줄에 들어가는 단어의 개수를 조절하는 것이 중요하다는 사실을 깨달을 것이다. 적당한 간격으로 단어를 배치해야 가독성이 좋기 때문이다. 예전에는 그냥 탐욕 알고리즘을 사용해서 한 줄에 단어를 최대한 욱여넣고는 했다. 그러나 한 개의 줄 뿐만 아니라 다음 줄에 등장할 단어까지도 고려한다면 더 보기 좋게 정렬할 수 있다.
이를 위해서 동적 프로그래밍을 이용할 수 있다. 일단 단어 i에서 j 사이의 badness(i, j)를 다음과 같이 정의하자.
\[badness(i, j) = \begin{Bmatrix}(페이지 \, 너비 - 총 \, 길이)^3 \quad (총 \, 길이 > 페이지 \, 너비)\\ \infty \quad (나머지 \, 경우)\end{Bmatrix}\]페이지 너비에 비해 줄의 길이가 짧을 수록 badness가 커질 것이다.
우리의 목표는 단어를 나눠서 badness의 합을 최소화하는 것이다.
-
하위 문제로 분류
단어들의 목록이 주어졌을 때, 다음 줄이 어느 단어에서 시작될지를 판단한다. (suffix word[i : ]) 그럼 n개의 단어가 있으면 하위 문제의 개수는 $\Theta(n)$ 이 된다. -
추측
첫 줄을 어디서 끊을지, 즉 다음 줄을 어디서 시작할지를 추측한다. 첫 번째 줄에 들어간 i개 단어를 제외하고 i번째 단어 이후로 추측하므로 (n - i)개의 선택지가 있고, $O(n)$ 로 표현할 수 있다. -
재귀
DP(i)를 i번째 단어부터의 하위 문제라고 할 때 ‘DP(i) = min(badness(i, j) + DP(j))’ (i $<$ j)의 재귀식으로 표현할 수 있다. 또한, DP(n) = 0 이다. 하위 문제당 시간은 $\Theta(n)$ 이다. -
순서
뒤에서부터 앞으로 계산하게 된다. 왜냐하면 DP(i)를 알기 위해서는 i보다 큰 수인 DP(j)에 대한 정보가 필요하기 때문이다. n부터 0까지 계산하게 된다. 1번과 3번을 고려하면 전체 시간은 $\Theta(n^2)$ 이 된다. -
기존 문제
DP(0)에 대해 계산하면 된다!
부모 포인터 문제
최단 거리 문제에서도 다루었지만, 우리는 ‘최소 비용이 얼마인가’를 계산하지, ‘어떤 방법이 최소 비용을 가지는지’는 관심이 없다. 실제로 어떤 방법이 최적인지를 알고 싶다면 부모 포인터를 사용하면 된다. 방법은 단순한데, 그냥 최솟/최댓값과 최대/최소 인수를 기억하면 된다. 메모이제이션, 상향식 방법과 마찬가지고 자동적으로 진행되는 과정이다.
블랙잭
필자는 블랙잭이 어떤 게임인지 완벽하게 이해하지는 못했다. 쉬운 룰만 생각해보면
- 딜러 카드의 합보다 내 카드의 합이 커야 한다.
- 합은 21보다 작아야 하며, 원하는만큼 카드를 더 뽑아도 되지만 21을 넘으면 패배한다.
카드의 순서라든지 상대의 합을 모두 알고있는, 정보를 모두 아는 블랙잭 카지노에 내부 첩자가 있어야… 의 경우에는 동적 프로그래밍을 이용해 필승 전략을 세울 수 있다. 물론 몇 가지 조건을 걸어야만 또? 한다. 이쯤 되면 그냥 운에 맡기자
- $c_0, c_1 … , c_{n-1}$ 이 모든 카드(덱, deck) 일 때
- 판돈은 1달러
모든 카드에 대해 여러 판의 블랙잭을 할 때 동적 프로그래밍으로 필승 전략을 세워보자.
-
하위 문제로 분류
i가 이미 플레이한 카드의 개수일 때, BJ(i)를 남은 카드($c_i, c_1 … , c_{n-1}$)에 대한 최고의 결과라고 정의한다. 하위 문제의 개수는 n이 된다. -
추측
참가자가 몇 장의 카드를 더 받을지를 예측한다. 정확하게 하면 (n - i - 4) 이겠지만(앞선 게임에서 사용한 i개를 빼고, 이번 게임에서 최초 지급받은 4개를 더 뺀다), 그냥 n보다 작거나 같다고 하자. -
재귀
‘BJ(i) = max(결과 $\in {-1, 0, 1}$ + BJ(i + 사용된 카드))’ 의 재귀 식으로 표현할 수 있다. 여기서 결과는 돈을 잃거나(-1), 비기거나(0), 돈을 딴 경우(+1) 이다. ‘사용된 카드’라는 인수는 조금 복잡한데, 이번 판에서 얼마나 많은 카드를 더 받을지까지도 고려해주어야 한다. 또한 각 선택지에서 딜러의 합과 비교하는 과정도 필요하다. 이를 모두 고려했을 때 하위 문제당 걸리는 시간은 $\Theta(n^2)$ 이다. -
순서
이번에도 순서가 거꾸로 된다. 게임의 세부 규칙에 따라 좀 다르겠지만 총 시간은 $\Theta(n^3)$ 이 된다. -
기존 문제
BJ(0)에 대해 계산하면 된다!
위를 자세한 의사코드으로 구현하면 다음과 같다.
별도의 출처 표시가 있는 이미지를 제외한 모든 이미지는 강의자료에서 발췌하였음을 밝힙니다.
댓글남기기