동적 프로그래밍 - 헤매다가 힘들어서 만든 개발 블로그

메모이제이션(Memoization)과 타뷸레이션(Tabulation)

재귀의 문제점

재귀를 이용한 분할 정복으로 많은 문제를 해결했다. 하지만 재귀는 콜스택을 차지하는 것 외에도 성능에 크게 영향을 미치는 치명적인 단점이 있다. 바로 중복 계산이다.

피보나치 수열로 보는 재귀의 비효율성

피보나치 수열이란 다음과 같은 규칙으로 만들어진다

F(0) = 0
F(1) = 1
F(n) = F(n-2) + F(n-1)  (n ≥ 2)

수열: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233...

재귀로 구현하기

public class FibonacciBasic {
    
    /**
     * 기본 재귀 방식의 피보나치 수열
     * @param n 구하려는 피보나치 수열의 위치
     * @return n번째 피보나치 수
     */
    public static int fibonacci(int n) {
        // 기저 조건
        if (n == 0 || n == 1) {
            return n;
        }
        
        // 재귀 호출
        return fibonacci(n - 2) + fibonacci(n - 1);
    }
    
    public static void main(String[] args) {
        System.out.println("fibonacci(5) = " + fibonacci(5));  // 5
        System.out.println("fibonacci(10) = " + fibonacci(10)); // 55
    }
}

/*
실행 결과

fibonacci(5) = 5
fibonacci(10) = 55
*/

재귀 호출 트리: 중복 계산의 실체

═══════════════════════════════════════════════════
fibonacci(5) 호출 트리
═══════════════════════════════════════════════════

                    fib(5)
                   /      \
                  /        \
              fib(3)      fib(4)
              /    \      /    \
             /      \    /      \
         fib(1)  fib(2) fib(2) fib(3)
                 /   \   /   \   /   \
              fib(0) fib(1) fib(0) fib(1) fib(1) fib(2)
                                            /   \
                                        fib(0) fib(1)

═══════════════════════════════════════════════════
함수 호출 횟수 분석
═══════════════════════════════════════════════════

fib(0): 3번 호출 !! 
fib(1): 5번 호출 !!!!!
fib(2): 3번 호출 !!!
fib(3): 2번 호출 !!
fib(4): 1번 호출 !
fib(5): 1번 호출 !

총 15번의 함수 호출!
실제 필요한 고유 계산: 6번 (fib(0) ~ fib(5))
중복 계산: 9번 (60%가 중복)

단계별 실행 과정

═══════════════════════════════════════════════════
Step 1: fibonacci(5) 호출
═══════════════════════════════════════════════════

fibonacci(5)
├─ fibonacci(3) 계산 필요
└─ fibonacci(4) 계산 필요

═══════════════════════════════════════════════════
Step 2: fibonacci(3) 먼저 계산 (왼쪽 우선)
═══════════════════════════════════════════════════

fibonacci(3)
├─ fibonacci(1) → return 1 ✓
└─ fibonacci(2)
   ├─ fibonacci(0) → return 0 ✓
   └─ fibonacci(1) → return 1 ✓
   → fibonacci(2) = 0 + 1 = 1 ✓

→ fibonacci(3) = 1 + 1 = 2 ✓

═══════════════════════════════════════════════════
Step 3: fibonacci(4) 계산
═══════════════════════════════════════════════════

fibonacci(4)
├─ fibonacci(2) 🔴 중복
│  ├─ fibonacci(0) → return 0 🔴
│  └─ fibonacci(1) → return 1 🔴
│  → fibonacci(2) = 1 🔴
│
└─ fibonacci(3) 🔴 중복
   ├─ fibonacci(1) → return 1 🔴
   └─ fibonacci(2) 🔴 중복
      ├─ fibonacci(0) → return 0 🔴
      └─ fibonacci(1) → return 1 🔴
      → fibonacci(2) = 1 🔴
   → fibonacci(3) = 2 🔴

