다이나믹 프로그래밍

다이나믹 프로그래밍

재귀 함수를 이용하여 구현했던 피보나치 수열의 경우에
$f(n)$ 함수에서 n이 커질수록 수행 시간이 기하급수적으로 늘어나게 된다.
$O(2^n)$의 시간 복잡도를 갖기 때문에, $n = 30$이라면 10억 가량의 연산을 수행해야 한다.

n = 6일 때의 함수 호출 과정을 살펴보자.

f(6)을 구하기 위해 f(3)뿐만 아니라 동일한 함수가 반복적으로 호출되는 것을 알 수 있다.

이처럼 수열의 점화식을 재귀함수를 사용하여 만들 수는 있지만, 단순히 매번 계산하도록 하면 문제를 효율적으로 해결할 수 없다.

이러한 문제는 다이나믹 프로그래밍(Dynamic Programming)을 사용하여 효율적으로 해결해야 한다.

다이나믹 프로그래밍을 사용할 수 있는 조건

1. 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있다.
2. 중복되는 부분 문제 : 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

피보나치 수열은 위의 조건을 만족하는 대표 문제이다.
이 문제를 메모이제이션(Memoization) 기법을 사용하여 해결해보자.

메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하여 메모한 결과를 그대로 가져오는 기법이다. 메모이제이션은 값을 저장하는 방법이므로 캐싱(caching)이라고도 한다.

또한 '메모이제이션'이라는 표현은 Top-Down 방식에서만 국한되어 사용되는 표현이다.

재귀, Top-Down(하향식)

# Memoization하기 위한 리스트 초기화
m = [0] * 100

# 재귀 -> Top down
def fibo(x) :
    print('f(' + str(x) + ')', end=' ')
    if x == 1 or x == 2 :
        return 1
    # 계산한 적 있는 문제라면, 리스트에서 해당 값 꺼내옴
    if m[x] != 0 :
        return m[x]
    else :
        m[x] = fibo(x-1) + fibo(x-2)
        return m[x]

print(fibo(6))

이처럼 재귀 함수를 이용하여 다이나믹 프로그래밍을 구현하는 방법을
큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운(Top-Down)방식이라고 한다.

반복문, Bottom-UP(상향식)

Top-Down 방식에서는 결과 저장용 리스트 구현을 '메모이제이션'이라고 했지만,
Bottom-Up 방식에서 사용되는 결과 저장용 리스트는 'DP Table'이라고 불린다.

또한, Bottom-Up방식이 다이나믹 프로그래밍의 전형적인 형태이다.

DP Table을 이용한 Bottom-UP 방식의 Dynamic Programming

# DP Table 초기화
d = [0] * 100

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

# 반복문으로 구현하는 Bottom-Up 방식의 Dynamic Programming
for i in range(3, n+1) :
    d[i] = d[i - 1] + d[i - 2]

print(d[n])