동적 프로그래밍은 문제를 더 작지만 가능한 더 작은 하위 문제로 나눕니다. 이러한 하위 문제는 독립적으로 해결되지 않습니다. 오히려 이러한 작은 하위 문제의 결과는 유사하거나 겹치는 하위 문제에 대해 기억되고 사용됩니다.
동적 프로그래밍은 문제가 있는 곳에서 사용되며 유사한 하위 문제로 나누어 결과를 재사용할 수 있습니다. 대부분 이러한 알고리즘은 최적화에 사용됩니다. 내재된 하위 문제를 해결하기 전에 동적 알고리즘은 이전에 해결된 하위 문제의 결과를 조사하려고 시도합니다. 하위 문제의 솔루션을 결합하여 최상의 솔루션을 얻습니다.
동적 프로그래밍을 사용하는 문제의 경우
- 문제는 더 작은 중첩 하위 문제로 나눌 수 있어야 합니다.
- 최적의 솔루션은 더 작은 하위 문제의 최적 솔루션을 사용하여 얻을 수 있습니다.
- 동적 알고리즘은 암기를 사용합니다.
동적 프로그래밍 문제는 2가지 접근 방식을 사용하여 해결할 수 있습니다. -
-
상향식 동적 프로그래밍:이 접근 방식에서는 먼저 문제를 분석하고 하위 문제가 해결되는 순서를 확인합니다. 우리는 사소한 하위 문제를 해결하는 것으로 시작하여 주어진 문제를 향해 쌓아갑니다.
-
하향식 동적 프로그래밍:이 접근 방식에서는 주어진 문제를 분해하여 해결하기 시작합니다. 주어진 하위 문제가 이미 해결된 것으로 보이면 저장된 솔루션을 반환하기만 하면 됩니다.