피보나치 수열을 구하는 방법을 예로 들어 몇가지 패턴을 정리해본다.
1. Recursion Function
int fib(int n){
if(n==1 || n==2){
return 1;
}else{
return fib(n-1) + fib(n-2);
}
}
재귀 함수를 이용하여 값을 구할 경우에는 top-down 방식으로 진행된다. 이때 각 tree모양으로 함수들이 뻗쳐나가기 때문에 중복되어 연산되는 경우가 급격히 늘어난다.
2. Memoization
Cache 배열에 계산된 값을 버리지 않고 저장하므로 같은 fib(n)을 중복으로 계산하는 일이 없어진다. '캐싱한다'고 한다.
int fib(int n){
if(n==1 || n==2){
return 1;
}else if(cache[n]>-1){
return cache[n];
}else{
cache[n] = fib(n-1) + fib(n-2);
return cache[n];
}
}
메모이제이션은 top-down방식이고 실제 필요한 sub problem을 푼다. 동적계획법의 일부이다.
3. Dynamic Programming
int fib(int n){
array[1] = array[2] = 1;
for(int i=3; i<=n; i++){
array[n] = array[n-1] + array[n-2];
}
return array[n];
}
이처럼 가장 기본적인 값으로 특정한 값을 계산하려는 것을 bottom-up 방식이라고 한다. 동적계획법의 좁은 의미 가운데 하나이다. 재귀에 수반되는 overhead가 없는 것이 특징이다.
* 피보나치 수열외에, 이항계수 문제도 nCk = n-1Ck-1 + n-1Ck 의 성질을 이용하여 위의 방법들과 마찬가지로 해결할 수 있다.