DP

Dynamic Programming의 줄임말로 동적 계획법이라고 한다. 

 

주어진 문제가 있으면 이를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 목적에 도달하는 방법이다. 하위 문제를 나누어 푼 답들을 미리 저장하고 같은 하위 문제가 나왔을 때, 또 계산을 하는 것이 아닌 저장한 하위 문제의 값을 사용해 계산 횟수를 줄인다.

 

해결책을 저장한 것을 메모이제이션(Memoization)이라고도 한다.

 

DP를 사용하는 경우

대부분의 경우에 사용할 수 있는 것은 아니다. DP를 사용하는 경우는 하위 문제가 있는지, 최적 부분 구조가 존재하는지로 확인할 수 있다. 

 

하위 문제가 있다는 것은 더 작은 부분으로 나눌 수 있고, 그 나눈 부분 일부가 재활용이 가능하다는 뜻이다. 다만, 각각의 부분들은 다른 모습이어서는 안된다.

 

피보나치 수열

피보나치 수열을 예시로 들어보자. 피보나치 수열은 간단히 정리해서 첫째 항과 둘째 항이 1이고 다음 항부터는 바로 뒤의 두 항의 합을 의미한다. 즉, 1 - 1 - 2 - 3 - 5 - 8이 된다. 좀 더 생각해보면 첫째 항의 값을 저장하고 둘째 항의 값을 저장하면 셋째 항의 값을 구할 수 있고 둘째 항, 셋째 항의 값을 저장하고 있으면 넷째 항의 값을 손쉽게 구할 수 있는 구조이다.

 

# f(n) = f(n-1) + f(n-2)

따라서 이러한 점화식을 구할 수 있다.

 

허나 피보나치 수열을 구사하는 방법은 DP말고도 재귀를 사용해서 해결할 수도 있다. 재귀에 대해서는 나중에 따로 설명하는 것으로 하고 일단 코드를 구해보면 다음과 같다.

 

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

print(fib(3))

이렇게 하면 피보나치 수열을 구할 수는 있으나 함수 안의 함수를 또 리턴하기에 숫자의 크기가 커질수록 계속해서 연산을 해나가야 하는 구조이기 때문에 좋지 않은 방식이다.

 

def dp(n):
    array = [0] * (n + 1)
    array[0] = 1
    array[1] = 1

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

print(dp(6))

이렇게 값을 값을 메모이제이션하여 필요할 때 꺼내쓰면 연산이 줄어들기에 O(n)이라는 시간 복잡도가 발생하게 되어 더 빨라진다. 참고로 위의 방식은 bottom-up 방식이다.