다이나믹 프로그래밍이란?

'하나의 문제는 단 한번만 풀도록 하는 알고리즘'이다. 한번 푼 것을 여러 번 풀지 않고 푼 정답을 저장해 놓은 뒤 꺼내 사용한다.

분할 정복 기법은 동일한 문제를 다시 푼다는 단점이 존재한다. 예를 들어 피보나치 수열은 특정한 숫자를 구하기 위해서 그 앞에 있는 숫자와 두칸 앞에 있는 숫자의 합을 구해야 한다.

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

이러한 문제는 분할 정복 기업으로 들어갈 시 큰 문제점이 야기된다. 이미 해결한 문제를 다시 반복적으로 해결하여 비효율성 문제가 생기고 기존보다 문제를 해결하는데 오랜 시간이 걸린다. 위 그림을 통해 D[12]인 경우 3번이나 반복적인 계산을 하고 있음을 알 수 있다.

다이나믹 프로그래밍의 가정

1번 가정 : 큰 문제는 작은 문제로 나눌 수 있다.

2번 가정 : 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

즉, 크고 어려운 문제가 있다면 그 문제를 작게 쪼개어 해결한 뒤에 전체의 답을 구하는 것이다.

분할 정복과 다른 점은 이 작은 문제를 배열의 저장하여 나중에 동일한 연산을 해야할 시 저장된 값을 불려와서 사용한다.

#include <stdio.h>

int d(int x) {
	if(x == 1) return 1;
	if(x == 2) return 1;
	return d(x - 1) + d(x - 2);
}

int main(void) {
	printf("%d", d(10));
}

위 경우 Dp[10]은 55 로 잘 나오나 만약 Dp[55]를 계산한다면 엄청난 연산량으로 인해 오랜시간이 걸리게 된다.

이를 해결하기 위해서 다음과 같이 수정한다.

#include <stdio.h>

int d[100];

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

int main(void) {
	printf("%d", fibonacci(30));
}

앞서 저장된 값들이 d라는 배열에 저장이 되고 한 번 구한 값을 다시 계산할 이유가 없어져 계산량이 훨신 줄어들게 된다.

출처

https://blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221233570962&redirect=Dlog&widgetTypeCall=true&directAccess=false