다이나믹 프로그래밍
- 다이나믹 프로그래밍(Dynamic Programming, DP). 다른 말로는 동적 계획법이라고도 한다.
- 큰 문제를 한 번에 해결하기 어려울 때 이를 작은 여러 개의 문제로 나누어서 푸는 기법이다. 일반적으로 부분 문제 반복1과 최적 부분 구조2를 가진 문제를 해결할 때 사용한다.
- 각 하위 문제의 해답을 계산하고 이를 별도의 저장공간에 저장하여 이후 같은 하위 문제가 나오는 경우 재차 계산하지 않고 간단히 해결할 수 있다.
- 최단 경로 탐색, 행렬 제곱 등의 최적화에 사용한다. DP이 문제를 해결하기 위한 모든 방법을 검토하고, 그중 최적의 풀이법을 찾아내기 때문이다.
- 상향식 접근법을 사용한다. 상향식 접근법이란 최하위 해답을 구한 뒤 이를 저장하고, 저장된 결과를 이용해서 상위 문제의 해답을 구하는 방식이다.
- 메모이제이션(Memoization)기법3을 사용한다.
- 문제를 쪼갤 때 각 부분은 서로 중복될 수 있다.
분할 정복
- 문제를 더이상 나누어지지 않을 때까지 나눈 뒤, 풀면서 각 부분을 합병하여 전체 문제의 답을 얻는 기법.
- 하향식 접근법을 사용한다. 하향식 접근법이란 상위 문제의 해답을 구하기 위해서 아래로 내려가며 하위 문제의 해답을 구하는 방식으로, 보통 재귀적으로 구현한다.
- 문제를 잘게 쪼갤 때 각 부분은 서로 중복되지 않는다.
그리디 알고리즘
- DP가 위에서 설명했듯이 문제의 해답을 찾기 위한 모든 방법을 검토하여 비효율적일 수 있다. 이러한 단점을 극복하기 위해 DP대신에 그리디 알고리즘이 등장했다.
- 그리디 알고리즘은 DP와는 달리 항상 최적해를 구하진 않지만 최소 신장 트리 문제 등에서 그리디 알고리즘이 최적해를 구할 수 있다.
- A지점에서 B지점까지 가능한 한 빨리 이동하는 경로를 찾고 싶다고 하자. 이 문제에 DP를 사용한다면 A에서 B로 가는 모든 경로를 비교하여 최적의 경로를 찾아낸다면, 그리디 알고리즘은 전체적인 상황을 고려하지 않고 교차로(선택지)가 보일 때마다 가장 빠른 경로를 검색해서 찾아주는 식이다.
- DP를 사용한다면 모든 경로를 비교하는 과정에서 다소 시간이 걸린다는 단점이 있다. 하지만 그러게 얻어낸 경로가 최적의 경로라는 사실은 보장된다. 반면에 그리디 알고리즘으로 경로를 탐색한다면 DP에 비해 빠르게 경로를 찾을 수 있지만, 그 경로가 최적의 경로라고 보장할 수 없다. 각 구간의 최적의 경로가 전체적인 최적의 경로가 되지 않기 때문.
DP을 이용한 알고리즘
- 최장 공통 부분 수열(Longest common subsequence, LCS)
- 벨만-포드 알고리즘
- 다익스트라 알고리즘
- 플로이드-워셜 알고리즘
- 연쇄 행렬 곱셈(Chain matrix multiplication)
- 배낭 문제(knapsack Problem)
대표적인 DP을 이용한 알고리즘. 이 외에도 많은 알고리즘이 있다.