Dynamic Programming
정의
- 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법
원리
- 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달
- 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결
예제
- 막대기 자르기 ( 막대기를 적절히 잘라서 가장 가격이 높게 만들어야 함)
1 | 길이(i) 0 1 2 3 4 5 6 7 8 9 10 |
- 길이가 4인 막대기로 자를 때 얻을 수 있는 최대 가격 : 길이 2인 막대기 두 개로 자름. -> 5 + 5 = 10
- 길이가 6인 막대기 : 자르지 않고 그대로
- 길이가 n인 막대기의 최대 가격 = Rn = max(Pi + Rn-i) (i는 1부터 n)
- R1 = max(P1 + R0) =1
- R2 = max(P1 + R1, P2 + R0) = 5
- R3 = max(P1 + R2, P2 + R1, P3 + R0) = 8
- R4 = max(P1 + R3, P2 + R2, P3 + R1) = 10
–> R1, R2, R3… 가 반복적으로 나옴 . 메모제이션 사용. 이전에 계산한 값들 저장.
단점
- 모든 방법을 일일이 검토하여 그 중 최적해를 찾아내는 주먹구구식 방법
장점
- 문제가 가능한 모든 방법을 충분히 빠른 속도로 처리할 수 있는 경우, 동적 계획법은 최적의 해법
- 계산 횟수를 줄임
- 하위 문제의 수가 기하급수적으로 증가할 때 유용
그리디 알고리즘과 비교
ex) A라는 지점에서 B라는 지점까지 가능한 빨리 이동하는 경로를 찾기”
- 그리디 : 전체적인 상황을 고려하지 않고, 순간순간 교차로가 보일 때마다 가장 빠른 경로를 검색
즉효성이 있음, but 항상 최적의 경로를 찾아주지는 않음 (각 구간마다는 최적경로O, 전체적으로는 최적 경로X)
- DP : 갈 수 있는 모든 상황과 교통 정체를 전부 감안하여 최적의 경로 찾음
약간의 시간 소요, but 가장 빠른 길이 된다고 장담