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

(2023-12-27)

동적 계획, 동적 프로그래밍


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

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

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

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


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

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

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

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


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

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


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

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


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

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


6. 동적 계획법의 풀이 구현 방식 종류Memoization (메모이제이션) (하향식 접근 풀이)
  ㅇ Tabulation (상향식 접근 풀이)

알고리즘 전략
   1. 알고리즘 설계   2. Brute Force   3. 분할 정복법   4. 탐욕 알고리즘   5. 동적 계획법  


Copyrightⓒ written by 차재복 (Cha Jae Bok)       기술용어해설후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"