<aside> <img src="/icons/list-indent_lightgray.svg" alt="/icons/list-indent_lightgray.svg" width="40px" />

Table Of Contents

</aside>

동적 계획법(Dynamic Programming)

전체 문제를 한 번에 해결하는 것이 아니라 작은 부분 문제들을 해결하고, 이것들을 활용하여 전체 문제를 해결하는 방법이라고 할 수 있다.

하지만 부분 문제를 활용하여 전체 문제를 해결했다고 해서 반드시 동적 계획법이 효율적인 것은 아니다.

정의

동적 계획법은 복잡한 문제를 더 작은 하위 문제들로 나누어 해결하고, 그 결과를 저장해두었다가 재사용하는 알고리즘 설계 기법이다.

동적 계획법을 쓸 수 있는 조건

동적 계획법을 효율적으로 활용하려면 아래 두 가지 조건을 만족해야 한다.

  1. 큰 문제를 작은 문제로 나누었을 때 동일한 작은 문제가 반복해서 등장해야 한다.
  2. 큰 문제의 해결책은 작은 문제의 해결책의 합으로 구성할 수 있어야 한다.

동적 계획법의 핵심은 작은 문제들이 같아야 하고 반복되어야 한다.

이 점이 분할 정복과 다르다.

이 반복되는 문제들을 해결하여 합하면 자연스럽게 큰 문제를 해결할 수 있어야 한다.

1. 최적 부분 구조(Optimal Substructure)