동적계획법(DP)

동적계획법은 큰 문제를 작은 문제로 나누어 푸는 문제를 일컫습니다. 동적계획법이 어떤 부분에서 동적으로 프로그래밍이 이루어진다는 말은 아닙니다. 동적계획법은 입력 크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로 원래 주어진 입력의 문제를 해결하는 것입니다. 

 

동적계획법의 조건은 이러합니다. 

1. 작은 문제가 반복하여 일어나는 경우(중복이 있는 경우)

2. 같은 문제는 구할 때마다 정답이 같은 경우

 

이러한 위와 같은 조건을 만족하는 경우에만 동적 프로그래밍을 사용할 수 있습니다. 작은 문제의 결과 값이 항상 같다는 점을 이용해서 큰 문제를 해결하는 방법입니다.

 

이와 같은 특성을 이용하여 한 번 계산한 작은 문제를 저장해놓고 다시 사용을 할 수 있습니다. 이것을 메모이제이션(Memoization) 이라고 합니다. 이것을 파이썬에서는 리스트나 배열을 이용하여 정답을 보관할 수 있는 것입니다. 

 

가장 대표적인 예로 피보나치 수열을 보겠습니다. 

피보나치 수열은 이전숫자와 자기자신을 더해서 다음 숫자를 구하는 것입니다. 1,1,2,3,5,8,,,,이러한 수를 갖게 되고 이는 점화식을 갖는 순열입니다. 

 

먼저, 재귀함수로 풀어보겠습니다. 

def fibo(n):
    if n <=2 :
        return 1 # 재귀함수의 탈출조건
    else:
        return fibo(n-1) + fibo(n-2)

재귀함수로 풀면 아주 간단하게 구현되는 것을 볼 수 있습니다. 그러나 n이 증가함에 따라 호출되는 함수의 수가 기하급수적으로 증가하기 때문에 일정 수 이상의 순열을 구하기가 어렵습니다. 

이처럼 똑같은 숫자가 계속 나오게 되면서 메모리를 많이 차지하게 되고 이것은 효율성을 떨어뜨리게 됩니다. 

 

이러한 문제에서 동적계획법을 사용할 수 있습니다. 

이 피보나치 수열의 경우 동적계획법의 두가지 조건을 만족합니다. 

1. 작은 문제들이 반복된다. 

>> F(5)를 구하기 위해서는 F(4), F(3) 이 필요합니다. 다시 F(4)를 구하기 위해서는 F(3), F(2)가 필요합니다. 보다시피 F(5)를 구하기 위해서도 F(3)이 필요하고, F(4)를 구하기 위해서도 F(3)이 필요합니다.  즉, 작은 문제가 계속 반복되는 것을 볼 수 있습니다. 

 

 

2. 같은 문제는 구할때마다 정답이 같다. 

>> 피보나치 수열의 경우 한 번 구한 값이 절대 바뀌지 않습니다. 

 

동적계획법으로 피보나치 수열을 푼 코드는 다음과 같습니다.

def fibo(n):
    val = [0,1]
    if n < 2:
        return val[n]
    else:
        for i in range(2,n+1):
            val.append(val[i-1] + val[i-2])
        return val[n], val
 
 (55, [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55])

코드를 보면 val[0], val[1]의 값을 이용해서 val[1] + val[0]를 val[2]에 append하고 append한 것은 다음 계산 시 이용하고 있습니다. 

 

이렇게 리스트나 배열을 이용하여 이전 답을 저장하고(캐쉬와 비슷) 필요할 때 꺼내 쓰게 되면 시간 복잡도를 매우 감소시킬 수 있습니다.