다이나믹 프로그래밍 (Dynamic Programming)

다이나믹 프로그래밍이란 '하나의 문제는 한번만 풀게 하는 알고리즘'이다. 즉, 이미 해결한 문제를 중복적으로 수행하는 것을 방지하는 알고리즘이다.

 

일반적으로 대부분의 분할 정복 기법은 동일한 문제를 다시 풀게 된다는 단점이 있다. (정렬과 같은 경우는 이러한 문제가 일어나지 않는다. 그 예시로 퀵 정렬과 병합 정렬은 매우 빠르게 정렬을 수행할 수 있다.)

분할 정복 기법의 단점이 드러나는 대표적인 예로는 '피보나치 수'가 있다.

 

*피보나치 수열의 점화식 : D[i] = D[i-1] + D[i-2]

 

만약 15번째 피보나치 수를 구하고자 한다면 14번째 피보나치 수와 13번째 피보나치 수를 더해야 한다. 그럴 경우, 14번째 피보나치 수를 또 구해야 하는데 이 과정에서 이미 구한 13번째 피보나치 수를 구하는 것을 중복적으로 수행하게 되어 비효율성을 유발한다.

 

▷그래서 다이나믹 프로그래밍은 분할 정복 기법과 무엇이 다른가?

▶다이나믹 프로그래밍은 '메모이제이션(Memoization)'을 사용한다. 말 그대로 이미 해결한 문제는 배열에 저장하여 이후에 재사용하는 것이다.

 

#include <iostream>

using namespace std;

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

int main() {
	int result = 0;
	result = fibonacci(50);
	printf("피보나치 수 : %d", result);
	
}

위와 같이 재귀적으로 피보나치 수를 구하게 됐다고 해보자. 아마 일정 수까지는 피보나치 수를 정상적으로 구할 수 있을 것이다. 하지만 50번째 피보나치 수를 구하고자 한다면 컴파일은 성공하되, 계속 기다려도 CPU는 계속해서 연산만 진행할 것이다. 그도 그런것이 재귀적으로 50번째 피보나치 수를 구하려면 총 2^50만큼의 연산을 수행해야 하기 때문이다.(이는 거의 1000,000,000,000,000번이 넘는 횟수이다)

 

#include <iostream>

using namespace std;

int d[100];

int fibonacci(int n) {
	
	if (d[n] != 0) {
		return d[n];
	}
	else { 
		return d[n] = fibonacci(n - 1) + fibonacci(n - 2); 
	}
}

int main() {
	int result = 0;
	d[1] = 1;
	d[2] = 1;
	result = fibonacci(50);
	printf("피보나치 수 : %d", result);
	
}

위와 같이 추가적인 배열 d를 이용해 피보나치 수를 구하게 되면 이미 해결한 문제에 대해서는 반환만 해주면 되기 때문에 성공적으로 50의 피보나치 수를 구할 수 있다.(다만, 50번째의 피보나치 수는 int 형으로 표현이 불가능 하기에 쓰레기 값이 나올 것이다)