→ fibonacci(4) = 1 + 2 = 3 ✓

═══════════════════════════════════════════════════
Step 4: 최종 결과
═══════════════════════════════════════════════════

fibonacci(5) = fibonacci(3) + fibonacci(4)
             = 2 + 3
             = 5 ✓

하지만... 이미 계산한 값들을 반복 계산

시간 복잡도

기본 재귀의 시간 복잡도: O(2^n)

n = 5:  15번 호출
n = 10: 177번 호출
n = 20: 21,891번 호출
n = 30: 2,692,537번 호출
n = 40: 331,160,281번 호출

지수적으로 증가

메모이제이션 (Memoization)

메모이제이션이란 이미 계산한 결과를 저장해두고 재사용하는 것으로 하향식(Top-Down) 접근 방식으로, 계산 결과를 해시 테이블에 저장하여 중복 계산을 방지한다.

메모이제이션 구현

import java.util.*;

public class FibonacciMemoization {
    
    /**
     * 메모이제이션을 사용한 피보나치 수열
     * @param n 구하려는 피보나치 수열의 위치
     * @param memo 계산 결과를 저장하는 해시맵
     * @return n번째 피보나치 수
     */
    public static int fibonacci(int n, Map<Integer, Integer> memo) {
        // 기저 조건
        if (n == 0 || n == 1) {
            return n;
        }
        
        // 이미 계산된 값이 있는지 확인
        if (!memo.containsKey(n)) {
            // 계산되지 않았다면 계산하고 저장
            int result = fibonacci(n - 2, memo) + fibonacci(n - 1, memo);
            memo.put(n, result);
        }
        
        // 저장된 값 반환
        return memo.get(n);
    }
    
    // 편의를 위한 오버로드 메서드
    public static int fibonacci(int n) {
        return fibonacci(n, new HashMap<>());
    }
    
    public static void main(String[] args) {
        // 성능 테스트
        long startTime, endTime;
        
        System.out.println("=== 메모이제이션 피보나치 ===");
        startTime = System.nanoTime();
        int result = fibonacci(40);
        endTime = System.nanoTime();
        
        System.out.println("fibonacci(40) = " + result);
        System.out.println("실행 시간: " + (endTime - startTime) / 1_000_000.0 + "ms");
    }
}

/*
실행 결과

=== 메모이제이션 피보나치 ===
fibonacci(40) = 102334155
실행 시간: 0.050208ms
*/

메모이제이션 동작 과정

═══════════════════════════════════════════════════
fibonacci(5) with Memoization
═══════════════════════════════════════════════════

초기 상태: memo = {}

Step 1: fibonacci(5) 호출
├─ memo에 5 없음
├─ fibonacci(3) 계산 필요
│
│  Step 1-1: fibonacci(3) 호출
│  ├─ memo에 3 없음
│  ├─ fibonacci(1) → return 1 ✓
│  ├─ fibonacci(2) 계산 필요
│  │
│  │  Step 1-1-1: fibonacci(2) 호출
│  │  ├─ memo에 2 없음
│  │  ├─ fibonacci(0) → return 0 ✓
│  │  ├─ fibonacci(1) → return 1 ✓
│  │  └─ memo[2] = 1 저장
│  │
│  └─ memo[3] = 1 + 1 = 2 저장
│
├─ fibonacci(4) 계산 필요
│
│  Step 1-2: fibonacci(4) 호출
│  ├─ memo에 4 없음
│  ├─ fibonacci(2) → memo[2] 사용! 1 반환 (중복 계산 방지)
│  ├─ fibonacci(3) → memo[3] 사용! 2 반환 (중복 계산 방지)
│  └─ memo[4] = 1 + 2 = 3 저장
│
└─ memo[5] = 2 + 3 = 5 저장

최종 memo = {2:1, 3:2, 4:3, 5:5}

