다이나믹 프로그래밍

다이나믹 프로그래밍(DP)은 복잡한 문제를 해결하기 위해 작은 부분 문제로 나누고, 그 결과를 저장하여 동일한 계산을 반복하지 않도록 최적화하는 기법이다. 이 접근법은 주로 점화식(Recurrence Relation)을 기반으로 하며, 대표적인 예로 피보나치 수열, 배낭 문제, 최장 공통 부분 수열(LCS) 등이 있다.

점화식과 메모이제이션

점화식은 문제를 재귀적으로 정의하는 수학적 관계식이다. 예를 들어, 피보나치 수열은 다음과 같은 점화식으로 표현할 수 있다.

$F(n) = F(n-1) + F(n-2), \quad \text{(단, } F(0) = 0, F(1) = 1\text{)}$

일반적인 재귀 방식으로 구현하면 $O(2^N)$ 의 시간 복잡도를 가지며, 큰 입력값에 대해 매우 비효율적이다. 하지만 다이나믹 프로그래밍을 적용하면 중복 계산을 피할 수 있다.

# 재귀 함수로 구현한 피보나치

def fibo(x):
		if x == 1 or x == 2:
				return 1
		return fibo(x - 1) + fibo(x - 2)

print(fibo(100))

동일한 함수와 연산이 반복적으로 호출되므로, n이 커지면 커질수록 연산이 불가능할 정도로 많은 시간과 메모리를 소모해야 한다.

메모이제이션(Memoization)은 이전에 계산한 결과를 저장하여 동일한 연산을 반복하지 않는 방식이다. 이를 적용한 피보나치 수열 알고리즘은 O(n)의 시간 복잡도로 최적화된다.

# 메모이제이션 테이블 d
d = [0] * 100

def fibo(x):
    if x == 1 or x == 2:
        return 1
    if d[x] != 0:
        return d[x]
    d[x] = fibo(x - 1) + fibo(x - 2)
    return d[x]

print(fibo(99))

탑다운(Top-down)과 바텀업(Bottom-up) 방식

탑다운 접근법은 큰 문제부터 시작하여 작은 문제로 나누어 해결하는 방식이다. 보통 재귀(Recursion)를 사용하여 구현한다. 아래 탑다운 방식으로 구현된 피보나치 수열에서 함수가 실행되는 순서에 주목하자. 먼저 큰 숫자가 인수로 들어가 재귀적으로 작은 숫자를 실행한다. x가 1 또는 2가 되어야 반환문에 닿아 최종 결과를 출력한다.

d = [0] * 100

# 피보나치 함수를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
def fibo(x):
    if x == 1 or x == 2:
        return 1
    if d[x] != 0:
        return d[x]
    d[x] = fibo(x - 1) + fibo(x - 2)
    return d[x]

print(fibo(99))

바텀업 접근법은 작은 문제부터 시작하여 큰 문제로 확장해 나가는 방식이다. 반복문을 사용하여 작은 문제를 차례대로 해결하고, 그 값을 쌓아가며 큰 문제를 해결한다. 아래 바텀업 방식의 피보나치도 마찬가지로 가장 작은 숫자에서 시작해, 목표 숫자(n = 99)에서 반복을 종료한다.

d = [0] * 100

d[1] = 1
d[2] = 1
n = 99

# 피보나치 함수를 반복문으로 구현 (바텀업 다이나믹 프로그래밍)
for i in range(3, n + 1):
    d[i] = d[i - 1] + d[i - 2]

print(d[n])