수리 공작소
[알고리즘 기초] 동적 계획법이란? 본문
동적 계획법(Dynamic Programming, DP)이란?
동적 계획(Dynamic Programming, DP)이란 주어진 문제를 작은 부분으로 쪼개어 해결해나가는 방법이다.
이러한 부분에서 분할정복(Divide and Conquer, DC) 비슷하지만 두 가지 대표적인 차이점이 있다.
1. 문제 접근 방식의 차이
DC는 top-down approach이고, DP는 bottom-up approach라는 차이점이 있다.
(물론 DP도 top-down으로 사용될 수 있지만 대체적으로 그렇다고 한다.)
2. DP의 추가적인 메모리 저장
DP는 DC와는 다르게 이전에 계산한 값을 배열(혹은 다른)에 저장을 하여 재활용한다.
이와 같은 방법을 Memoization이라고 한다. 덕분에 이후에 중복 계산을 피하고 시간 복잡도를 줄일 수 있다는 점에서 DC와 차이가 있다.
위의 Memoization의 관점에서 조금 더 생각을 해보면,
DP -> 쪼개어진 문제들을 해결하는 과정에서 반복되는 부분이 많은 경우. 즉, 문제들간의 연관성이 높을 때 활용하면 좋다.
DC -> 위와 반대로 문제들이 서로 독립적인 경우에는 굳이 메모리를 잡아먹는 DP를 활용하지 않고 DC를 사용하면 좋다.
재귀 관계식이란?
DP에서 문제를 해결할 때, "재귀 관계식"이라는 것을 세워야한다.
이는 작은 문제들의 해를 조합하여 큰 문제의 해를 구하는 점화식(Recurrence Equation)을 의미한다.
예)
피보나찌 수열
F(n) = F(n-1) + F(n-2)
와 같은 재귀 관계식을 세울 수 있다.
다음은 동적 계획을 이용한 알고리즘 두가지이다.
1. 이항계수 구하기
2. Floyd 알고리즘 (최단 경로 구하기)