다이나믹 프로그래밍 : DP

💡 다이나믹 프로그래밍(DP)란?

다이나믹 프로그래밍(Dynamic Programming), 줄여서 DP는 복잡한 문제를 여러 개의 작은 문제로 나누고, 이전 결과를 저장해서 재활용하는 방식이다.
같은 계산을 반복하지 않도록 해서 성능을 크게 높일 수 있다는 게 핵심이다.

📌 핵심 개념 두 가지

1. 중복되는 부분 문제 (Overlapping Subproblems)
   → 같은 문제를 반복해서 계산하게 되는 구조

2. 최적 부분 구조 (Optimal Substructure)
   → 전체 문제의 정답이, 그 하위 문제들의 정답으로 이루어지는 구조

이 두 조건이 만족되면 다이나믹 프로그래밍으로 문제를 풀 수 있다.

✅ 예시: 피보나치 수열

피보나치 수열은 DP의 대표적인 예시다.

f(0) = 0  
f(1) = 1  
f(n) = f(n-1) + f(n-2)

❌ 비효율적인 방식 (재귀)

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

이 방식은 같은 계산을 반복하게 되므로, 시간 복잡도가 O(2^n) 으로 매우 비효율적이다.

✅ 효율적인 방식 (DP - Bottom-Up)

public int fib(int n) {
    if (n == 0) return 0;
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

이 방식은 이전 값을 저장해두고 사용하는 방식이라서, 시간 복잡도는 O(n) 으로 훨씬 빠르다.

🔁 또 다른 예시: 동전 문제

여러 종류의 동전이 있을 때, 정해진 금액을 만들기 위해 필요한 최소 동전 개수를 구하는 문제

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1); // 큰 값으로 초기화
    dp[0] = 0;

    for (int coin : coins) {
        for (int i = coin; i <= amount; i++) {
            dp[i] = Math.min(dp[i], dp[i - coin] + 1);
        }
    }

    return dp[amount] > amount ? -1 : dp[amount];
}

동전 하나씩 확인하면서, 이전 값(dp[i - coin])을 이용해 현재 금액(i)을 만들 수 있는 최소 개수를 갱신해 나가는 방식이다.

이런 식으로 다이나믹 프로그래밍은 중복 계산을 없애고, 하위 문제의 해답을 쌓아가며 전체 문제를 해결하는 방식이다.
처음에는 구현이 낯설 수 있지만, 반복적으로 연습하다 보면 점점 익숙해진다!