Dynamic Programming (DP) : 작은 문제의 답을 조합해 큰 문제를 푼다.

다이나믹 프로그래밍(DP)은 복잡한 문제를 여러 개의 작은 문제로 나누고, 그 작은 문제들의 결과를 재사용하여 전체 문제를 빠르게 해결하는 기법입니다.

🧠 Divide and Conquer vs Dynamic Programming

DP는 Divide and Conquer(분할 정복)와 유사해 보이지만, 몇 가지 중요한 차이점이 존재합니다.

구분Divide and ConquerDynamic Programming

🔁 Overlapping Subproblem (중복되는 부분 문제)

DP의 핵심 조건 중 하나는 중복되는 부분 문제가 존재해야 한다는 것입니다. 예를 들어, n번째 피보나치 수를 구하는 문제는 fibonacci(n-1)과 fibonacci(n-2)의 값을 구해야 하며, 이 과정에서 동일한 값(fibonacci(2), fibonacci(3) 등)을 여러 번 계산하게 됩니다.

이러한 중복을 피하기 위해, 한 번 계산한 결과를 어딘가에 저장해두고 다시 사용할 수 있어야 합니다. 이를 Memoization 또는 Caching이라고 합니다.

✨ Optimal Substructure (최적 부분 구조)

또 다른 핵심 조건은 Optimal Substructure, 즉 작은 문제의 최적해를 이용해 큰 문제의 최적해를 구할 수 있어야 한다는 것입니다. 문제를 작게 나눌 수 있고, 그 작은 문제들을 같은 방식으로 해결할 수 있다면 DP를 적용할 수 있습니다.

💡 피보나치 수열을 통해 이해하는 DP

✅ 재귀 호출 (비효율적 방식)

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

이 방식은 간단하지만, 같은 값을 여러 번 계산하게 되어 매우 비효율적입니다.

✅ Memoization을 이용한 Top-down 방식

int memo[100] = {0,};
 
int fibonacci(int n){
    if(n <= 1) return n;
    if(memo[n] > 0) return memo[n];
    
    memo[n] = fibonacci(n-1) + fibonacci(n-2);
    return memo[n];
}

한 번 계산한 값을 memo 배열에 저장해두고, 이미 계산된 값은 바로 반환하여 성능을 획기적으로 개선할 수 있습니다.

🧭 DP를 푸는 두 가지 접근 방식

🔼 Top-Down 방식 (재귀 + 메모이제이션)

1. 큰 문제를 작은 문제로 나눈다.
2. 작은 문제의 답을 계산하고 저장한다.
3. 저장된 결과를 조합해 전체 문제의 답을 구한다.

🔽 Bottom-Up 방식 (반복문 + 테이블)

1. 가장 작은 문제부터 차례대로 푼다.
2. 점차 문제의 크기를 키워가며 전체 문제를 해결한다.
3. 일반적으로 메모리 사용을 더 잘 제어할 수 있어 효율적이다.

int fibonacci(int n){
    int dp[100] = {0,};
    dp[1] = 1;
 
    for(int i = 2; i <= n; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

🎯 정리

• 다이나믹 프로그래밍은 중복되는 문제와 최적 부분 구조가 있는 경우 사용
• 핵심은 결과 재사용을 통해 시간 복잡도를 줄이는 것
• 접근 방식은 Top-down(재귀 + 메모이제이션)과 Bottom-up(반복문 + 테이블)