Memoization과 Tabulation: 다이나믹 프로그래밍(DP)의 두 가지 접근법

다이나믹 프로그래밍은 큰 문제를 작은 문제로 쪼개어 해결하는 방법을 말합니다. 이때, 작은 문제를 풀어나가는 방법에는 Memoization과 Tabulation 방식이 있습니다.

Memoization 방식은 큰 문제를 풀기 위해 필요한 값들을 저장해 두었다가 다시 활용하는 방식으로, Top-down 방식이라고도 부릅니다. Memoization 방식에서는 한 번 계산된 값을 메모이제이션(기록)하여 중복 계산을 방지합니다. 이를 통해 작은 문제를 해결하고, 그 결과를 저장해 놓는 과정에서 dp 배열이 생성됩니다.

Tabulation 방식은 작은 문제부터 큰 문제까지 순차적으로 풀어나가는 방식으로, Bottom-up 방식이라고도 부릅니다. Tabulation 방식에서는 작은 문제의 해결에 필요한 값을 이전 계산 결과로부터 계산해 나가는 것입니다. 이를 통해 dp 배열을 순차적으로 채워나가며, 최종적으로 큰 문제를 해결합니다.

Memoization 방식은 일반적으로 재귀 함수를 이용하여 구현하며, Tabulation 방식은 반복문을 이용하여 구현합니다. 둘 다 dp 배열을 활용하는 것은 동일하지만, 접근 방식에 따라 구현 방법이 달라집니다.

Memoization과 Tabulation 방식 중 어떤 방식을 선택할지는 구현하고자 하는 문제에 따라 달라집니다. Memoization 방식은 필요한 부분만 계산하여 더 빠른 속도를 보이지만, 재귀 함수를 사용하기 때문에 함수 호출 시간이 추가로 소요될 수 있습니다. 반면에 Tabulation 방식은 반복문을 사용하여 dp 배열을 순차적으로 채워나가기 때문에 좀 더 직관적이고 빠른 속도를 보일 수 있습니다.

예를 들어, 피보나치 수열을 구하는 문제를 Memoization 방식으로 풀면 다음과 같습니다.

#include <iostream>
#include <cstring>
using namespace std;

int memo[100];

int fibonacci(int n) {
    if (n <= 1)
        return n;

    if (memo[n] != -1)
        return memo[n];

    return memo[n] = fibonacci(n-1) + fibonacci(n-2);
}

int main() {
    int n = 10;
    memset(memo, -1, sizeof(memo));
    cout << fibonacci(n) << endl;
    return 0;
}

반면에 Tabulation 방식으로 풀면 다음과 같습니다.

#include <iostream>
#include <cstring>
using namespace std;

int dp[100];

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];
    }
    return dp[n];
}

int main() {
    int n = 10;
    cout << fibonacci(n) << endl;
    return 0;
}

두 방식 모두 피보나치 수열을 구하는 문제를 해결하지만, Memoization 방식은 Top-down 방식으로 큰 문제를 작은 문제로 쪼개어 해결하는 반면, Tabulation 방식은 Bottom-up 방식으로 작은 문제부터 큰 문제까지 순차적으로 해결해 나가는 방법입니다.