동적계획법: 개요

동적 계획법(dynamic programming)은 부분 문제의 해를 결합해 문제를 해결한다. 동적 계획법은 부분 문제가 서로 중복될 때 적용할 수 있다. 동적계획법을 이용하면 모든 부분 문제를 한 번만 풀어 그 해를 테이블에 저장함으로써 각 부분 문제를 풀 때마다 다시 계산하는 일을 피할 수 있다.

 

동정 계획법 알고리즘을 개발할 때는 다음 4단계를 따른다.

1. 최적해의 구조의 특징을 찾는다.
2. 최적해의 값을 재귀적으로 정의한다.
3. 최적해의 값을 일반적으로 bottom-up 방법으로 계산한다.
4. 계산나된 정보들로부터 최적해를 구성한다.

위의 내용이 Introduction to Alogirhtm 에 수록되어 있는 내용이다.

 

위 내용을 읽고 생각해보면, 동적 계획법은 각 부분에 대한 값을 계산하고 저장해두며, 필요할 때 이용하는 방법으로 문제를 해결하는 것이라는게 잘 바로 이해가 될 것이다. 동적 계획법을 이용하여 문제를 해결할 때, 이러한 사실을 잘 기억해 두어야 한다. 동적 계획법에서 중요한 것은, "해를 구하기 위해 필요한 부분 문제를 어떻게 설정하느냐?"이다.

 

Reference

• Cormen. T. H, Leiserson. C. E, Rivest. R. L, Stein. C, “Introduction to Algorithms, Third Edition”, MIT press. 2009, pp.865-917.