Dynamic Programing (동적 프로그래밍)

Dynamic Programing이란?

 

동적 프로그래밍은 딱히 프로그래밍 방법론은 아니다.

이름이 '프로그래밍'이라서 헷갈리는데, 그냥 알고리즘 방식의 하나라고 생각하면 된다.

 

동적 프로그래밍 방법에서는

입력 크기가 작은 문제들을 먼저 해결해서 그 결과값(해)들을 저장해두고 (=memorization)

이것을 이용해 크기가 큰 문제들을 해결한다.

작은 문제의 결과들을 저장해두었기 때문에

큰 문제의 결과를 구할 때 다시 계산할 필요가 없어 속도가 빠르다.

 

 

 

분할 정복 알고리즘과의 차이

 

동적 프로그래밍은 분할 정복(Divide and Conquer) 알고리즘과 비슷한데

분할 정복이 하향식(top-down) 접근을 하는 것이라면

동적 프로그래밍은 상향식(bottom-up) 접근을 한다.

 

무슨말이냐면

분할 정복 방법이 큰 문제(top)를 순환적으로 나누어서(down) 해결하는 방식이고

동적 프로그래밍은 작은 문제들(bottom)의 해를 구해서 큰 문제(up)의 해를 구하는 것이다.

 

이때 분할 정복에서 분할된 문제들은 서로 독립적이지만

동적 프로그래밍에서의 작은 문제들은 서로 중복되는 부분이 있다. (그렇기 때문에 저장해둔 값들의 재사용이 가능하다)

 

 

 

예를 들어보자

 

동적 프로그래밍의 가장 대표적인 문제는 피보나치 수열 문제이다.

 

피보나치 수열이란?

바로 앞 두 항의 수를 합친 값이 다음 항의 값이 되는 수열이다.

(0, 1항의 값은 1이다)

1, 1, 2, 3, 5, 8, 13, ... 이런 식으로 나아가는 것이다.

 

 

 

 

동적 프로그래밍 방법론으로 이를 분석해보면 다음과 같다.

 

0항과 1항의 값은 1로 주어져 있으니 넘어가고

가장 작은 문제는 2항의 값을 구하는 것이다.

2항의 값은 그 앞에 있는 1항과 0항의 합이 되므로

1+1 = 2가 된다.

 

// 동적 프로그래밍으로 피보나치 수열 구하기
int[] fibonacci = new int[n];

// 0, 1항의 값은 1로 주어져있다.
fibonacci[0] = 1;
fibonacci[1] = 1;

// 피보나치 수열의 각 항의 값은 앞선 두 항의 값의 합이다.
for(int i = 2; i<n; i++){
	fibonacci[i] = fibonacci[i-1] + fibonacci[i-2];
}

 

작은 문제의 결과값을 array에 저장해놓고

큰 문제의 값을 구할때 불러와서 사용하고 있다.

 

반면에 분할 정복 방법론에서는 작은 문제의 값을 저장하지 않고

자기 자신을 불러와서 순환적(재귀적)으로 값을 구한다.

 

// 분할 정복으로 피보나치 수열 구하기
int fibonacci(int n);

if (n==0) fibonacci = 1;
if (n==1) fibonacci = 1;

for(int i=0; i<n; i++) {
	fibonacci(n) = fibonacci(n-1) + fibonacci(n-2);
}

 

위 코드에서는 array 대신 함수를 사용하고 있는데

이 경우에는 n-1, n-2의 값을 매번 계산해야 한다.

저장해둔 값을 불러오는 동적  프로그래밍 방식보다 시간이 더 소요된다.

 

 

 

따라서 소문제들이 중복되는 경우에는

분할 정복 대신 동적 프로그래밍을 사용하는 것이 훨씬 효율적이다.

 

단, 소문제들이 중복되지 않고 독립적인 경우에는

동적 프로그래밍 방법을 쓸 수 없으므로 분할 정복을 사용해야 한다.