동적 계획법 (Dynamic Programming)

동적 계획법 (Dynamic Programming) 은 각 단계에서 해결해야 할 일련의 문제들이 상호 관련성을 맺고 있을 경우에, 

어느 단계에서 하나의 결정이 이루어지면 그 결정은 그 다음 단계의 문제를 결정하는 데 영향을 미치게 되고 

그 결과 달성하고자 하는 목표에도 영향을 미치게 되기 때문에 이러한 문제를 해결하기 위해서 필요한 알고리즘이다.

대표적인 예로 [피보나치 수] 가 있다. 피보나치 수는 1 1 2 3 5 8 ... 형식으로 이루어져 있는 수열을 의미하는데,

초기값인 첫번째 항과 두번째 항은 1이고, n-2 번째 항과 n-1 번째 항을 더해서 n번째 항을 구한다.

n 번째 피보나치 수열을 구하는 코드는 위와 같다.

하지만 피보나치 수를 구하는 알고리즘을 위의 코드 같이 재귀적으로 짜면 문제가 발생한다.

왜냐하면 위의 사진과 같이 4번째 항을 구할 때 불필요한 값이 중복되서 계산되기 때문이다.

또한 위와 같이 피보나치 수를 구하는 것은 분할정복법을 이용한 풀이가 아니다. 

왜냐하면 분할정복법은 문제를 각각 독립된 풀이로 해결 한 후에, 합치는 것이기 때문이다. 

분할정복법은 큰 문제를 쪼개 내려가서 합치면서 올라와 해결하기 때문에 Top Down 이라고한다.

그러므로 피보나치 수를 구하는 알고리즘을 동적 계획법으로 풀이하려면 

작은 풀이부터 차근차근 올라와 원하는 값을 얻어야 하는데, 

예를 들면 F(6)을 구하기 위해서는 F(1)~F(5)를 차례대로 구한 후에 F(6)을 구하자는 것이다. 

즉, 구하는 값보다 작은 모든 풀이를 먼저 하여 원하는 값을 얻어내는 것이다. 

그래서 동적 계획법 (Dynamic Programming)은 분할계획법(Top Down)과 다르게 밑에서부터 올라가서 해결하는 알고리즘이다.

---

---

이제 피보나치 수 구하기를 동적 계획법의 문제 풀이 순서에 따라 다시 풀어보자.

피보나치 수에서는 부분 문제를 정의하기 간단하지만, 

동적 계획법을 이용한 문제에서 가장 어려운 부분이 첫번 째 단계인 부분 문제를 정의하는 것이다.

점화식을 구하기 위해서 문제를 정의하는 것인데, 여기에서는 F(i) 를 피보나치 수열의 i번째 값이라고 정의한다.

부분 문제를 정의했으므로, 이제 점화식을 구해야한다.

F(i) = F(i-1) + F(i-2) 로 간단하게 생각 할 수 있다.

예를 들어 F(7) 을 구하기 위해서는 F(5) 와 F(6)을 알아야하고, 

F(6) 을 구하기 위해서는 F(4)와 F(5)를 알아야 하고,

F(5)를 구하기 위해서는 f(3)과 F(4)를 알야아 한다.

이런 식으로 계속 파악하다 보면 진행방향을 파악할 수 있는데,

즉, 0번째부터 차례대로 올라와야 원하는 답을 얻을 수 있다는 것이다.

피보나치 수열의 초기값은 F(0)=1, F(1)=1 이다.

초기값을 주고나서, 2번 째 항부터는 쉽게 구할 수 있다.

이렇게 피보나치 수 구하기 문제해결을 사고하는 방식이 동적 계획법을 사용한 방법이다.

이 문제로는 동적 계획법을 이해하기 부족하기 때문에, 또 다른 문제를 예시로 들어 설명하겠다.

출처 : Algorithm LABS