[python]다이나믹 프로그래밍

들어가며

이글은 동빈나님의 이코테 강의를 보며 정리한 글입니다. 다이나믹 프로그래밍은 동적 계획법이라고도 합니다. 다이나믹 프로그래밍을 이해하기 위해서는 동적 할당(Dynamic Allocaion)을 이해할 필요가 있습니다.

C 언어를 공부하다보면 Allocation 함수, 즉 메모리 할당 함수들을 접하게 됩니다. 이와 비슷하게 동적 할당은 '프로그램이 실행되는 도중에 필요한 메모리를 할당하는 기법'을 의미합니다. 이해가 잘 안될 수 있으니 본격적으로 다이나믹 프로그래밍에 대해서 이야기 해보도록 하겠습니다.

Fibonacci Sequence

혹시 피보나치 수열에 대해서 알고계신가요? 피보나치 수열이란 초항 $a_{0}$와 두번째 항 $a_1$을 각각 0, 1이라고 하였을 때, 점화식을 통해 이전 두 항의 합으로 이루어진 수열을 의미합니다. 점화식으로 표현한다면 다음과 같습니다.

$a_0=0,a_1=1$

$a_i=a_{i-2}+a_{i-1}, (i\geq2)$

각 $i$에 양수들을 대입하면 피보나치 수열을 알 수 있습니다.

$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...$

파이썬으로 해당하는 인덱스의 피보나치 수열항을 구하는 프로그램을 작성할 때, 하단과 같이 작성할 수 있습니다.

def fibo(i):
	if i == 0:
    	return 0
    elif i == 1:
    	return 1
    else:
    	return fibo(i-2)+fibo(i-1)

print(fibo(5))

이는 피보나치 수열의 점화식을 이용하여 재귀함수를 통해 구현할 수 있습니다. 근데 이러한 방식에는 문제가 있습니다. 이러한 방식은 정답을 도출하기 위해서 자신보다 작은값에 대해서 계속 재귀함수 호출이 이루어지고, 이미 한번 계산된 과정 역시도 호출된다는 것입니다. 이러한 방식에서 피보나치 수열의 시간복잡도는 빅오 표기법으로 표현한다면 $O(2^n)$입니다. $i$의 크기가 증가한다면 지수함수적 증가를 하고 있기 때문에 엄청나게 거대해질 것입니다. 이러한 상황에서 수월하게 해결할 수 있는 것이 다이나믹 프로그래밍입니다.

Dynamic Programming

다이나믹 프로그래밍은 연산이 수행되면 DP테이블이라는 것을 만들어 값을 기록하고, 또 다시 연산이 수행된다면 DP테이블의 값을 이용합니다. 재귀함수를 또 호출할 필요가 없는 것이죠. 그렇기 때문에 새로운 연산에 대해서만 재귀함수를 호출하게 되어 시간복잡도가 훨씬 줄어들게 됩니다. 다만, 다이나믹 프로그래밍을 수행하기 위해서는 아래와 같은 조건을 만족해야 합니다.

1. 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있어야 함.
2. 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결함.

피보나치 수열을 구하는 과정은 이 두 조건을 모두 만족합니다. 점화식을 이용해서 큰 문제를 작은 문제로 나눌 수 있고, 각각의 과정 중 중복되는 풀이과정이 존재하기 때문입니다. 그러면 이제 정말 다이나믹 프로그래밍을 사용할 수 있습니다.

다이나믹 프로그래밍은 가장 아래에서 최상위로 이동하며 문제를 해결하는 상향식(Bottom Up), 가장 최상위에서 아래로 이동하며 문제를 해결하는 하향식(Top Down) 방식이 존재합니다. 일단 하향식 방식으로 피보나치 수열을 구하는 프로그램을 바꾸면 아래와 같습니다.

dp = [0] * 100 #DP테이블 초기화

def fibo(i):
	if i == 0:
    	return 0
    if i == 1:
    	return 1
    # 이미 계산되었다면 바로 사용
    if dp[i] != 0:
    	return dp[i]
    # 계산이 수행되지 않았다면 메모이제이션 수행
    dp[i] = fibo(i-2) + fibo(i-1)
    return dp[i]
        
print(fibo(5))

이 함수의 내용을 보겠습니다. 이 함수에 숫자가 들어오면 처음에는 DP 테이블이 비어있기 때문에 해당하는 인덱스의 DP테이블값을 점점 채우게 됩니다. 그렇게 되면 후의 계산들은 대부분 DP 테이블을 참조하여 바로바로 수행이 완료됩니다. 여기서 100으로 초기화한 것은 그냥 예시입니다. 실제로는 문제에서 입력될 수 있는 값을 포함하도록 설정해야 합니다. 이제 상향식 방법도 알아보겠습니다. 상향식 방법에서는 점화식을 그대로 프로그래밍으로 변환하는 일이 보통입니다. 한번 보겠습니다.

dp = [0] * 100 # DP 테이블 초기화
dp[1] = 1 #dp 1 미리 지정
for i in range(2, 5):
	d[i] = d[i-2] + d[i-1]

print(d[5])

상향식 방식은 반복문을 이용해서 구현하는 경우가 많습니다. 여기서 주의사항은 인덱스 범위를 벗어나면 안되기 때문에 처음에 지정된 값들은 초기화를 미리 수행하고, 인덱스 범위를 초과하지 않는 범위로 반복문을 실행해야 합니다.

다이나믹 프로그래밍을 이용하여 다시 만들어진 피보나치 함수 프로그램의 시간복잡도는 빅오 표기법으로 $O(n)$으로 지수함수적 특성에서 선형적 특성으로 줄어들었다는 것을 알 수 있습니다.