동적프로그래밍(Dynamic Programming, DP) 의 두가지 주요 특성

 

• 중복 부분 문제 (Overlapping Subproblems):
  • 동적 프로그래밍 문제는 동일한 하위 문제를 여러 번 반복해서 푸는 특성이 있습니다. 예를 들어 피보나치 수열에서 F(n) = F(n-1) + F(n-2)와 같은 점화식을 사용할 때, F(n-1)과 F(n-2)를 반복적으로 계산하는 경우가 많습니다.
  • DP에서는 이러한 중복 계산을 **메모이제이션 (Memoization)**이나 탑다운/바텀업 접근법으로 저장해 두고, 동일한 하위 문제가 다시 등장하면 저장된 값을 사용하여 계산을 줄입니다. 이를 통해 시간 복잡도를 줄여 효율성을 높입니다.
• 최적 부분 구조 (Optimal Substructure):
  • 최적 부분 구조란 문제를 작은 하위 문제들로 나누어 해결할 수 있고, 각 하위 문제의 최적해를 결합하여 전체 문제의 최적해를 구성할 수 있는 특성입니다. 다시 말해, 전체 문제를 해결하는 최적의 해답이 하위 문제들의 최적해로 이루어져 있다는 것입니다.
  • 예를 들어, 최단 경로 문제에서는 특정 노드까지의 최단 경로가 그 이전 경로들의 최단 경로들로 이루어져 있습니다.