개요
DP, 다이나믹 프로그래밍으로 불리는 DP는 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법을 뜻합니다.
DP의 원리
DP를 구현해보기 전, DP가 어떤식으로 이루어져 있는지 DP의 원리를 먼저 알아봅시다.
DP로 해결하기 위한 조건
DP를 사용하여 문제를 해결하기 위해서는 다음과 같은 조건을 만족해야 합니다.
- 큰 문제를 작은 문제로 나눌 수 있어야 한다.
- 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다.
동적 계획법의 가장 대표적인 문제인 피보나치 수열을 예로 들어 설명해봅시다.
// n번 수열은 n-1번 수열과 n-2번 수열의 합이다.
fibo[n] = fibo[n - 1] + fibo[n - 2]피보나치 수열의 공식은 위와 같습니다. n번째 피보나치 수열을 구하는 문제는 n-1번 피보나치 수열과 n-2번 피보나치 수열을 구하는 작은 문제로 나눌 수 있고, 수열의 값은 항상 같기 때문에 동적 계획법으로 풀 수 있습니다. 이 때 수열의 값은 항상 같기 때문에 피보나치 수열은 DP로 풀 수 있습니다.
점화식
점화식이란 수열에서 이웃하는 두 항 사이에 관계를 나타내는 관계식을 나타내는 말로 피보나치 수열의 공식또한 점화식입니다.
DP문제를 해결할 때에는 논리적으로 전체 문제를 나누고, 전체 문제와 부분 문제 간의 인과 관계를 나타내는 점화식을 세우는 능력이 중요합니다.
메모이제이션(Memoization)
DP를 해결하기 위한 핵심적 기술이라고 부를 수 있는 메모이제이션에 대해서 알아봅시다.
우선 5번째 피보나치 수열을 구하는 과정을 살펴봅시다.
5번째 피보나치 수열을 구하기 위해서 피보나치 수열을 구하는 함수 fib()가 총 15번 실행되고, 이 중 fib(3)이 2번, fib(2)가 3번, fib(1)은 5번, fib(0)은 3번 계산되게 됩니다.
즉, 15번의 함수 호출 중 11번은 중복된 함수를 호출하는 셈입니다.
위에 예시에선 비교적 작은 값을 찾아 에게, 15번 밖에 안되는거 아닌가? 라고 생각할 수 있지만, 수가 커지고 중복되는 연산이 많아지게 되면 시간복잡도 측면에서 효율적인 알고리즘이라고 볼 수 없습니다.
만약, 위 사진처럼 피보나치 수열을 구하는 과정에서 이미 계산한 값을 다시 계산하지 않고 이미 계산된 값을 이용한다면 중복된 연산을 제외하여 효율적으로 피보나치 수열을 구할 수 있습니다.
이처럼, 부분 문제를 풀었을 때 이 문제를 DP 테이블에 저장해 놓고 다음에 같은 문제가 나왔을 때 재계산하지 않고 DP테이블의 값을 이용하는 것을 메모이제이션이라고 부릅니다.
DP 구현 방식
이제 DP를 구현해봅시다.
- 탑-다운 방식(Top-Down)
- 바텀-업 방식(Bottom-Up)
DP는 위와 같은 두 가지 방식으로 구현할 수 있습니다.
탑-다운 방식(Top-Down)
탑-다운 방식은말 그대로 위에서부터 문제를 파악해 내려오는 방식으로, 주로 재귀 함수를 이용해 구현합니다.
재귀로 구현하기에 코드의 가독성이 좋고 이해하기가 편합니다.
// 계산한 값을 넣기 위한 배열. 초기에는 모두 -1로 초기화해주어야 한다.
int D[1001] = { -1, };
int fib(int n){
// 기존의 계산한 적이 있는 부분 문제는 다시 계산하지 않고 저장된 값을 반환한다.
if(D[n] != -1){
return D[n];
}
// 메모이제이션 : 구한 값을 바로 반환하지 않고 테이블에 저장 후 반환
D[n] = fib(n - 1) + fib(n - 2);
return D[n];
}바텀-업 방식(Bottom-Up)
바텀-업 방식은 탑-다운과 반대로 가장 작은 부분 문제부터 문제를 해결하면서 점점 큰 문제로 확장해 나가는 방식입니다.
주로 반복문으로 구현합니다.
// 계산한 값을 넣기 위한 배열. 초기값 0,1은 미리 담아준다.
int D[1001] = { 0, 1 };
int fib(int n){
for(int i = 2; i <= n; i++){
D[i] = D[i - 1] + D[i - 2];
}
return D[n];
}탑-다운 vs 바텀-업
두 방식 중 좀 더 안전한 방식은 바텀-업입니다. 탑-다운은 재귀로 구현돼있어 깊이가 깊어질 경우 런타임 에러가 발생할 수 있기 때문입니다.
하지만, 실제 알고리즘 문제 푸는 경우에는 오히려 자신이 구현한 함수에 오류가 있을 확률이 더 높기 때문에 두 방식의 차이점은 거의 없다고 할 수 있습니다.
좀 더 편한 방식이나 문제에 따라 두 방식 중 하나를 쓸 수 있습니다.
