Top-Down vs. Bottom-Up (DP)

동적 프로그래밍의 두 가지 접근 방식: Top-Down vs. Bottom-Up

동적 프로그래밍을 사용할 때, 두 가지 방식으로 문제를 해결할 수 있다..

1. 탑다운(Top-Down): 재귀(Recursion) + 메모이제이션(Memoization)
2. 보텀업(Bottom-Up): 반복문(Iteration)

---

1. 탑다운(Top-Down) 방식: 재귀 + 메모이제이션

private static int[] memo = new int[100];

public static int fibTopDownMemo(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (memo[n] != 0) return memo[n]; // 이미 계산된 값이면 반환

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

---

2. 보텀업(Bottom-Up) 방식: 반복문 사용

보텀업 방식은 가장 작은 문제부터 해결하고, 이를 기반으로 큰 문제를 해결하는 방식이다.

public int fibonacciBottomUp(int n) {
    int[] fibList = new int[n + 1]; // 배열 크기는 n+1
    fibList[0] = 0;
    fibList[1] = 1;

    for (int i = 2; i <= n; i++) { // 작은 값부터 채워나감
        fibList[i] = fibList[i - 1] + fibList[i - 2];
    }

    return fibList[n]; // 마지막 값 반환
}

코드 설명

1. fibList 배열을 n+1 크기로 생성 (인덱스 0~n 포함)
2. fibList[0] = 0, fibList[1] = 1 기본값 설정
3. 반복문을 사용해 작은 값부터 차례로 피보나치 수 계산
4. 최종 결과(fib(n))을 반환

---

3. 시간 복잡도 분석

✅ 탑다운 방식(재귀 + 메모이제이션)

• 중복된 연산을 줄이기 위해 메모이제이션을 사용.
• 시간 복잡도: O(n)
• 추가 메모리 필요: O(n) (메모이제이션을 위한 배열 저장)

✅ 보텀업 방식(반복문)

• 메모이제이션 없이 처음부터 끝까지 계산.
• 시간 복잡도: O(n)
• 추가 메모리 필요: O(n) (배열 fibList 사용)

---

4. 메모이제이션을 추가하면 어떻게 될까?

현재 보텀업 방식에서는 배열을 새로 생성하고, 반복문을 다시 실행해야 한다.
즉, 같은 값을 다시 계산해야 하므로, 두 번째 실행도 O(n) 이 된다..

메모이제이션을 추가하면?

• 한 번 계산한 값을 배열에 저장하고, 필요할 때 즉시 가져온다.
• 두 번째 실행부터는 O(1) 만에 값을 가져올 수 있다.

private static int[] memo = new int[100]; // 미리 저장할 배열

public static int fibonacciWithMemo(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (memo[n] != 0) return memo[n]; // 이미 계산된 값이면 반환

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

✔ 첫 번째 실행: O(n) (재귀적으로 계산 및 저장)
✔ 두 번째 실행 이후: O(1) (배열에서 바로 가져옴)

하지만 추가적인 메모리(O(n))를 사용한다는 단점이 있다.

---

5. 메모리 최적화: 배열 없이 보텀업 구현

배열을 사용하지 않고, 변수 두 개만 사용하여 메모리를 절약할 수도 있다.

public static int fibonacciOptimized(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    int prev2 = 0, prev1 = 1;
    int result = 0;

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

    return result;
}

✔ 시간 복잡도: O(n)
✔ 공간 복잡도: O(1) (배열 없이 변수만 사용)

---

6. 최종 정리

탑다운 (재귀 + 메모이제이션)	O(n)	O(n)	재귀 사용, 중복 연산 방지
보텀업 (배열 사용)	O(n)	O(n)	반복문 사용, 작은 문제부터 해결
보텀업 (메모리 최적화)	O(n)	O(1)	추가 메모리 없이 변수만 사용

✔ 탑다운 방식: 메모이제이션을 사용하면 효율적이지만, 재귀 호출로 인해 스택 오버플로우 위험이 있음.
✔ 보텀업 방식: 배열을 사용하면 직관적이지만 추가 메모리 필요.
✔ 보텀업 (메모리 최적화): O(1) 메모리만 사용하여 가장 효율적.