Dynamic Programming(동적 계획법)

동적 계획법의 원리는 매우 간단하며 작은 문제가 중첩되어있는 문제를 해결하는데 사용하는 방법이다. 일반적으로 문제를 풀때 하위의 작은 문제들을 해결한다음 합쳐서 결과를 얻게 되는데 작은 문제를 해결할때 생기는 반복적인 작업의 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결 할수 있다. 예를 들어 피보나치 수열을 구하는 함수는 다음과 같다. function fibonazzi(n) { if(n==0 || n==1) return 1; else return fibonazzi(n-1)+fibonazzi(n-2); } 이때, fibonazzi(5)를 구한다 fibonazzi(5) = fibonazzi(4) + fibonazzi(3) = fibonazzi(3) + fibonazzi(2) + fibonazzi(2) +fibonazzi(1) = fibonazzi(2) + fibonazzi(1)+fibonazzi(1)+fibonazzi(0)+fibonazzi(1)+fibonazzi(0))+fibonazzi(1) = fibonazzi(1)+fibonazzi(0)+fibonazzi(1)+fibonazzi(1)+fibonazzi(0)+fibonazzi(1)+fibonazzi(0))+fibonazzi(1) 이때에 fibonazzi(2)의 하위 계산은 반복된다. 이 값을 저장하는 객체를 두고 하위 작업의 결과 값을 저장해 둔다면 복잡도는 O(n)이 된다. 다음 코드는 동적계획법을 사용한 피보나치의 예이다. 코드를 간단히 보게되면 하위 문제의 해결값을 넣어둘 배열 m을 두게 됩니다. 피보나치 0과 1의 값은 1이기 때문에 m[0]과 m[1]에 1을 넣어주고 m[2]부터 사용자가 구하고자 하는 값인 m[n]까지 구하게 됩니다. 이때 바로 하위의 값은 이미 구해서 메모리에 있기 때문에 복잡도는 높아지지 않고 구할수 있게 됩니다. 결과적으로 m[n]의 값은 하위 점화식으로 부터 분할정복법으로 구한 값과 같은 값을 구한게 됩니다.