01. Overlapping Subproblems Property
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 된 피보나치 수 :
/* Memoization 된 피보나치 수 */#include<stdio.h>#define NIL -1#define MAX 100int 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 된 문제는 상향식으로 만든 테이블에서 마지막 값을 솔루션으로서 반환한다.
/* 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번째 피보나치 수를 구하는 실행 시간을 확인해보자.
또한 Ugly Number의 메소드 2에서도 볼 수 있다
연습:
1) LCS문제를 Memoization 하라.
2) Memoization과 Tabulation 중 어떤 것이 더 효율적인가?