Dynamic Programming   동적 계획법, 다이내믹 프로그래밍

1. 동적 계획법 (Dynamic Programming, 다이내믹 프로그래밍) 전략

  ㅇ 중첩된 부 문제들을 갖는 복잡한 문제를 해결하는 최적화 기법
     - 주로, 아래에서 위로 해결하면서, 전체 문제를 해결하는, 상향식 접근 방식을 취함

  ※ 동적 계획 용어 고안  :  1953년 리처드 벨먼 (Richard Ernest Bellman, 1920~1984)
     - 미국의 응용수학자

  ※ 분할 정복, 동적 계획 방법 간의 비교
     - 분할 정복 : 분할된 부 문제들이 서로 독립적임
     - 동적 계획 : 분할된 부 문제들이 서로 의존적임


2. 동적 계획법의 적용 대상

  ㅇ 주어진 문제가,
     - 최적 부분 구조 (Optimal Substructure)를 갖고,
     - 부 문제들이 중첩되는 (Overlapping Subproblem) 정도가 높을 때, 유용함

  ㅇ 최적성의 원리
     - 주어진 문제에 대한 최적해가 소문제에 대한 최적해들로 구성된다는 원리

  ㅇ 例) 
     - 피보나치 수열
     - 최소값/최대값을 구하는 최적화 문제
     - 최단경로 알고리즘 (플로이드 알고리즘, 벨만 포드 알고리즘)
        . 어떤 최단 경로 내 각각의 부분 경로들도 최단 경로이어야 됨


3. 동적 계획법의 풀이 방식 개요

  ㅇ 간단한 하위 문제부터 해결하면서,
  ㅇ 하위 문제의 해를 테이블에 저장해 놓고,
  ㅇ 이를 이용하여, 좀더 복잡한 상위 문제를 해결하여 나아감


4. 동적 계획법의 풀이 방식 요점

  ㅇ 재귀 관계식을 세워, 입력 사례를 더 작은 입력 사례로 분할 함
     - 단, 통상적인 재귀 접근과는 달리, 상향식 임
        . 즉, 하위 문제를 풀고, 이들 해들을 결합시키면서, 전체 해를 구함 

  ㅇ 주로, 크기별로 모든 문제들을 미리 풀어놓고, 이를 찾아 재사용하게 됨
     - 즉, 각 부 문제의 해답을 1회 만 풀어 저장하고,
     - 나중에 동일한 부 문제의 해답이 요구될 때, 이렇게 저장된 해답을 찾아서 해결함


5. 동적 계획법의 주요 특징

  ㅇ 분할된 부 문제들이 서로 독립일 필요는 없음
  ㅇ 특히, 주어진 문제가 재사용 가능한 여러 중복된 부 문제들로 중첩되면, 적합함


6. 동적 계획법의 풀이 구현 방식 종류

  ㅇ Memoization (메모이제이션) (하향식 접근 풀이)
  ㅇ Tabulation (상향식 접근 풀이)