동적 계획법(Dynamic Programming)이란? - Bottom-Up 방식: 테뷸레이션

📘 동적 계획법(Dynamic Programming)이란?

해결편: Bottom-Up 방식 (테뷸레이션 Tabulation)

⚠️ 메모이제이션의 구조적 문제

메모이제이션(Memoization)은 재귀 호출 중복을 방지하기 위해 사용됩니다.
한 번 계산한 값을 기록하여,
같은 계산이 들어왔을 때 다시 재귀하지 않고 저장된 값을 반환합니다.

하지만 구조적으로 보면 다음과 같은 흐름을 갖습니다:

F(n) → F(n-1) → F(n-2) → F(n-3) → ... → F(1) → F(0)   
                                                → F(1) → F(2) → ... → F(n) 

• 계산을 시작하기 위해 F(n)을 호출하면
• F(n-1), F(n-2) 등으로 재귀 호출이 분기되며 계속 내려갑니다
• 계산 자체는 F(0)에서 시작되어, 다시 F(n)까지 올라가며 수행됩니다

이 방식은 중복 호출은 줄이지만,
계산 흐름이 내려갔다가 다시 올라오는 복잡한 구조입니다.
우리는 실제로 오른쪽 절반, 즉 F(1)부터 F(n)까지의 순차적인 흐름만 필요합니다.

2025.06.29 - [알고리즘/동적계획법] - 동적계획법(Dynamic Programming)이란? - 메모이제이션

동적계획법(Dynamic Programming)이란? - 메모이제이션

 

💡 Bottom-Up 방식의 핵심 아이디어

(= 테뷸레이션 Tabulation)

✅ 핵심 발상

❗ “우리가 진짜로 원하는 계산 흐름은 이거 하나다.”

→ F(1) → F(2) → ... → F(n)

그런데 메모이제이션은
굳이 F(n)에서 시작해 F(0)까지 내려갔다가,
그제야 위 흐름을 다시 계산합니다.

🧠 그래서 이렇게 사고를 전환합니다:

“처음부터 F(0)과 F(1)을 알고 있으니,
그걸 기반으로 F(2), F(3)… F(n)까지 차례대로 쌓아가면 되는 것 아닌가?”

✔️ 그러면 어떻게 구현할 수 있는가?

1. 계산 결과를 저장할 배열을 준비합니다
2. F(0), F(1)은 초기값으로 직접 넣습니다
3. 그다음 F(2)부터는
   → 저장된 F(i-1), F(i-2)를 참조해서 계산
   → 새로운 결과를 배열에 저장

이렇게 순서대로 쌓아가며 계산하는 방식이 바로
Bottom-Up 방식이며,
동적 계획법에서 이 방식을 전문 용어로 테뷸레이션(Tabulation)이라 부릅니다.

🧰 코드 구현

🔷 기본적인 테뷸레이션 방식

#include <iostream>
using namespace std;

int fib(int n) {
    int dp[100];
    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;
    cin >> n;
    cout << fib(n) << endl;
    return 0;
}

• F(0)과 F(1)을 기반으로
• F(2)부터 F(n)까지 순서대로 계산
• 중간 결과는 배열에 저장, 다음 계산에 활용
• 재귀 없이, 반복문만으로 처리

🔷 공간 최적화된 테뷸레이션

#include <iostream>
using namespace std;

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

    int prev2 = 0;  // F(n-2)
    int prev1 = 1;  // F(n-1)
    int current;

    for (int i = 2; i <= n; ++i) {
        current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }

    return current;
}

int main() {
    int n;
    cin >> n;
    cout << fib(n) << endl;
    return 0;
}

• 배열 없이 변수 2개만 사용
• 공간 복잡도 O(1)
• 동적 계획법의 최적 형태 중 하나

📊 수치 비교

입력값 n	단순 재귀 호출 수	메모이제이션 호출 수	Bottom-Up 반복 횟수
5	15	6	4
10	177	11	9
20	21,891	21	19
30	2,692,537	31	29
40	약 331,160,281	41	39

• Bottom-Up은 호출 자체가 없음
• 반복문만으로 순차 계산
• 중복 없음
• 재귀 스택 없음

✅ 요약 및 마무리

• 메모이제이션(Memoization)은 재귀 구조를 그대로 유지하면서
  계산 결과를 저장하여 중복 계산을 피하는 방식입니다.
  구조적으로는 내려갔다가 올라오는 왕복 흐름을 가집니다.
• Bottom-Up 방식, 또는 테뷸레이션(Tabulation)은
  애초에 우리가 원하는 계산 흐름
  → F(1) → F(2) → ... → F(n)
  만 따라가겠다는 전략입니다.
• 중간 결과를 저장하면서 순서대로 계산을 진행하고,
  재귀 없이 반복문만으로 구현 가능합니다.
• 구조가 더 단순하고, 메모리도 더 효율적이며,
  시간 복잡도도 동일하게 O(n)입니다.

✅ 테뷸레이션은 동적 계획법의 본질을
가장 직관적이고 깔끔하게 구현한 형태입니다.