데이터 구조-동적 프로그래밍

동적 프로그래밍 접근 방식은 문제를 더 작지만 가능한 하위 문제로 나누는 것과 유사합니다. 그러나 분할 및 정복과는 달리 이러한 하위 문제는 독립적으로 해결되지 않습니다. 오히려 이러한 작은 하위 문제의 결과가 기억되고 유사하거나 중복되는 하위 문제에 사용됩니다.

동적 프로그래밍은 문제가있는 경우에 사용되며 유사한 하위 문제로 나누어 결과를 재사용 할 수 있습니다. 대부분 이러한 알고리즘은 최적화에 사용됩니다. 현재의 하위 문제를 해결하기 전에 동적 알고리즘은 이전에 해결 된 하위 문제의 결과를 조사하려고합니다. 최상의 솔루션을 얻기 위해 하위 문제의 솔루션이 결합됩니다.

그래서 우리는 이렇게 말할 수 있습니다.

• 문제는 더 작은 중첩 하위 문제로 나눌 수 있어야합니다.

• 더 작은 하위 문제의 최적 솔루션을 사용하여 최적의 솔루션을 얻을 수 있습니다.

• 동적 알고리즘은 Memoization을 사용합니다.

비교

로컬 최적화가 해결되는 탐욕스러운 알고리즘과 달리 동적 알고리즘은 문제의 전체 최적화에 동기를 부여합니다.

전체 솔루션을 얻기 위해 솔루션을 결합하는 분할 및 정복 알고리즘과 달리 동적 알고리즘은 더 작은 하위 문제의 출력을 사용한 다음 더 큰 하위 문제를 최적화하려고합니다. 동적 알고리즘은 Memoization을 사용하여 이미 해결 된 하위 문제의 출력을 기억합니다.

예

다음 컴퓨터 문제는 동적 프로그래밍 접근 방식을 사용하여 해결할 수 있습니다.

• 피보나치 수열
• 배낭 문제
• 하노이 타워
• Floyd-Warshall의 모든 페어 최단 경로
• Dijkstra의 최단 경로
• 프로젝트 일정

동적 프로그래밍은 하향식 및 상향식 방식으로 사용할 수 있습니다. 물론 대부분의 경우 이전 솔루션 출력을 참조하면 CPU 사이클 측면에서 재 계산하는 것보다 저렴합니다.