동적 계획법으로 해결 가능한 문제를 판단하는 것은 때로는 경험이나 직감에 기반하기도 합니다. 그러나 일반적으로 다음 두 가지 주요 특성을 가진 문제들이 동적 계획법을 사용하여 해결될 가능성이 높습니다.

중복되는 부분 문제 (Overlapping Subproblems)

동적 계획법은 중복되는 부분 문제들을 효과적으로 해결하기 위해 설계되었습니다.

주어진 문제를 여러 작은 문제로 나누었을 때, 그 작은 문제들이 반복적으로 나타나는 경우 동적 계획법이 효과적입니다.

최적 부분 구조 (Optimal Substructure)

주어진 문제의 최적 해결 방법이 해당 문제의 부분 문제들의 최적 해결 방법을 포함하는 경우입니다.

즉, 큰 문제의 최적의 해결책을 찾기 위해 작은 문제들의 최적의 해결책을 사용할 수 있어야 합니다.

동적계획법으로 접근하는게 효율적인 경우

동적계획법의 대표적인 예시는 피보나치수를 구하는 문제가 있습니다.

피보나치를 구하는 과정은 아래와 같습니다.

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) (n >= 2)

이를 코드로 그대로 옮기면 아래와 같습니다.

def fibonacci_dp(n):
    if n <= 1:
        return n

    dp = [0] * (n + 1)
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]

    return dp[n]

위의 코드에서 dp 배열은 피보나치 수열의 값을 저장합니다. 이 방법은 중복 계산을 피하면서 각 값들을 한 번씩만 계산하므로 효율적입니다.

코드를 분석해보면, fibonacci_recursive(3) 같은 값을 여러 번 계산하게 됩니다. 이러한 중복된 계산은 많은 시간을 낭비하게 됩니다.(중복부분문제 만족) 추가적으로, 피보나치 수열에서 F(n)의 최적의 해는 F(n-1)과 F(n-2)의 최적의 해를 바탕으로 구해집니다. 즉, 큰 문제의 최적의 해결책을 작은 문제들의 최적의 해결책을 통해 얻을 수 있습니다.(최적 부분 구조 만족) 중복부분문제와 최적 부분 구조 모두 만족하므로, 피보나치수는 동적계획법을 통해 효율적으로 문제를 풀 수 있습니다.

동적계획법으로 접근하는게 효율적이지 않은 경우

이번에는 팩토리얼을 구하는 과정을 봅시다.

n! = n × (n-1) × (n-2) × ... × 2 × 1

이를 코드로 구현하면 아래와 같습니다.

def factorial_recursive(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial_recursive(n-1)

이 코드에서, factorial_recursive(n)을 호출하면 factorial_recursive(n-1)을 호출합니다. 그러나 이전에 계산한 값이 다시 사용되지 않습니다.(중복부분 문제가 아님) 즉, 어떤 값에 대한 팩토리얼을 계산하면 그 값에 대한 계산은 한 번만 이루어집니다.

따라서 팩토리얼은 동적계획법으로 접근하면 효율적이지 않습니다. 부분문제가 중복되지 않기 때문에, 메모이제이션으로 해도 효율이 없기 때문입니다.