동적 프로그래밍 (Dynamic Programming)

사용 조건

 

• 작은 문제의 최적 솔루션이 그 보다 더 큰 문제의 최적 솔루션에 포함되는 경우
• 재귀적인 방법으로 구현 시 중복 호출로 인한 큰 비용/비효율이 발생하는 경우

 

피보나치 수열

 

피보나치 수열은 동적 프로그래밍의 사용 동기와 조건, 구현을 가장 쉽고 명료하게 확인할 수 있는 예제.

 

fn = fn-1  + fn-2   (n >= 3) f1 = f2 = 1 (n = 1, 2)

 

 

1. 재귀호출 방식

 

• 의사 코드 (Pseudo-code)

Fibonacci(n) {        if (n = 1 or n = 2)            then return 1;        else            return Fibonacci(n - 1) + Fibonacci(n - 2); }

 

• 구현 (Implement)

 

// Not to use dynamic programming.. int fibonachi(unsigned long long index) {     if (index == 0) {         return 0;              }          if (index == 1 || index == 2) {         return 1;     } else {         return fibonachi(index - 1) + fibonachi(index - 2);     } }

 

이러한 재귀호출 방식으로 구현한 피보나치 수열은 중복 호출로 인한 심각한 비효율을 초래한다.

 

 

그림 1. 피보나치 수열을 재귀적 용법으로 구현했을 때 발생하는 중복 호출 구간들

 

2. 동적 프로그래밍

• 의사 코드 (Pseudo-code)

 

Fibonacci(n) {        f[1] <- f[2] <- 1;   for i <- 3 to n        f[i] <- f[i-1] <- f[i-2]; return f[n]; }

 

• 구현 (Implement)

 

// Use the dynamic programing. unsigned long long accu_result[100] = {0,1,1};   int fibonachi_dynamic(int index) {          if (index <= 0) return 0;          if (accu_result[index]) {         return accu_result[index];     } else {         int fVal = 0, sVal = 0;                  fVal = fibonachi_dynamic(index - 1);         sVal = fibonachi_dynamic(index - 2);                  return accu_result[index] = fVal + sVal;     } }

 

 

3. 결과 비교

Result of Fibonachi: 832040 -> time: 0.004713 Result of Fibonachi by using dynamic programming: 832040 -> time: 0.000002

 

위는 n값이 30일 때의 피보나치 수열을 각각 재귀적 용법과 동적 프로그래밍을 이용하여 푼 결과값이다.

동적 프로그래밍을 사용했을 때 재귀적 용법을 사용했을 때 보다 훨씬 빠른 성능을 보여주고 있음을 확인할 수 있다.