동적계획법 (Dynamic Programming)

동적계획법(Dynamic Programming)

큰 문제를 작은문제로 나누어 푸는 문제를 일컫는 말

- 복잡한 문제(complex problem)를 작은 문제(sub problems)로 나눔
- 작은 문제의 해는 복잡한 문제를 풀기위한 부분 해가 됨
- 복잡한 문제를 풀기위한 작은 문제들은 자주 등장하기 때문에
  작은 문제가 나타날때 마다 계산할 필요 없이 해를 저장해놨다가
  동일한 문제가 나오면 재 활용하여 시간을 절약

동적프로그래밍으로 풀어야하는 문제는 다음과 같은 2가지 특성을 가짐

- Overlapping Subproblems
- Optimal Substructure

Overlapping Subproblems(겹치는 부분문제) : 중복 하위 문제

- sub-sub problem 간에 중복되는 경우가 여러 번 발생하는 경우
  이것을 매번 계산하지 않고 먼저 계산한 값을 배열이나 해시 테이블에 저장해두었다가 다음번 수행 시 즉시 반환

분할정복 알고리즘처럼  동적 프로그래밍은 하위 문제에 대한 솔루션을 사용(결합, 조합)하는데  
동적 프로그래밍은 주로 동일한 하위 문제의 솔루션이 반복(again and again)해서 필요할 때 사용

하위 문제가 이미 계산 되었다면 다시 계산할 필요가 없도록 테이블에 저장했다가 나중에 다시 사용
따라서 동적 프로그래밍은 공통적인 (겹치는) 하위 문제가 없다면 동적프로그래밍으로 풀면 안됨

두 가지 방법으로 하위문제들(subproblem)의 해를 저장해 놨다가 다시 재활용함
- Memoization
- Tabulation


Memoization

메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때,
이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여
프로그램 실행 속도를 빠르게 하는 기술

동적 계획법의 핵심이 되는 기술
재귀를 이용하며, 탑 다운 (Top-Down), 하향식

Before - After

Tabulation

bottom up 방식은 메모이제이션과 다르게 하위 문제의 모든 해를 조회 테이블의 모든 엔트리에 저장

메모이제이션에서는 하위문제의 수요에 따라 계산되어 저장된다면 테뷸레이션에서는
첫 번째 항목부터 시작하여 모든 항목이 하나씩 가져감

반복문을 이용하며 바텀 업 (Bottom-Up), 상향식

 

Optimal Substructure(문제의 정답을 작은 문제의 부분에서 구할 수 있을 때) : 최적 부분구조

주어진 문제에 대한 최적해를 구하고자 할 때, 좀 더 작은 sub-problem들에 대한 optimal solution들을 찾은 후
그것들을 결합하면 결국 전체 문제의 optimal solution 이 되는 경우이어야 함

Main Problem의 최적해(optimal solution)는 Sub Problem의 최적해들의 집합으로 이루어짐

* 최적 하부 구조
  컴퓨터 과학에서, 문제의 최적 해가 그 하위 문제의 최적 해로부터 얻을 수 있는 경우
  문제에 대한 동적 프로그래밍 및 욕심 알고리즘의 유용성을 결정하는 데 사용
  ex) 최단 경로 문제(shortest path problem)
      노드 x가 소스 노드 u에서 목적지 노드 v까지의 최단 경로에 놓이는 경우
     u에서 v까지의 최단 경로는 u에서 x까지의 최단 경로와 x에서 v까지의 최단 경로의 조합
     Floyd-Warshall 및 Bellman-Ford 와 같은 최단경로 알고리즘이 동적 프로그래밍의 전형적인 예

 

DP가 적용 되는 경우

- 큰 문제들을 작은 문제들로 나눌 수 있는 경우
- 해당 작은 문제들 사이에 중복되는 문제가 존재하여 효율성을 개선할 수 있는 여지가 있는 경우
- 작은 문제들의 최적해의 집합이 큰 문제의 최적해와 일치하는 경우