DP(1) 메모제이션과 bottomUp방식

DP는 Dynamic Programming이라는 말은 줄인말이다. 

 

Memoization 

memoization은 같은 계산이 반복 될 때 이를 기록해두어 계산을 진행하지 않고 저장된 값을 불러오는 것이다. 

fibonacci의 예를 들면

int fibo(int n){
	if( n == 1 || n == 2)
    	return 1;
    else 
    	return fibo(n-1) + fibo(n-2);
 }

일반적인 코드는 위와 같이 작성한다. 하지만 위와 같이 작성되면 단점이 있는데 같은 계산이 반복되는 것이다. 

아래의 경우 fib(2), fib(1), fib(3) 등의 재귀 함수가 반복되는 것을 볼 수 있다. 했던 계산식을 계속해서 반복하는 단점이 존재한다. 

그래서 아래와 같이 작성을 한다. 

int fibo(int n){
	if(n==1 || n==2)
    	return 1;
	else {
		if(memo[n] == 0) 
           memo[n] = fibo(n-1) + fibo(n-2);
        return memo[n];	
    }
}

모든 메모를 0으로 초기화한 후 memo의 값을 memo[n] = memo(n-1) + memo(n-2);와 같이 기록해둔다. 

 

bottomUP

다른 방법은 bottomUp 방식이 있다. bottomUp 방식은 아래의 기본값부터 차례대로 상위 계산까지 올라가게 하는 것이다. 

int fibo(int n){
	f[2] = f[1] = 1;
    for(int i = 3; i <= n; i++)
		f[i] = f[i-1] + f[i-2];
    return f[i];
 }

위와 같이 작성 해주면 가장 작은 fibo(3)부터 위로 차례데로 계산하난 방식이다. 그럼 O(n)의 속도 만큼 피보나치의 값을 구할수 있다.

 

이항계수 

 

이항계수는 nCk n개의 경우에서 k개를 선택할 경우를 의미한다. 

int nCk(int n, int k){
	if( n==k || k == 0)
    	return 1;
    else {
    	return nCk(n-1, k) + nCk(n-1, k-1);
    }

위와 같이 c언어로 표현할 수 있다. 그럼 이도 그렇듯이 fibo나치 처럼 반복되는 계산식이 많을 것이다. 

이 값도 메모제이션으로 해결할 수 있다.

 

int nCk(int n, int k){
	if( n==k || k==0)
    	return 0;
    else {
    	if(map[n][k] == -1)
        	map[n][k] = nCk(n-1, k) + nCk(n-1, k-1);
        return map[n][k];
    } 
        

위에는 2차원 배열 형태로 이루어져있다. 2차원 배열을 활용하여 map[n][k]와 같은 형태로 값을 저장하고 호출해준다. 

 

bottomUp방식으로 활용

int nCk(int n, int k){
	for(int i = 0; i <= n; i++){
    	for(int j = 0; j <= k && j <= i; j++){
        	if( k == 0 || n == k )
            	map[i][j] = 1;
            else 
            	map[i][j] = map[i-1][j] + map[i-1][j-1];
         }
    }
    return map[n][k]
 }

기본적인 값 부터 시작하여 차례대로 위의 값까지 계산해주면 됩니다. 하지만 여기서는 2차원 배열인데 bottomUp방식이라고 할 수 있을까 라고 생각이듭니다. 

 

그래서 이렇게 생각하면 좋을 것 같습니다. 

          왼쪽 값     =  오른쪽 연산
오른쪽 연산은 왼쪽값보다 먼저 연산이 되는 순서입니다. 이러한 것을 bottomUp방식으로 생각하겠습니다. 

 

특징요약

1. 순환식의 값을 계산하는 기법들이다.
2. 둘다 동적 계획법의 일종으로 보기도함 
3. Memojation은 topDown 방식이며 실제로 필요한 subProblem만 푼다. 
4. 동적 계획법은 bottomUp 방식이며 recursion에 수반되는 overhead가 없다.