Dynamic Programming (DP)
동적 프로그래밍
- 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있는 구조에 적용할 수 있는 알고리즘을 통칭하는 말이다.
- 특히 이러한 "작은 문제의 해답"을 Optimal Substructure(최적 부분 구조)라 부른다.
- DP에서는 이러한 Optimal Substructure를 재귀적으로 해결하되,
중복된 연산을 최소화하여 효율적으로 해결하는 것이 관건이다.
※ 즉, 어떤 문제가 Optimal Substructure를 가지고 있되, 이를 단순한 재귀로 해결했을 때 큰 비효율이 발생한다면,
동적 프로그래밍을 적용해 볼 수 있다.
* 이렇게 DP에서 중복된 재귀 호출을 피하는 것을 Memoization(메모하기)라 부른다.
이는 Top-Down Approach에 해당되는 기법이다.
("Memorization"이 아니다.)
* "동적 프로그래밍"이란 용어의 의미
"'동적(Dynamic)'이란 용어는 '정적(Static)'이란 용어의 대비로서는 그럴듯하지만,
이 기법의 내용을 놓고 보면 영어든 한국어든 별로 어울리지 않고 직관적인 이해에도 도움이 되지 않는다.
그래도 역사적으로 그렇게 정착되었으므로 이 이름을 쓸 수 밖에 없다."
(서울대학교 컴퓨터공학부 문병로 교수)
- 즉, 용어가 이렇게 굳어져 내려왔으니, 그냥 사용하도록 하자
DP Examples (동적 프로그래밍 적용 예시)
* Fibonacci Sequence (피보나치 수열) (URL)
* Matrix Path Problem (행렬 경로 문제) (URL)
* Stone Placement Problem (돌 놓기 문제) (URL)
* Matrix-Chain Multiplication Problem (행렬 곱셈 순서 문제) (URL)
* Longest Common Subsequence Problem (최장 공통 부분 순서 문제) (URL)
* Optimal Binary Search Tree (최적 이진 검색 트리) (URL)
* Coin Exchange Problem (동전 교환 문제) (URL)
[All-Pairs Shortest Path; 모든 쌍 최단 경로]
* Floyd-Warshall Algorithm (플로이드-워샬 알고리즘) (URL)
* Johnson's Algrithm (존슨 알고리즘) (URL)
- 존재하는 모든 (시작 정점, 도착 정점) Pair에 대한, \(n(n-1)\)개의 최단 경로를 계산해내는 알고리즘들이다.
- 한 시작 정점에 대해, 다른 모든 정점들로 향한, \(n-1\)개의 최단 경로를 계산해내는 알고리즘들이다.
- 이들 알고리즘에서는 임의의 두 정점 간 경로가 존재하지 않으면, 이 경로의 길이는 \(\infty\)로 정의하며,
두 정점을 직접 연결하는 간선이 없는 경우, 가중치가 \(\infty\)인 간선이 있다 간주한다.
Reference: Introduction to Algorithms 3E (CLRS)
(Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 저, MIT Press, 2018)
Reference: 쉽게 배우는 알고리즘
(문병로 저, 한빛아카데미, 2018)
