다이나믹 프로그래밍(Dynamic Programming)

1. 다이나믹 프로그래밍이란?

다이나믹 프로그래밍(DP)은 큰 문제를 작은 문제로 나누어 해결하고, 그 결과를 저장(memoization 또는 tabulation) 하여 중복 계산을 줄이는 최적화 기법

1. 중복 계산 방지 → 한 번 계산한 결과를 저장하여 재사용
2. 점화식(Recurrence Relation) → 작은 문제의 해를 조합해 큰 문제의 해를 표현
3. 최적 부분 구조(Optimal Substructure) → 작은 문제의 최적해가 큰 문제의 최적해 구성에 기여

2. DP를 적용할 수 있는 조건

1. 중복 하위 문제(Overlapping Subproblems)
   동일한 계산을 여러 번 수행해야 하는 경우
2. 최적 부분 구조(Optimal Substructure)
   작은 문제의 최적해를 이용해 큰 문제의 최적해를 구할 수 있어야 함

3. 예제: 피보나치 수열

피보나치 수열 점화식:

F(n)=F(n−1)+F(n−2),

F(1)=1, F(2)=1

3.1. 단순 재귀 (비효율적)

int fibonacci(int n) {
    if (n == 1 || n == 2) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

• 시간 복잡도: O(2ⁿ)
• 동일한 계산이 반복됨 → 매우 비효율적

3.2. Top-Down (메모이제이션)

이전 결과를 저장하여 중복 계산 제거

Map<Integer, Integer> memo = new HashMap<>();

int fibonacci(int n) {
    if (n == 1 || n == 2) return 1;
    if (!memo.containsKey(n)) {
        memo.put(n, fibonacci(n - 1) + fibonacci(n - 2));
    }
    return memo.get(n);
}

• 특징: 재귀(Recursion) 사용
• 한 번 계산한 값은 memo에 저장하여 재사용
• 시간 복잡도: O(n)

3.3. Bottom-Up (타뷸레이션)

작은 문제부터 차근차근 해결

Map<Integer, Integer> memo = new HashMap<>();

int fibonacci(int n) {
    memo.put(1, 1);
    memo.put(2, 1);
    for (int i = 3; i <= n; i++) {
        memo.put(i, memo.get(i - 1) + memo.get(i - 2));
    }
    return memo.get(n);
}

• 특징: 반복문(Iteration) 사용
• 계산 순서가 명확 → 스택 오버플로우 우려 없음

4. Top-Down vs Bottom-Up

• Top-Down: 필요한 시점에서 계산(재귀 기반), memoization 기법 사용
• Bottom-Up: 처음부터 차례로 계산(반복 기반), tabulation 기법 사용