동적 계획법 (Dynamic Programming, DP)

동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 효율적으로 해결하기 위해 문제를 작은 하위 문제로 나누고, 이 하위 문제들의 해결 결과를 저장하여 재사용하는 알고리즘 기법이다. 중복된 계산을 피하면서 최적의 결과를 얻기 위해 사용된다.

특징

최적 부분 구조 (Optimal Substructure)

큰 문제의 최적해가, 그 문제를 구성하는 하위 문제들의 최적해로부터 얻어질 수 있는 구조를 말한다. 즉, 문제를 여러 작은 하위 문제로 나누고, 각 하위 문제를 최적으로 해결한 후 이들을 결합해 전체 문제의 최적해를 구할 수 있어야 한다.

피보나치 수열에서 F(n)을 계산하려면 F(n−1)과 F(n−2)의 값이 필요하다. 각 하위 문제 F(n−1)과 F(n - 2)는 다시 더 작은 하위 문제로 나눌 수 있다.

중복 하위 문제 (Overlapping Subproblems)

문제를 해결하는 과정에서 동일한 하위 문제가 여러 번 반복적으로 계산되는 경우를 말한다. 동적 계획법은 이러한 중복되는 하위 문제의 결과를 저장하고 재사용함으로써 계산 시간을 절약한다.

피보나치 수열에서 F(3)을 계산하기 위해 F(2)와 F(1)이 필요하고, F(4)를 계산할 때도 F(3)과 F(2)가 필요하다. 동적 계획법은 이미 계산한 F(3)의 값을 저장해 두고 재사용함으로써 중복 계산을 피한다.

구현

탑다운 (Top-down)

탑다운 방식은 재귀적 접근을 사용하여 문제를 큰 문제에서 작은 문제로 나누어 해결하는 방법이다. Memoization과 결합되어 사용된다.

재귀 호출이 깊어지면 스택 오버플로우가 발생할 수 있고, 재귀 호출에 따른 오버헤드가 발생한다.

Memoization

동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 최적화하는 방식이다.

memo = {}

def fibo(n):
    if n == 1 or n == 2:
        return 1
    if n not in memo:
        memo[n] = fibo(n - 1) + fibo(n - 2)
    return memo[n]

바텀업 (Bottom-Up)

바텀업 방식은 반복문을 사용한 비재귀적 접근을 통해 작은 하위 문제부터 차례대로 해결하여 큰 문제를 해결하는 방법이다. Tabulation과 결합되어 사용된다.

재귀 호출에 따른 추가적인 오버헤드가 없지만 문제의 크기에 따라 초기 메모리 사용량이 높을 수 있다.

Tabulation

동적 계획법에서 작은 하위 문제부터 순차적으로 해결해 결과를 테이블에 저장하고 이를 이용해 큰 문제를 해결하는 방식이다.

def fibo(n):
    if n == 1 or n == 2:
        return 1
    table = [0] * (n + 1)
    table[1], table[2] = 1, 1
    for i in range(3, n + 1):
        table[i] = table[i - 1] + table[i - 2]
    return table[n]