다이나믹 프로그래밍 문제를 푸는 방법으로는 크게 두 가지, Top-down 방식
과 Bottom-up 방식
이 있다. 이 두 방식은 어떠한 차이점이 있는지 피보나치 숫자의 예시와 함께 알아보자.
우리말로 '하향식'이라고도 한다. 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식이다.
설명에서도 알 수 있듯이, 보통 재귀 호출을 통해 답을 구한다.
함수 호출의 횟수를 줄이기 위해 메모이제이션 기법
이 사용된다.
컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다. 메모아이제이션이라고도 한다.
출처: 위키백과
int fibonacci(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
if (dp[n] != -1) return dp[n];
dp[n] = fibonacci(n - 1) + fibonacci(n - 2);
return dp[n];
}
여기서 dp[n]
에 피보나치 수열의 값을 저장함으로써 메모이제이션 기법을 사용하였다.
우리말로 '상향식'이라고도 한다. 가장 작은 문제들부터 답을 찾아 가면서 마지막에는 전체 문제의 답을 구하는 방식이다.
보통 반복문을 이용해 구현하게 된다. 재귀 호출을 하지 않으므로 시간과 메모리의 사용량이 상대적으로 적다는 이점이 있다.
int fibonacci(int n) {
dp[0] = 0, dp[1] = 1;
for (int i = 2; i <= n; i++)
dp[i] = dp[i - 1] + dp[i - 2];
}
보다시피 반복문을 사용해 구현하였다.
다이나믹 프로그래밍 문제를 풀 때는 이 두 방식 중 '어느 것이 더 낫다'고 콕 집어서 말하기가 힘든 것 같다. 문제들 중에는 두 방식의 구현 난이도가 굉장히 다른 경우가 존재하기도 한다. 따라서 두 방식 모두를 잘 숙지하고 있어야 하겠다.