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

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

🧠 해결편: 메모이제이션

🔍 재귀의 문제

📌 문제 구조: 계산이 반복된다

피보나치 수열을 재귀적으로 구현하면 코드가 다음과 같습니다.

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

이 코드만 보면 단순하고 깔끔합니다.
하지만 fib(n)을 계산하기 위해 fib(n-1)과 fib(n-2)를 호출하고,
그 둘도 또 각각 재귀로 내려가기 때문에,
같은 계산이 여러 번 반복됩니다.

🔎 구조적으로 어떤 일이 일어나는가?

예를 들어 fib(5)를 호출하면 다음과 같은 구조가 생깁니다.

fib(5)
├─ fib(4)
│  ├─ fib(3)
│  │  ├─ fib(2)
│  │  │  ├─ fib(1)
│  │  │  └─ fib(0)
│  │  └─ fib(1)
│  └─ fib(2)
└─ fib(3)
   ├─ fib(2)
   └─ fib(1)

여기서 보이는 문제점은 명확합니다:

• fib(2)는 총 3번
• fib(3)은 총 2번 호출됩니다

이 말은,
한 번 계산했던 결과를 다시 계산하고 있다는 뜻입니다.
문제는 이 중복이 단지 5까지에서 끝나는 게 아니라,
입력이 커질수록 기하급수적으로 중복 호출이 증가한다는 것입니다.

예를 들어 fib(40)을 재귀로 계산하면 fib(1)만 수천만 번 호출됩니다.
이 문제를 그대로 두면, 시간 복잡도는 O(2ⁿ)입니다.

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

동적계획법(Dynamic Programming)이란? 문제편

💡 메모이제이션: 중복 계산을 막는 전략

🎯 해결하고 싶은 건 단 하나입니다:

“같은 계산을 두 번 하지 않도록 만드는 것”

그러면 어떻게 해야 같은 계산을 막을 수 있을까요?

🧭 인간적인 사고의 흐름에서 출발

• ❓ 어떤 계산을 다시 하지 않으려면,
  → 그 계산을 이미 한 적이 있는지를 먼저 알아야 합니다.
• ✅ 즉, 한 번이라도 계산했다는 사실을 기억해야 중복을 피할 수 있습니다.
• ▶ “한 번 계산한 결과를 기억하고,
  다음에 같은 계산이 들어왔을 때 기억한 값을 그대로 쓰면 되겠다.”
• 💡 이 기억을 실제로 구현하려면,
  → 계산한 결과를 어딘가에 기록해두는 구조가 필요합니다.

📘 이 전략을 정리하면 이렇게 됩니다:

• “이미 계산했다면 다시 계산하지 말자”는 조건을 걸고,
• 그 조건을 확인하려면 “이전에 계산했는지 알 수 있도록 기록”해야 합니다.
• 이 구조 전체를 기억(Memo)을 코드화하는 것이기 때문에,
  → 메모이제이션(Memoization)이라는 이름이 붙습니다.

🧱 다이어그램으로 보는 변화

❌ 중복이 있는 원래 구조

fib(5)
├─ fib(4)
│  ├─ fib(3)
│  │  ├─ fib(2)
│  │  │  ├─ fib(1)
│  │  │  └─ fib(0)
│  │  └─ fib(1)
│  └─ fib(2)
└─ fib(3)
   ├─ fib(2)
   └─ fib(1)

→ 계산한 결과를 기억하지 않기 때문에, 같은 호출이 계속 반복됩니다.

✅ 메모이제이션 적용 구조

fib(5)
├─ fib(4)
│  ├─ fib(3)
│  │  ├─ fib(2)
│  │  │  ├─ fib(1)
│  │  │  └─ fib(0)
│  │  └─ [memo[1]]
│  └─ [memo[2]]
└─ [memo[3]]

→ [] 표시된 부분은 더 이상 재귀 호출하지 않고,
이미 저장해 둔 값을 사용하는 곳입니다.
중복 호출이 사라지면서 성능이 급격히 향상됩니다.

🧰 코드로 보는 해결

각 단계마다 전체 코드를 반복해서 보여주며,
무엇이 왜 추가되었는지 설명합니다.
▶ 아이콘으로 흐름을 따라갑니다.

🔷 1단계: 기본 재귀 구조

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

▶ 문제: 같은 계산이 반복됩니다.
▶ 예: fib(2) → 여러 번 계산됨.
▶ 해결 필요.

🔷 2단계: 저장 공간 준비

int memo[100];  // ▶ 계산 결과를 저장할 배열 추가

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

▶ 아직 아무 기능 없음.
▶ 다만, 계산한 값을 기록할 공간은 마련함.
▶ 다음 단계에서 이 배열을 활용.

🔷 3단계: 계산된 적 있는지 확인

int memo[100];

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

    if (memo[n] != -1)          // ▶ 이미 계산된 경우
        return memo[n];         // ▶ 저장된 값 사용, 재귀 중단

    return fib(n - 1) + fib(n - 2);
}

▶ 조건 추가: “이미 계산된 값이 있는가?”
▶ 조건이 만족되면 재귀를 피함.
▶ 하지만 아직 저장 기능이 없음. 항상 -1이라서 항상 계산함.

🔷 4단계: 계산 결과를 저장

int memo[100];

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

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

    memo[n] = fib(n - 1) + fib(n - 2);  // ▶ 계산 결과 저장
    return memo[n];                    // ▶ 저장된 값을 반환
}

▶ 이제 재귀로 계산한 값을 기록합니다.
▶ 그리고 그 값을 다음부터 그대로 사용함.

🔷 5단계: 전체 구조 + 초기화

#include <iostream>
using namespace std;

int memo[100];

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

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

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

int main() {
    for (int i = 0; i < 100; ++i)
        memo[i] = -1;  // ▶ 계산 전 값은 -1로 초기화

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

▶ 이제 모든 흐름이 완성됨.
▶ fib(n)은 최대 한 번만 계산됨.
▶ 이후 호출은 저장된 값을 즉시 반환.

📊 계산량 비교

입력값 n	단순 재귀 호출 수	메모이제이션 호출 수
5	15	6
10	177	11
20	21,891	21
30	2,692,537	31
40	약 331,160,281	41

• 메모이제이션은 최대 n+1번만 함수 호출
• 계산 결과를 저장한 덕분에 중복 계산이 완전히 제거됨
• 시간 복잡도는 O(n)으로 감소

🧾 정리

• 재귀의 가장 큰 문제는 중복 계산입니다.
• 이 문제는 “이미 계산된 건 다시 하지 말자”는 조건 하나로 해결할 수 있습니다.
• 하지만 그 조건을 만들기 위해선 기억이 필요합니다.
• 바로 그 기억을 코드에 구조로 담은 것이 메모이제이션입니다.
• 메모이제이션은 시간 복잡도를 O(2ⁿ)에서 O(n)으로 줄입니다.