[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming)

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

 

직역하면 동적 프로그래밍으로 불리는 이 프로그래밍 방법은 큰 문제를 작은 부분으로 나누어 작은 부분들을 이용해 큰 문제를 해결하는 기법입니다. 이와 대조되는 분할 정복 알고리즘 역시 큰 문제를 한번에 처리하기에 연산 수가 크고 복잡하여 큰 문제를 작은 부분으로 나누는 기법입니다. 방법은 유사하지만 동적 프로그래밍은 작은 부분들을 다시 반복하여 연산하지 않는다는 차이점이 존재합니다. 즉, 큰 문제들을 작은 문제들로 나누는 과정은 동일하지만 분할 정복은 작은 문제들을 다시 연산하고 다이나믹 프로그래밍은 미리 연산된 결괏값을 재사용합니다.

 

다이나믹 프로그래밍에서 모든 작은 문제들은 반드시 한번만 사용하게 됩니다. 따라서 연산이 끝난 문제들은 어딘가에 Memo를 하게되는데 이것을 메모이제이션(Memoization)이라고 합니다. 메모이제이션은 다이나믹 프로그래밍에서 작은 문제들의 연산 값이 항상 동일하다는 점을 이용하여 큰 문제들을 해결함에 있어서 작은 문제들의 연산값들을 재사용하므로 프로그래밍 연산 속도를 증가시킵니다.

 

따라서, 다이나믹 프로그래밍의 사용 조건은 다음과 같습니다.

1. 큰 문제를 작은 문제들로 나누는 과정을 실행한다.

2. 이미 연산된 작은 문제들의 결괏값은 다시 연산해도 항상 동일하다. 

 

대표적인 예시인 Fibonacci 수열을 예로 들어보겠습니다.

피보나치 수열은 특정한 N번째 수를 구하고자 할 때 i[N] = i[N - 1] + i[N - 2] 의 점화식을 가지는 수열입니다.

위 그림은 i[5]의 값을 분할 정복 기법으로 풀이하고 있습니다. 이 수열에 따르면 i[5]의 값은 2 + 3 = 5 임을 알 수 있습니다. 하지만 위 구조에서 i[3]의 경우 왼쪽과 오른쪽에서 반복 연산된 것을 알 수 있습니다. 왼쪽에서 이미 i[3]의 연산 값이 i[2]와 i[1]의 합인 2로 연산되었음에도 불구하고 오른쪽에서 다시 연산하고 있습니다.

i[5]처럼 연산 수가 적은 구조에서는 분할 정복과 다이나믹 프로그래밍의 연산 수 차이가 적어보일 수 있지만 만약 i[100]같은 수의 피보나치 수열 값을 구한다면 어떻게 될까요? 아마도 컴퓨터가 이 값을 분할 정복 기법으로 처리하려면 엄청난 시간이 소요될 것입니다. 100에서 99와 98로 나누어지는 데 연산 수는 2, 그 밑으로 연산 수가 4, 8, 16 ... 가 되므로 2^n 이라는 수가 나옵니다. 한마디로 i[100]을 처리하려면 2의 100승인 1,267,650,600,228,229,401,496,703,205,376번의 연산을 해야하기 때문입니다. 이러한 비효율성 때문에 다이나믹 프로그래밍을 사용합니다.

다이나믹 프로그래밍을 사용하면 위와 같이 메모이제이션으로 미리 결괏값들이 저장되어 있으므로 필요 시에는 반환만 하여 사용하면 됩니다. 다시 연산할 필요가 없어져 시간 복잡도가 O(N)으로 크게 줄어들게 됩니다.

 

알고리즘 구현

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

#include <stdio.h>

int i[11];
int fibonacci_dp(int x) {
	if (x == 1) return 1;
	if (x == 2) return 1;
	if (i[x] != 0) return i[x];
	return i[x] = fibonacci_dp(x - 1) + fibonacci_dp(x - 2);
}

int main() {
	printf("%d\n", fibonacci_dp(10));

	return 0;
}
// 55

i[1]과 i[2]의 값은 항상 1이므로 모두 1을 반환하도록 합니다. i[x]가 0이 아니면, 즉 메모이제이션 되어있는 값이 존재하면 바로 그 값을 반환하도록 합니다. 저장되어 있지 않은 경우에만 재귀적으로 연산을 실행합니다.

 

 

* 나동빈님 블로그를 참고하여 개인적으로 재작성한 글입니다.