http://www.geeksforgeeks.org/dynamic-programming-set-1/
Dynamic Programming - Set 1. Overlapping Subproblems Property
Dynamic Programming은 어려운 문제를 푸는 알고리즘의 유명한 예로, 복잡한 문제를 subproblem들로 나누어서 같은 subprobelm들의 결과를 저장하여 복잡한 계산의 반복을 피한다.
Dynamic Programming으로 해결할 수 있는 문제는 다음 두 주요 특성을 가진다
1) Overlapping Subproblems
2) Optimal Substructure
1) Overlapping Subproblems:
분할정복Divide and Conquer과 같이, Dynamic Programming은 subproblem들의 솔루션들을 결합한다. Dynamic Programming은 주로 같은 subproblem들의 솔루션이 계속해서 필요할 때 사용된다. Dynamic Programming에서 subproblem들의 복잡한 솔루션들을 한 테이블에 저장하여 재연산을 하지 않는다. 그래서 Dynamic Programming은 같은(overlapping) subproblem들이 없을 때 사용하기 힘들다. 반복할 필요가 없다면 솔루션을 저장할 필요가 없기 때문이다. 예를 들어, 이진 탐색Binary Search는 같은 subproblem들이 없다. 재귀로 풀어지는 많은 subproblem들로 이루어진 유명한 문제로는 피보나치 수가있다.
int fib(int n)
{
if ( n <= 1 )
return n;
return fib(n-1) + fib(n-2);
}
fib(5)의 실행 재귀 트리 :
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
/ \
fib(1) fib(0)
함수 fib(3)이 2번 호출 되는 것을 볼 수 있다. 만약 f(3)의 값을 저장했다면, 그것을 계산하는 대신 전에 저장했던 값을 다시 사용할 수 있다. 값을 저장하고 이 값을 재사용하는 방법에는 두 가지가 있다.
a) Memoization (하향식):
b) Tabulation (상향식)
a) Memoization : 재귀형태와 비슷한 Memoization 된 문제는 솔루션을 계산하기 전에 탐색 테이블에서 그 반환 값을 탐색한다. 탐색 어레이는 NIL과 같은 초기값으로 초기화 되어있다. subproblem들의 솔루션을 필요로 할 때마다 먼저 탐색 테이블에서 탐색한다. 만약 이미 계산된 값이 없다면 값을 계산하고 결과를 탐색 테이블에 삽입하여 이후 재사용 가능하게 한다.
Memoization 된 피보나치 수 :
#include<stdio.h>
#define NIL -1
#define MAX 100
int lookup[MAX];
void _initialize()
{
int i;
for (i = 0; i < MAX; i++)
lookup[i] = NIL;
}
int fib(int n)
{
if(lookup[n] == NIL)
{
if ( n <= 1 )
lookup[n] = n;
else
lookup[n] = fib(n-1) + fib(n-2);
}
return lookup[n];
}
int main ()
{
int n = 40;
_initialize();
printf("Fibonacci number is %d ", fib(n));
getchar();
return 0;
}
|
b) Tabulation : Tabulation 된 문제는 상향식으로 만든 테이블에서 마지막 값을 솔루션으로서 반환한다.
#include<stdio.h>
int fib(int n)
{
int f[n+1];
int i;
f[0] = 0; f[1] = 1;
for (i = 2; i <= n; i++)
f[i] = f[i-1] + f[i-2];
return f[n];
}
int main ()
{
int n = 9;
printf("Fibonacci number is %d ", fib(n));
getchar();
return 0;
}
|
두가지 다 subproblem들의 해답을 저장한다. Memoization의 테이블은 요구에 따라 채워지나, Tabulation의 테이블은 처음부터 하나씩 전부 채워진다. Tabulation과 다르게, Memoization에서는 탐색테이블의 모든 공간이 채워질 필요는 없다. 예를 들어, Memoization 된 LCS문제는 모든 공간이 채워질 필요가 없다.
Memoization, Tabulation, 기본재귀 버전의 40번째 피보나치 수를 구하는 실행 시간을 확인해보자.
기본재귀
Memoization
Tabulation
또한 Ugly Number의 메소드 2에서도 볼 수 있다
연습:
1) LCS문제를 Memoization 하라.
2) Memoization과 Tabulation 중 어떤 것이 더 효율적인가?
