Dynamic Programming(이하 DP)은 어떤 고정된 조건이 주어졌을 때, 그 조건에 부합됨과 동시에 결과값이 최대 또는 최소가 되게하는 최적화 문제(Optimization problem)에 대한 해답을 주는 알고리즘이다. 그러나 모든 최적화 문제에 DP를 적용할 수 있는 것은 아니다. 다음과 조건을 만족할 때에만 사용 가능하다.
1. Optimal Substructure를 가질 때 : 최종적인 최적값이 그 하부에서의 최저값을 포함하고 있는 경우.
2. Overlapping Subproblems가 있을 때 : 자기 반복적인 (recursive) 알고리즘의 경우, 이미 한 번 풀어놓은 문제를 다시 풀어야 하는 경우가 생긴다. 이 때, 계산을 다시 하기 보다는 적당한 기억 장소에 결과값들을 저장해 놓고, 단순히 참조해서 사용한다.
( 밑에 보면 z[] 배열을 볼 수 있는데, 그것이 바로 요것!)
→ "Solve problem for input size 1...i-1, and use it for solving problem with input size i; then iterate."

⊙ 계단을 오르는 문제로 Dynamic Programming을 이해해보자.
총 n개의 계단이 있을 때,
T(n): n개의 계단을 오르는 총 방법의 수.
T(n-1): n-1 계단까지 오르는 방법의 수 (1칸 남은 상태)
T(n-2): n-2 계단까지 오르는 방법의 수 (2칸 남은 상태)

그리고 계단은 보통 한 번에 한칸, 두칸씩 오르기도 한다. (지식인은 급하면 세 칸씩도 오르더라만은... 나에겐 불가능이므로 제외!)
그러면, 내가 지금 n개의 계단을 올랐다면, 그것은 n-1번째 계단에서 한 칸 오른 것이거나, n-2번째 계단에서 두 칸 올라서 도달한 것이다. 그래서,
T(n) = T(n-1) + T(n-2) : recurrence equation (점화식 -ㅇ-)
가 성립한다. 그리고 다음과 같이 표현된다.
T(n) = ( ((√5)+1 )/2 )ⁿ

이것이 바로, DP의 fundamental intuition 이다. 대충 어떤 것인지 느낌이 오시는지? ^^

⊙ Prefix Dictionary
: 이것은, Dictionary 속에서 특정 phrase(여기에서는 encoding의 대상이 되는 문자들의 단위라고 생각하면 된다.)의 앞머리가, 같은 dictionary에 있는 다른 phrase이기도 하다는 것이다. 이는 tree 구조로 표현이 가능하며, 그림으로 나타내면 다음과 같다.

Prefix Dictionary


이 prefix dictionary의 전제는, ∑ = {A, B} 이며 최대 두 문자까지 encoding이 가능하다는 것이다. 또한 이것은 prefix code 이다.

이제, 본격적인 encoding 작업을 해보자.
입력 문자열이 AABABBAA일 때, 어떻게 하면 가장 짧은 encoding이 가능할까? (A는 0, B는 1로 나타내면 8개로 가능하다~ 할 수 있겠지만.... -.- 이건 간단한 예이고, general한 과정으로 풀어보자..흐흐)
이것은, 앞의 계단 문제와 매우 흡사하다. phrase를 encoding할 때, '이번에 encoding할 문자를 한 문자로 볼 것이냐, 이전것과 함께 두 문자로 불 것이냐?'는 것은 한 칸씩 오를 것이냐, 두 칸씩 오를 것이냐와 같다. 그래서 총 문자열 수는 총 계단수와 같다.

다음의 DP 알고리즘을 살펴보자.
z[1:n] : z[i]에는 i번째 까지 parsing했을 때 가능한 최소의 길이를 담아둔다.

z[0] ← 0
for i ← 0 to n
z[i] = ∞
for j ← i-1 down to 1
z[i] ← MIN(z[i], z[j] + length of codeword of input[j+1:i])

이것은, 길이 k인 phrase를 사용하게 되는 DP 알고리즘으로, O(kn) =O(n)이다.

지금 우리가 예로 보고 있는 것은, k=2이다. encoding해보자.
Input : AABABBAA
1. 제일 먼저 A가 등장했으므로, 10으로 encoding하고, z[0] = 2.
2. 그 다음 A가 나오면, 그냥 A로 parsing하면 10으로, z[1]= z[0]+2=4이고, 앞의 A와 함께 AA로 parsing하면 11로, z[1]=2가 되므로, z[1]=2가 된다.
3. 다음 문자는 B로, 그냥 B로 parsing하면 0000으로, z[2] = 2+4=6이 되고, 앞의 문자와 함께 AB로 parsing하면 z[2] = z[0] + 2 = 4가 되므로, z[2]=4이다.
4. 이런 식으로 반복하면, z[] = {2,2,4,5,6,9,9,11}로, 최소값이 들어가서, 전체 encoding의 길이는 11이 된다.

