동적계획법의 의의와 종류, 최적화의 원리, 동적계획모형의 특징, 동적계획법의 유용성과 한계

1. 동적계획법의 의의

동적계획법은 복잡한 문제를 해결하기 위한 강력한 전략으로, 큰 문제를 작은 하위 문제로 나눠 접근하는 방식이다. 이 방법은 문제를 단계별로 분해하여 각 단계의 최적 해를 구하고, 이러한 해들이 다음 단계로 연결되도록 구성하여 전체 문제의 최적 해를 찾아가는 과정을 따른다. 이렇게 단계적으로 접근함으로써 동적계획법은 문제의 구조를 명확히 하고, 중복된 계산을 줄이며, 효율적으로 해결책을 제시할 수 있다. 동적계획법은 주로 최적화 문제에서 사용되며, 그 근본 원리는 최적 부분 구조(optimal substructure)와 중복되는 부분 문제(overlapping subproblems)다. 최적 부분 구조란 전체 문제의 최적 해가 그 하위 문제들의 최적 해로 구성될 수 있음을 의미하며, 중복되는 부분 문제는 동일한 하위 문제를 여러 번 계산할 필요가 없음을 나타낸다. 이러한 특성을 활용하면, 이미 계산된 하위 문제의 결과를 저장하여 나중에 다시 사용할 수 있어 전체 계산량을 획기적으로 줄일 수 있다. 이는 특히 재귀적 방법을 사용할 때 중요한 요소다. 동적계획법의 대표적인 예시는 최대 부분 수열 합 문제, 배낭 문제, 최단 경로 문제와 같은 …