═══════════════════════════════════════════════════
결과 비교
═══════════════════════════════════════════════════

기본 재귀: 15번 함수 호출
메모이제이션: 9번 함수 호출 (40% 감소)

더 중요한 것은...
기본 재귀 fibonacci(40): ~1,000ms
메모이제이션 fibonacci(40): ~1ms
→ 1000배 빠름

타뷸레이션 (Tabulation)

타뷸레이션이란 작은 문제부터 차근차근 풀어서 테이블을 채우는 방식으로 상향식(Bottom-Up) 접근 방식으로, 재귀 없이 반복문을 사용하여 작은 문제부터 순서대로 해결한다

타뷸레이션 구현

public class FibonacciTabulation {
    
    /**
     * 타뷸레이션을 사용한 피보나치 수열
     * @param n 구하려는 피보나치 수열의 위치
     * @return n번째 피보나치 수
     */
    public static int fibonacci(int n) {
        // 기저 조건
        if (n <= 1) {
            return n;
        }
        
        // 계산 결과를 저장할 테이블 생성
        int[] table = new int[n + 1];
        
        // 초기값 설정
        table[0] = 0;
        table[1] = 1;
        
        // 상향식으로 테이블 채우기
        for (int i = 2; i <= n; i++) {
            table[i] = table[i - 2] + table[i - 1];
        }
        
        // 최종 결과 반환
        return table[n];
    }
    
    public static void main(String[] args) {
        long startTime, endTime;
        
        System.out.println("=== 타뷸레이션 피보나치 ===");
        startTime = System.nanoTime();
        int result = fibonacci(40);
        endTime = System.nanoTime();
        
        System.out.println("fibonacci(40) = " + result);
        System.out.println("실행 시간: " + (endTime - startTime) / 1_000_000.0 + "ms");
    }
}

/*
실행 결과

=== 타뷸레이션 피보나치 ===
fibonacci(40) = 102334155
실행 시간: 0.003ms
*/

타뷸레이션 동작 과정

═══════════════════════════════════════════════════
fibonacci(5) with Tabulation
═══════════════════════════════════════════════════

초기 테이블: table = [0, 1, _, _, _, _]
                   ↑  ↑
                   기저값

Step 1: i = 2
table[2] = table[0] + table[1] = 0 + 1 = 1
table = [0, 1, 1, _, _, _]
            ↑  ↑
           사용 저장

Step 2: i = 3
table[3] = table[1] + table[2] = 1 + 1 = 2
table = [0, 1, 1, 2, _, _]
               ↑  ↑
              사용 저장

Step 3: i = 4
table[4] = table[2] + table[3] = 1 + 2 = 3
table = [0, 1, 1, 2, 3, _]
                  ↑  ↑
                사용 저장

Step 4: i = 5
table[5] = table[3] + table[4] = 2 + 3 = 5
table = [0, 1, 1, 2, 3, 5]
                     ↑  ↑
                    사용 저장

최종 결과: table[5] = 5


특징

재귀 호출 없음
함수 호출 오버헤드 없음
스택 오버플로우 위험 없음
반복문으로 간단하게 구현
순차적으로 계산하므로 캐시 효율성 높음

성능 측정 비교

public class FibonacciComparison {
    
    // 기본 재귀
    public static int fibonacciRecursive(int n) {
        if (n == 0 || n == 1) return n;
        return fibonacciRecursive(n - 2) + fibonacciRecursive(n - 1);
    }
    
    // 메모이제이션
    public static int fibonacciMemo(int n, Map<Integer, Integer> memo) {
        if (n == 0 || n == 1) return n;
        if (!memo.containsKey(n)) {
            memo.put(n, fibonacciMemo(n - 2, memo) + fibonacciMemo(n - 1, memo));
        }
        return memo.get(n);
    }
    
