동적 계획법 (Dynamic Programming, DP)

01. 동적 계획법이란 ? 

• 큰 문제를 작은 문제로 나누고, 작은 문제의 해답을 저장해두었다가 재활용하여 전체 문제를 푸는 방법론
• 문제를 분할하고 중복 계산을 피한다는 점에서 분할 정복과 유사하지만 계산 결과를 저장한다는 점이 차이점

02. 핵심 원리

• 최적 부분 구조 : 문제의 최적 해가 그 하위문제들의 최적 해로부터 구성될 수 있는 구조여야 함.
• 중복되는 부분 문제 : 같은 하위 문제가 여러 번 반복되어 등장하는 구조여야 함. 

03. 구현 방식 

• Top - Down 

재귀 + 메모이제이션 방식으로 풀었던 작은 문제들의 해를 저장해가면서 실행하는 방식으로

큰 문제에서 작은 문제들로 재귀적으로 나눠지며 실행된다. 

다만 , 주의할 점은 재귀 깊이가 커 질수록 콜스택에 무리가 갈 수도 있기 때문에 주의해야 한다. 

public static int FibonacciTopDown(int n, Dictionary<int, int> memo = null)
{
    if (memo == null)
        memo = new Dictionary<int, int>();

    if (n <= 1) return n;

    if (memo.ContainsKey(n))
        return memo[n];

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

 

* Dictionary는 참조형이기 때문에 '공유되는 하나의 객체' 로써 동작해서 같은 해를 두 번 구하지 않는다. 

즉, memo 객체는 하나의 재귀 흐름에서 공유되어야 하며, 보통 함수 인자로 전달해서 공유한다. 단, 전역 변수(static)으로 처리할 수도 있으나 , 가독성과 재사용성을 고려하면 함수 인자로 전달하는 방식이 더 일반적이다. 

 

처음에 푼 문제들의 답을 기록할 memo 객체를 만들고 , 재귀적으로 문제를 풀면서 답을 memo에 기록해둔다. 

이 방식으로 하면 똑같은 재귀를 반복할 필요가 없어 일반 재귀보다 훨씬 효율적이게 된다. 

 

• Bottom-Up

public static int FibonacciBottomUp(int n)
{
    if (n <= 1) return n;

    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];
}

 

Bottom - up 방식은 살짝 다르다. 

반복문을 통해 순차적으로 작은 문제에서부터 큰 문제로 계산을 한다. 

일반적으로 답을 저장할 배열이 필요하나, 만일 모든 숫자가 필요한 것이 아니라면 ( 모든 해가 아니라 하나의 해만 필요)

public static int FibonacciOptimized(int n)
{
    if (n <= 1) return n;

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

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

 

다음과 같이 공간 최적화를 통해 배열을 사용하지 않고도 해결할 수 있으며, 이 경우 메모리 사용량을 줄일 수 있다. 

이러한 Bottom - up 방식은 일반적으로 스택 오버플로우 위험이 없고, 재귀 호출이 없기 때문에 조금 더 성능상 유리한 경우가 많다. 특히 반복문 기반이라 시스템 리소스 측면에서 안정적이다. 

 

* 스택 오버플로우 : 콜 스택이 가득 차 넘치는 현상( 더 이상 데이터를 저장할 수 없게되는 현상 ) 

 

다만 Top - down 방식이 조금 더 직관적이고, 트리 구조/ 불규칙한 문제 구조에서는 유리할 수 있다. 

 

 

04. 사용 시기와 특징

• 문제가 최적 부분 구조를 갖고 같은 하위 문제의 반복이 많을 때 사용 ( 같은 계산을 여러 번 반복할 때 )
• 부분 문제들이 서로 독립적인 경우는 분할 정복이 더 적합
• 하위 문제의 수가 적거나 저장하고 다시 쓸 필요가 없는 경우는 비효율적
• 문제 구조가 선형이 아닌 완전 탐색이나, 백트래킹에 가까운 경우, 비효율적

 

• 일반적으로 동적 계획법은 O(n) ~ O(n^2)  범위의 시간복잡도를 갖고 있음
• 중복 계산을 제거하여, 완전탐색( O(2^n) ) 등을 선형/2차 수준의 시간복잡도로 줄일 수 있음