Sanjoy Dasgupta가 저술한 책인 Algorithms과 이기창님의 블로그를 참고하였다.
1. Dynamic Programming(DP)
계산결과를 저장해두었다가 재활용하는 기법. 즉, 하나의 문제를 단 한 번만 풀도록 하는 알고리즘이다. 주로 큰 문제를 작은 문제로 나누어 푸는 문제에 사용된다.
DP의 두 가지 특징은 다음과 같다.
- Optimal Substructure : 부분문제의 최적해를 이용해 전체문제의 최적해를 구할 수 있는 구조
- Overlapping Subproblem : 큰 문제를 작은 문제로 쪼갤 수 있고, 큰 문제와 작은 문제를 같은 방법으로 풀 수 있는 것(이미 풀었던 문제를 여러 번 푸는 것)
여기서 Optimal Substuructure는 앞서 배운 Greedy Algorithm과 최단경로 알고리즘의 조건 중 하나이기도 하다.
2. Dynamic Programming의 종류
-
LIS(Longest Increasing Subsequence. 최장증가순열)
수열의 부분수열을 구성할 때, 증가하는 순서대로 숫자를 고르면서 부분수열의 길이가 최대인 수열을 구하는 알고리즘
-
문자열간의 유사도를 알아내는 알고리즘
-
일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 배낭의 용량을 넘지 않는 선에서 짐들의 가치의 합이 최대가 되도록 짐을 고르는 문제
-
Chain matrix multiplication(연쇄행렬곱셈)
두 개 이상의 행렬을 곱할 때 결합법칙에 따라 최소곱셈 횟수를 구하는 문제
-
TSP(Traveling Salesman Problem. 외판원 문제)
시작점에서 출발해 모든 도시들을 한번 씩 방문하여 다시 돌아오는 데까지 걸리는 최단 시간을 구하는 문제
-
Independent sets in trees(독립집합)
가장 큰 독립집합(트리에서 서로 인접하지 않은(간선이 없는) 정점들의 집합)을 찾는 문제
-
Floyd-Warshall Algorithm(플로이드-와샬 알고리즘)
다익스트라, 벨만-포드와 함께 최단 경로를 구하는 알고리즘 중 하나. 정점 $i$부터 $j$까지의 경로에서 새로운 정점 $k$가 중간에 포함될 때 경로가 더 짧아지는지 아닌지를 판단한다.
3. Dynamic Programming 기타 설명
이전에 배운 것들이랑 헷갈리니까 다시 한 번 짚고 넘어가자.(장문 주의)
cf) DP와 Greedy Algorithm
먼저 그리디 알고리즘은 각 부분 문제의 최적해를 찾아가며 최종적으로 전체 최적해에 도달하는 기법이다. 따라서 당연히 부분문제의 최적해가 전체문제의 최적해가 되어야하므로 Optimal Substuructure 조건이 필요한 것이다. 이와는 다르게, DP는 부분문제의 결과를 저장해두었다가 부분문제가 사용되는 전체 문제에 이 값을 재활용하는 것이다. 따라서 당연히 부분문제의 최적해가 전체문제의 최적해가 되어야하므로 Optimal Substructure 특징이 필요하고, 또 이 큰 문제가 부분문제로 쪼개질 수 있고 같은 방법으로 풀 수 있어야 하므로 Overlapping Subproblem 특징이 필요하다.
cf) DP와 Divide & Conquer Algorithm
DP와 분할정복 모두 부분 문제의 최적해가 전체의 최적해가 될 수 있다는 점에서 같은 특성을 갖고 있다. 하지만 이 부분문제의 의존성에서 차이가 발생한다. 예를 들어, 분할 정복 알고리즘 중 하나인 Merge Sort는 부분 문제를 merge할 때 다른 부분 문제에 의존하지 않는다. 하지만 DP 중 하나인 피보나치 수열은 부분문제끼리 의존성이 있다(이전 값과 이전 전 값의 합이 현재 값이므로 현재 값이 이전 값(부분문제)에 영향을 받음).
따라서 이미 푼 부분문제를 다른 부분문제에서 다시 풀 필요가 없고, 저장되어 있는 계산 결과를 가져다 쓰면 되므로 DP가 효율적인 알고리즘이라고 평가받는 것이다(만약 피보나치 수열을 Brute Force 방식으로 무식하게 풀면 지수 시간 복잡도가 발생하여 매우 오랜 시간이 걸린다). 분할정복은 단지 큰 문제를 원-큐로 해결하기 어려워서 짜잘짜잘하게 쪼개서 나눠 푸는 것 뿐이다. 오해하지 말자!