알고리즘 동적계획법(dynamic programming)

 

●동적계획법(dynamic programming)

- 작은 문제들의 해를 먼저 구하여 저장하고 더 큰 문제의 해를 구할 때 작은 문제의 해를 반복계산하지 않고 저장도니 ㄱ려과를 사용하는 방법이다. 동적계획법을 하기 위해선 주어진 문제의 해를 구하기 위한 순환적인 성질을 구성하여야 한다. 상향식으로 작은 부분부터 해를 구한다.

 

 

●장점

- 프로그램을 구현할 때에는 필요한 모든 가능성을 고려해서 구현하게 된다. 따라서 동적 계획법을 이용하여 항상 최적의 결과를 얻을 수 있다.

 

 

●단점

- 모든 가능성에 대한 고려가 불충분할 경우  최적의 결과를 보장할 수 없다. 동적 계획법을 구현하기 위해서는 충분히 많은 가능성에 대한 고려를 해야 한다. 다른 기법에 비해 메모리를 많이 요구한다.

 

 

●점화식 세우는 법

①해를 구하기 위한 순환적인 성질을 구성해야 한다.

 

②전체 문제도 부분 문제 형태로 표현할 수 있어야 한다.

 

③문제를 어떻게 부분 문제로 분할할 것인지 생각해야 한다.

 

④보통 동적 계획법 문제는 일정 회수의 선택을 반복하는 구조로 이루어져 있다.

 

⑤그 상태에서의 선택과 그 선택 전의 상태를 고려해야 한다.

 

⑥한 번의 선택에서는 생길 수 있는 모든 가능성을 고려해야 한다.

 

⑦최적해를 찾는 문제라면, 그 가능성 중에서 가장 좋은 선택을 찾아야 한다.