동적 계획법 (1) - Fibonacci & Binomial

Dynamic Programming (1)

Fibonacci Numbers

fibonacci (int n) {

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

return 1;

else

return fiboncci(n - 2) + fibonacci(n - 1);

}

- Recursion을 이용하여 피보나치 수를 구하는 과정에서 많은 계산이 중복된다는 문제가 있어 비효율적이다.

- 중복 계산을 구하는 방법에는 Caching기법과 Dynamic Programming기법이 있다.

Fibonacci - Memorization

- 중간 계산 결과를 caching하여 중복 계산하는 문제를 회피하게 된다.

fibonacci (int n) {

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

return 1;

else if (f[n] > -1) // 배열 f의 값들이 -1으로 추기화되어 있다 가정한다.

return f[n]; // -1보다 크다는 것은 곧 이미 계산된 값임을 의미한다.

else

f[n] = fibonacci(n - 2) + fibonacci(n - 1); // 중간 계산 결과를 캐싱한다.

return f[n];

}

Fibonacci - Dynamic Programming

- Bottom-Up 방식을 통해 기본적인 숫자부터 계산해 올라가며 중복을 피하는 기법이다.

int fibonacci (int n) {

f[1] = f[2] = 1;

for (int i = 3; i<= n; i++)

f[n] = f[n - 1] + f[n - 2];

return f[b];

}

이항 계수 (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);

}

- 순환식으로 계산할 경우 계산 과정에서 피보나치 수열때와 같이 많은 과정이 중복된다.

Binomial - Memorization

int binomial (int n, int k) {

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

return 1;

else if (binom[n][k] > -1)

return binom[n][k];

else {

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

return binom[n][k];

}

}

Binomial - 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의 의존관계를 잘 구분해야 한다.

- 이항 계수를 구할때는 배열상으로 봤을 때 (0, 0)부터 (1, 0), (1, 1)로 내려가면서 계산을 수행해야 한다.

Memorization vs Dynamic Programming

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

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

- Memorization은 Top-Down방식을 사용하며, 실제로 필요한 Sub Problem만을 해결하지만, 순환에 의존하기 때문에 overhead를 감수해야 한다.

- 동적 계획법은 Bottom-Up방식을 사용하며, 순환에 수반되는 overhead가 나타나지 않는다.