동적 계획법 (DP)

1. 개요

[그림 1] 동적 계획법 ( Dyanmic Programming )

 

완전검색을 좀 더 효율적으로 하는 방법

Recursive + Memoization 기법을 활용

(1) 메모이제이션 (Memoization) : 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기법으로 동적계획법의 핵심이 되는 기술이다.

(2) 동적계획법의 적용 요건

1. 최적 부분문제 구조 (Optimal Substructure) : 최적화 원칙이란 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다는 것이다.

동적 계획법의 방법 자체가 큰 문제의 최적 해를 작은 문제의 최적해 들을 이용해서 구하기 때문에 만약 큰 문제의 최적해가 작은 문제들의 최적해로 구성되어있지 않다면 이 문제는 동적 계획법을 적용할 수 없다.

2. 중복 부분문제 구조(Overlapping subproblem) : 동적 계획법 문제는 순환적인 성질 때문에 이전에 계산되어졌던 작은 문제의 해가 다른 어딘가에서 필요하게 되는데 이를 위해 이미 해결된 작은 문제들의 해들을 어떤 저장공간(Table)에 저장하게 된다.

이렇게 저장된 해들은 다시 필요할 때마다 해를 얻기 위해 다시 문제들을 재 계산하지 않고 Table의 참조를 통해서 중복된 계산을 피하게 된다.

(3) 동적계획법과 분할 정복의 비교

분할정복 (Divide and conquer)	동적 계획법 (Dynamic Programming)
-연관 없는 부분 문제로 분할 한다 - 부분 문제를 재귀적으로 해결한다. - 부분 문제의 해를 결합(combine)한다. - 분할 정복은 같은 부분문제가 나타날 경우 재계산한다. - 하향식 방법으로 문제를 해결   (병합정렬, 퀵 정렬)	- 부분 문제들이 연관이 없으면 적용할 수 없다. 즉, 부분문 제들은 더 작은 부분문제들을 공유한다. - 모든 부분문제를 한번만 계산하고 재사용(동적 계획법은 같은 부분 문제가 나타날 경우 다시 계산하지 않음) - 상향식 방법으로 문제를 해결

(4) 동적 계획법 적용 3단계

1. 최적해 구조의 특성을 파악하라.

- 문제를 부분 문제로 나눈다.

2. 최적해의 값을 재귀적으로 정의하라

- 부분문제의 최적해 값에 기반하여 문제의 최적해 값을 정의한다.

3. 상향식 방법으로 최적해의 값을 계산하라.

- 가장작은 부분문제부터 해를 구한 뒤 테이블에 저장한다.

- 테이블에 저장되어 있는 부분 문제의 해를 이용하여 점차적으로 상위 부분 문제의 최적해를 구한다. (상향식 방법)

---

2. 동적 계획법 예제 1 - 피보나치 수열 (Fibonacci Series)

[그림 2] 피보나치 수열 ( Fibonacci Series )

피보나치 수열을 코드로 작성한다고 생각하면 재귀호출을 떠올리기 쉽다. 피보나치의 정의를 C언어로 구현하면 아래와 같다.

int f(int n) { if(n <= 2) return 1; else return f(n-1) + f(n-2); }

재귀호출은 함수가 호출되면 스택에 데이터가 쌓인다. 그 함수의 실행이 끝났을 때 메모리가 해제되는 방식인데, 즉, 함수가 호출되면 메모리에 쌓이는것이 계속 증가한다는 소리다. 

예를들어 5의 피보나치수를 구한다고 생각해보자. 그러면 4와 3의 피보나치 수를 알아야한다. 4의 피보나치 수를 알려면 2와 3의 피보나치 수를알아야하고... 5의 피보나치수를 구하는데 총 9번의 함수가 호출된다

이렇게 숫자가 작은데도 많은 수의 호출을 하는데 숫자가 조금만 더 커지면 어떻게 될까? 아마 시간복잡도와 공간 복잡도가 엄청 커져서 속도에 있어서 취약하고 스택오버플로우까지 발생할 수도 있다.

따라서, 이런 삽질 연산을 방지하기 위해 이전에 계산했던 값들을 따로 배열에 저장하는 방식의 동적 계획법을 이용한다.

int main() { long long int start, end; long long int res; long long int fiboCnt; while (1) { int startTime, endTime; res = input(&start, &end); if (res == FALSE) break; printf("---------------------------------------\n"); printf("[ 동적계획법(DP)를 이용한 처리 결과 ]\n"); startTime = clock(); fiboCnt = dpFibonacci(start, end); // end값이 10억을 넘어가도 매우 빠름 printf("Fibonacci 개수 : %3d\n", fiboCnt); endTime = clock(); printf("알고리즘 실행 소요시간 : %d(millisecond)\n",(endTime-startTime)); } return 0; } //////////////////////////////////////////////////////////////////// // DP long long int dpFibonacci(long long int start, long long int end) { long long int fiboNum = 0; long long int fibonacciCnt = 0; long long int i; for (i = 1; fiboNum <= end; ++i) { fiboNum = dpfibo(i); // i번째 fibonacci 수를 찾음 if (fiboNum >= start && fiboNum <= end) // 구간이내의 fibonacci수 이면 { ++fibonacciCnt; printf("%lld\n", fiboNum); } } return fibonacciCnt; } long long int dpfibo(int num) // num번째 fibonacci수의 값을 구함 { if (memo[num] == 0) memo[num] = dpfibo(num - 2) + dpfibo(num - 1); return memo[num]; }

이렇듯 동적계획법을 이용하면 막대한 양의 메모리를 희생하는 대신 아주 빠르게 연산을 해준다.