    // 타뷸레이션
    public static int fibonacciTable(int n) {
        if (n <= 1) return n;
        int[] table = new int[n + 1];
        table[0] = 0;
        table[1] = 1;
        for (int i = 2; i <= n; i++) {
            table[i] = table[i - 2] + table[i - 1];
        }
        return table[n];
    }
    
    public static void main(String[] args) {
        int n = 40;
        long startTime, endTime;
        
        System.out.println("=== 피보나치 수열 성능 비교 (n=" + n + ") ===\n");
        
        // 기본 재귀 (경고: n=40에서 매우 느림!)
        System.out.println("1. 기본 재귀 방식");
        startTime = System.nanoTime();
        int result1 = fibonacciRecursive(n);
        endTime = System.nanoTime();
        System.out.println("   결과: " + result1);
        System.out.println("   시간: " + (endTime - startTime) / 1_000_000.0 + "ms");
        System.out.println();
        
        // 메모이제이션
        System.out.println("2. 메모이제이션 방식");
        startTime = System.nanoTime();
        int result2 = fibonacciMemo(n, new HashMap<>());
        endTime = System.nanoTime();
        System.out.println("   결과: " + result2);
        System.out.println("   시간: " + (endTime - startTime) / 1_000_000.0 + "ms");
        System.out.println();
        
        // 타뷸레이션
        System.out.println("3. 타뷸레이션 방식");
        startTime = System.nanoTime();
        int result3 = fibonacciTable(n);
        endTime = System.nanoTime();
        System.out.println("   결과: " + result3);
        System.out.println("   시간: " + (endTime - startTime) / 1_000_000.0 + "ms");
    }
}

/*
실행 결과

=== 피보나치 수열 성능 비교 (n=40) ===

1. 기본 재귀 방식
   결과: 102334155
   시간: 856.234ms

2. 메모이제이션 방식
   결과: 102334155
   시간: 0.123ms

3. 타뷸레이션 방식
   결과: 102334155
   시간: 0.089ms
*/

세 가지 방법 비교

방식	기본재귀	메모이제이션	타뷸레이션
시간 복잡도	O(2^n)	O(n)	O(n)
공간 복잡도	O(n)	O(n)	O(n)
함수 호출	많음	보통	없음
구현 난이도	쉬움	보통	쉬움
실행 속도	매우느림	빠름	가장빠름
메모리 효율	좋음	나쁨	보통

시간 복잡도 상세 분석

기본 재귀

T(n) = T(n-1) + T(n-2) + O(1)

이는 피보나치 수열 자체와 유사한 재귀식
→ T(n) ≈ φ^n (황금비)
→ O(2^n) 지수 시간

실제 호출 횟수
F(5):  15번
F(10): 177번
F(20): 21,891번
F(30): 2,692,537번
F(40): 331,160,281번

메모이제이션

각 F(i)를 최대 1번만 계산
F(0), F(1), ..., F(n) → n+1개

시간 복잡도: O(n) ✓
공간 복잡도: O(n) 해시맵 + O(n) 재귀 스택

타뷸레이션

for 루프가 n번 실행
각 반복마다 O(1) 연산

시간 복잡도: O(n) ✓
공간 복잡도: O(n) 배열만 사용

메모이제이션 vs 타뷸레이션

메모이제이션을 사용하는 경우

재귀적 사고가 자연스러운 문제
모든 부분 문제를 계산할 필요가 없는 경우
문제가 복잡하고 하향식 접근이 직관적인 경우
Top-Down 방식이 이해하기 쉬운 경우

타뷸레이션을 사용하는 경우

모든 부분 문제를 해결해야 하는 경우
반복문으로 구현이 자연스러운 경우
최대 성능이 필요한 경우
재귀 깊이 제한을 피하고 싶은 경우
메모리 효율이 중요한 경우

동적 프로그래밍은 “닥터 스트레인지처럼 시간을 공간으로 바꾸는 마법”이다. 아마도

인프런 강의 중 감자님의 강의 ‘그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)’ 강의 참고