알고리즘설계기법 - 4. 동적 계획법

재귀적인 recursive 방법의 한계

- 재귀적 방법은 문제를 간단한 부분 문제로 만듬

- 하지만 부분 문제의 크기 합을 작게 유지시켜야만 효과적임

- 부분 문제의 크기가 균형이 맞지 않을시 복잡도가 지수적으로 증가

 => 재귀적인 방법의 한계로 인해 동적 계획법 이용

 

 

 

동적 계획법 dynamic programming

- 부분 문제들의 답을 별도의 표에 기억

- 필요할때마다 표를 참조

   * 재귀적 방법의 문제 : 재귀적인 방법에선 그 표의 값을 매번 새로 계산했었음

=> 동적 계획법은 부분 문제의 답을 기억. 이후 다시 계산하지 않음