동적계획법 (Dynamic programming)

DP은 여러번 계산하지 않고 한번만 계산하는 것을 목표로 한다. 보통 점화식을 작성하는 문제에서 효율적으로 코딩하는데에 사용된다. 점화식 작성이란 전체 문제를 부분 문제로 생각하여 일반화 할 수 있는 방법을 찾아 식으로 작성하는 것이다.

가장 좋은 예시로 드는 것이 바로 피보나치 수열이다. 피보나치 수열은 $F_{n+2} = F_{n} + F_{n+1}$ 을 따르는 수열이다. $F_{0}$ 과 $F_{1}$ 이 각각 0, 1일 때, n=1 부터 나열하면 다음과 같이 피보나치 수열이 완성된다.

피보나치 문제를 풀 때 재귀를 먼저 생각할 것이다. 먼저 재귀로 풀어보자.

재귀로 접근, 그리고 한계

앞에 있는 두개의 숫자를 계속 불러오면 되므로 아래와 같이 쉽게 작성할 수 있다.

def Fibo(n):
    if n <= 1:
        return n
    
    return Fibo(n-2) + Fibo(n-1)

print(Fibo(8))

# 21

하지만 이렇게 하면 계산했던 수를 계속 다시 계산하므로 n이 높아지면 높아질 수록 복잡도가 굉장히 빨리 늘어난다. 그래서 이미 계산해둔 수는 다시 계산하지 않도록 작성하면 된다. (동적계획법)

동적 계획법

동적 계획법 (DP)은 이미 계산한 값을 다시 계산하지 않으므로써 계산량을 줄이는 것이 핵심이다. 이미 계산한 값을 다른 배열에 저장해두고 매번 재귀함수를 불러올 때마다 계산이 되어 있는지 아닌지 확인하면 된다.

def Fibo(n, history):
    if n <= 1:
        return n

    if history[n] == None:
        history[n] = Fibo(n-2, history) + Fibo(n-1, history)

    return history[n]

n = 8
history = [None] * (n + 1)
print(Fibo(n, history))

# 21