[알고리즘] 동적 계획법 | 다이나믹 프로그래밍 ( Dynamic Programing)

동적 계획법은 주어진 문제를 여러 개의 부분 문제로 분할하여 각 부분문제의 해결안을 바탕으로 주어진 문제를 해결하는 기법이다.

이 때 각 부분 문제는 다시 여러개의 부분 문제로 분할될 수 있다.

각 부분문제는 원래 주어진 문제와 동일한 문제이지만 입력 크기가 작다. 따라서 부분 문제를 반복해서 분할하면 궁극적으로 입력의 크기가 매우 작은 단순한 문제가 되기에 쉽게 문제를 해결할 수 있게된다. 

 

반복해서 여러 번 호출되는 부분 문제가 있을 경우 해당되는 부분 문제가 첫 번째 수행될 때 그 결과를 기록해 두었다가 이후에 다시 수행이 요구될 때 또 수행하지 않고 기록해둔 결과를 이용하는 것이 동적 계획법의 핵심이다. 

 

즉, 한 마디로 동적 계획법을 표현하자면 '하나의 문제는 단 한 번만 풀도록 하는 알고리즘'이다.

 

이를 알아보기 전에 분할-정복 기법의 단점에 대해 살펴보도록 하자.

이 기법의 단점은 부분문제들이 중복되는 경우와 부분문제의 결합단계가 지나치게 복잡한 경우 나타난다는 것이다.

예를들어 피보나치 수열에 대해 생각해보자. 분할 정복 기법은 동일한 문제를 다시푸는 단점을 가지고 있는데, 이 단점을

극명하게 보여주는 것이 피보나치 수열이다.

피보나치 수열은 특정한 숫자를 구하기 위해 그 앞에 있는 숫자와 두 칸 앞에 있는 숫자의 합을  구해야 한다.

피보나치 수열의 점화식: f(n) = f(n-1) + f(n-1)  이 공식에 따라 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...와 같이 나아갈 수 있다. fib(5) 같은 경우 동일한 계산 과정이 여러번 반복되는 것을 직접 계산해 봄으로써 알 수 있을 것이다.

 

따라서 이럴 때 동적 계획법을 이용하여 문제를 해결할 수 있다.

 

작은  부분문제의 해가 전체 문제의 해를 구성하는데 사용되어야하는 성질

(작은 문제에서 구한 정답이 그것을 포함하는 큰 문제에서도 동일해야한다.)

 

즉, 문제의 해를 구성함에 있어서 앞에서 구한 부분 문제의 해가 사용되고 있는데, 이와 같은 성질을

최적성의 원리라고 한다. 따라서 작은 문제의 해를 구한 다음에 그들을 합하면 큰 문제의 해가 되어야한다.

만약 어떤 문제의 한 사례에 대한 최적해가 모든 부분 사례에 대한 최적해들을 항상 포함할 때 동적 계획법의 문제에 적용된다고

정의 할 수 있다. 

 

동적 계획법으로 문제를 해결하려면 그 문제가 최적성의 원리를 만족해야한다. 

부분해를 계속 구성해가면서 전체 문제에 도달하는 방법을 사용하고 있기 때문이다.

어떤 문제에 이 원리가 적용된다면 부분문제에 대한 최적해를 이용하여 더 큰 크기의 문제에 대한

최적해를 구하는 순환적 관계를 나타내는 점화식을 도출할 수 있다.

따라서 문제의 크기가 작은 경우에 대한 점화식의 해를 구한 다음 점점 크기가 큰 문제의 해를 구할 수 있게 되는 것이다.

 

동적 계획법과 욕심쟁이 방법을 비교해보자.

이 두 방법 모두 최적성의 원리가 적용된다는 공통점을 가지고 있다. 

차이점이 있다면, 동적 계획법에서는 모든 가능성을 고려하여 결정을 내리게 되므로 항상 최적의 결과를 얻을 수 있지만,

욕심쟁이 방법은 단계별로 진행되어 각 단계에서는 현재 상태에서 가장 최적이라고 판단되는 결정을 내리게 되므로 문제에 따라

최적해를 구할 수도, 그렇지 않을 수도 있다는 단점을 가지고 있다.