Dynamic Programming
동적 계획법은 최적화 이론의 한 기술이며, 특정 범위까지의 값을 구하기 위해서 다른 범위까지의 값을 이용 해서 효율적으로 답을 구하는 알고리즘 설계기법이다.
Dynamic Programming이란 Divide and Conquer와 동일하게 문제를 작은 단위로 나누어 풀고 결합하여 답을 찾는다. 하지만 Dynamic Programming은 각각의 Subproblem의 답을 저장하여 중복되는 문제를 한번만 풀도록하기 때문에 최적화된 방법으로 문제를 풀 수 있도록 도와준다.
- DP와 D&C의 차이점 : D&C는 하위문제가 서로 독립적인 반면, DP는 하위문제의 중복이 발생하는 경우 사용한다.
Dynamic Programming의 조건
- Optimal Substructure : Subproblem의 답은 상위문제에서도 동일하다
- Overlapping Subproblems : 중복되는 Subproblem이 존재한다
위의 두 조건을 만족하는 경우 Dynamic Programming을 사용하여 최적화할 수 있다.
Dynamic Programming의 설계
- 최적해의 구조를 찾는다
- 최적해의 값을 재귀적으로 구할 수 있도록 정의한다(점화식)
- 최적해의 값을 작은 문제에서 큰 문제 순으로 구한다
- 이전에 구한 문제의 최적값을 이용한다
Dynamic Programming은 Subproblem이 전체 문제와 크기가 비슷할 때(N -> N-1 -> N-2 ..., D&C가 비효율적일 때), 혹은 Subproblem에 중복이 발생할 때 유리하다.
Dynamic Programming의 구현
- Top-down : Memorization. 문제를 Subproblem으로 나누면서 재귀적으로 문제를 해결하고, 그 결과를 기록하여 사용한다.
- 재귀함수
- Bottom-up : Tabulation. Subproblem을 먼저 해결하고 table에 저장한 뒤, 상위 문제를 table에 저장된 값을 이용하여 해결한다.
- 반복문
Dynamic Programming의 장단점
- 장점
- 필요한 모든 가능성을 고려하여 구현하므로 항상 최적의 결과를 얻을 수 있다
- 메모리에 저장된 값을 사용하므로 빠른 속도로 최적의 해를 찾아낼 수 있다
- 단점
- 모든 가능성을 고려하지 못하면 최적의 결과를 보장할 수 없다
- 다른 알고리즘에 비해 많은 메모리 공간을 요구한다
Dynamic Programming의 종류
- 피보나치 수열
- 이항계수
- 최장 공통부분 수열(LSC) : 두 개의 수열에서 가장 길게 겹치는 부분수열을 찾음
- 0/1 Knapsack : 조합 최적화. 한정된 무게를 담을 수 있는 배낭에 담을 수 있는 최대가치의 물건조합을 찾음
- 부분집합 합 : 집합의 원소의 합이 특정값이 되는지 판단
- 연쇄행렬 곱셈 : 주어진 연쇄행렬의 곱셈횟수를 최소로 할 수 있는 행렬곱셈의 순서를 찾음
- 최단거리
- Bellman-Ford : 한 노드에서 다른 노드까지의 최단거리를 구하는 알고리즘
- Floyd-Warshall : 그래프에서 가능한 모든 노드쌍에 대해 최단거리를 구하는 알고리즘
