개발 공부 - [동적계획법 (Dynamic Programming)] Dynamic Programming - 1

다이나믹 프로그래밍 = 동적계획법

피보나치 수열

: 많은 계산이 중복됨

-> recursion 으로 계산하니까 중복현상이 있음!

Memoization

int fib(int n)

{

     if (n==1 || n==2)

         return 1;

     else if (f[n] > -1) /* 배열 f가 -1으로 초기화되어 있다고 가정 */

         return f[n]; /* 즉 이미 계산된 값이라는 의미 */

     else {

         f[n] = fib(n-2) + fib(n-1); /* 중간 계산 결과를 caching */

         return f[n];

     }

}

bottom-up 방식으로도 중복 계산을 피할 수 있다.

이항 계수(Binomial Coefficient)

int binomial(int n, int k)

{

     if (n == k || k == 0)

         return 1;

     else

         return binomial(n - 1, k) + binomial(n - 1, k - 1);

}

역시 많은 계산이 중복되어 일반적으로 

n     n-1             n-1

   =           +                   과 같은 경우의 수를 볼 수 있다.

k       k              k-1

Memoization

int binomial(int n, int k)

{

     if (n == k || k == 0)

         return 1;

     else if (binom[n][k] > -1) /* 배열 binom이 -1로 초기화되어 있다고 가정 */

         return binom[n][k];

     else {

         binom[n][k] = binomial(n-1, k) + binomial(n-1, k-1);

         return binom[n][k];

     }

}

Dynamic Programming

int binomial(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)

                     binom[i][j] = 1;

                 else

                     binom[i][j] = binom[i-1][j-1] + binom[i-1][j];

                 }

         }

         return binom[n][k];

}

bottom-up 방식으로 중복 계산을 피함 

Memoization vs. Dynamic Programming

- 순환식의 값을 계산하는 기법들이다.

- 둘 다 동적계획법의 일종으로 보기도 한다.

- Momoization은 top-down방식이며, 실제로 필요한 subproblem만을 푼

다.

- 동적계획법은 bottom-up 방식이며, recursion에 수반되는 overhead가

없다.