Dynamic Programming

 이번 포스팅에서는 Dynamic Programming의 개념적인 내용을 살펴보겠다. 자세한 적용 예는 좀 더 공부한 후에 더 자세히 포스팅하도록 하겠다.

 

•  Dynamic Programming는 간단히 말해 부분 문제의 해를 결합해 문제를 해결하는 것을 의미한다. 부분 문제가 서로 중복될 때,즉 부분 문제가 다시 자기 자신의 부분 문제를 공유할 때 적용할 수 있다.

 

 부분문제를 푸는 것은 분할정복 기법(재귀방법)과 비슷하지만 다른 점이 있다.

• 분할 정복 기법   VS   Dynamic Programming

분할 정복 기법(재귀적 방법)	Dynamic Programming
부분 문제를 단순히 반복적으로 계산하여서 해결한다. 필요 이상의 계산이 필요하기 때문에 시간이 오래걸릴 수 있다.	부분 문제를 해결한다는 점은 분할 정복 기법과 비슷하지만 한 번 계산한 부분 문제는 별도의 테이블(메모리)에 저장하여 쓸데없는 계산 시간을 줄인다. 다만 부가적인 메모리가 필요하다는 단점이 있다.

 

Dynamic Programming을 이용하는 순서

1. 최적해의 구조의 특징을 찾는다.

2. 최적해의 값을 재귀적으로 정의한다.

3. 최적해의 값을 일반적으로 상향식(bottom-up) 방식으로 계산한다.

4. 계산된 정보들로부터 최적해를 구성한다.

 

[참고자료]

Introduction to algorithm(3rd) - Thomas H. Cormen .....