만약 k=3이라면, z[5]를 계산하기 위해서 z[4], z[3], z[2]까지 거슬러 올라가 보게 될 것이다.

여기에서 우리는, DP에서 z[n]이 매우 중요한 역할을 하고 있다는 것을 알 수 있다. 이것은 DP의 큰 특징 중에 하나이다.

⊙ Knapsack Problem (0-1 Knapsack Problem)
아주 간단한 예로, Knapsack Problem에 대해 이해해보자.
▪ knapsack의 크기가 50일 때, 어떤 물건들은 넣어야 가장 이익일까?
물건 1 : 부피 10, 가격 60만원 // 단위 부피 : 6만원
물건 2 : 부피 20, 가격 100만원 // 단위 부피 : 5만원
물건 3 : 부피 30, 가격 120만원 // 단위 부피 : 4만원
단위 부피로 생각해보면, 물건 1, 2를 챙겨야 겠지만(160만원), 사실 물건 2,3을 챙겨야 한다 (220만원). 이건 그냥 딱 봐도 알겠는데, 문제는! 물건이 무지무지 많으면 어쩌냐는 것이다! 이럴 때, DP를 사용한다. :)

1. A[1:n] 배열을 정의한다. 이것은 바로 knapsack이다. 1≤j≤n이라고 했을 때, 각 단계의 j에는 1 만큼 해당되는 부피의 물건을 넣을 수 있게된다. 그리고 j단계에서의 최대 이익값을 담고 있는 변수 maxBenefit(j)=0으로 초기화한다.
2. 전체 물건들의 집합을 S라고 했을 때, j를 하나씩 증가시키면서 그 때 knapsack A에 들어갈 수 있는 최대 가치의 물건 s를 넣는다.
3. 현재 j=i이고, s의 크기가 k였다고 가정하자. 그러면 j=i에서 j=i-k까지 물건 s로 채우고, 나머지는 j=i-k=1 단계 때의 물건들로 채워준다. 그리고 새롭게 갱신되는 maxBenefit(i)값 (= maxBenefit(i-k-1) + k의 가치)을 maxBenefit(i-1)과 비교해서 더 커졌다면 S=S-{s}로 만든 뒤, A의 상태를 저장한다. 이 때, maxBenefit(i-1)에 비하여 총합 가치가 커진 것이 아니라면, 이번 step은 차라리 빈 공간으로 둔다.
4. 2단계를 j=n이 될 때 까지 반복한다.

KnapSack Problem


이렇게 DP를 사용하게 되면, j=i-k=1 번째의 최적화 답을 가져오는데 걸리는 시간은 O(1)이므로, n을 Knapsack크기, m을 물건의 개수라 하면, running time은 O(nm)이 되고, n과 m이 비슷할 때에는 O(n²)으로 polynomial time이 된다.

⊙Matrix-chain Multiplication
행렬의 곱을 어떤 순서로 행하면 가장 빠르게 할 수 있는가에 대한 문제인데, 앞의 3가지 예제외는 달리, 복잡하므로 따로 다루어야 겠다. (언제 할 지는 모르겠다. -.- )

⊙ Dynamic Programming VS Greedy Algorithm
DP에서는 모든 것이 정수라는 가정하에서 이루어졌다. 그런데, 정수가 아니라면? 예를 들어, Knapsack에서, 물건을 나눌 수 있다면 어떻게 할 것인가? (우유나 금가루 같은것들.) 이것은 바로 fractional knapsack problem으로, Greedy algorithm에 속한다. Greedy algorithm은 말 그대로, '탐욕적인 알고리즘'이다..;;


출처 : http://vorlon.eecs.cwru.edu/~kxm73/ : 덮옹님 홈페이지. 므흣.
Posted by 스니

댓글을 달아 주세요

  1. 스니스니

    앗. 이런 걸 읽는 분이 계실 줄이야 -ㅇ- 반갑습니다.
    그런데 매우 애석하게도.. 저도 잘 모르겠네요. -_-;;
    그렇게 푼 이유가 있었는데 기억이 안나는건지...
    그냥 그렇게 풀었던건지... -_-;
    알게 되면 다시 올리도록 하죠 .. ^^;;

    2005.01.09 14:13 [ ADDR : EDIT/ DEL : REPLY ]