[Python] Dynamic Programming(동적계획법) 알고리즘

🔊 이번 포스팅에는 최근에 Python으로 알고리즘을 공부하기 시작하면서 알게 된 여러 알고리즘의 원리와 Python으로 구현하는 방법에 대해 소개해보려 한다. 필자는 최근 알고리즘 공부를 '나동빈'님의'이것이 취업을 위한 코딩 테스트다 with 파이썬'이라는 책과 백준 온라인 저지 사이트로 하고 있다. 이 중 '나동빈'님이 저자이신 책에서 가르쳐주는 내용을 기반으로 배운 내용을 정리해보려 한다.

 

이번 포스팅에서는 "한 번 계산한 문제는 다시 계산하지 않도록 한다!" 는 다이나믹 프로그래밍(Dynamic Programming, 동적 계획법이라고도 함)에 대해서 소개해보고 이를 Python으로 구현하는 방법에 대해 알아보자.

 

Dynamic한 프로그래밍 방법에 대해 알아보자!

 

다이나믹 프로그래밍은 메모리 공간을 약간 더 사용해서 연산 속도를 비약적으로 증가시키는 방법이다. 우선 다음과 같은 2가지 조건을 만족할 때 다이나믹 프로그래밍을 사용할 수 있다.

 

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

위 조건을 만족하는 대표적인 문제가 피보나치 수열 문제이다. 피보나치 수열은 다음과 같은 점화식을 만족하는 수열이다.

 

$$a_n = a_{n-1} + a_{n-2}, \ a_1=1,\ a_2=1$$

 

우선 피보나치 수열을 Python의 재귀함수로 구현한다면 다음과 같이 구현할 수 있다.

 

import time

def fibo(x):
    if x == 1 or x == 2:
        return 1

    return fibo(x-1) + fibo(x-2)

for num in range(5, 40, 10):
    start = time.time()
    res = fibo(num)
    print(res, '-> 러닝타임:', round(time.time() - start, 2), '초')

 

위와 같이 단순 재귀함수로 구현했을 때 $x$값이 커짐에 따라 연산 수행시간이 기하급수적으로 늘어남을 다음과 같이 관찰할 수 있다.

 

$x$값에 따른 러닝타임

 

따라서 이러한 문제를 해결하기 위해 다이나믹 프로그래밍을 사용해야 한다. 다이나믹 프로그래밍의 포인트는 바로 한 번 결과를 수행한 것을 메모리에 저장해 놓고 다음에 똑같은 결과가 필요하면 그 때 다시 연산하지 않고 메모리에 저장된 그 값을 가져와 쓰는 것이다.

 

이러한 것을 메모제이션(캐싱) 기법이라고도 한다. 다음은 재귀함수를 사용한 다이나믹 프로그래밍으로 피보나치 수열을 구현한 코드이다.

 

import time

d = [0] * 50

def fibo(x):
    if x == 1 or x == 2:
        return 1
    if d[x] != 0:
        return d[x]
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]

for num in range(5, 40, 10):
    start = time.time()
    res = fibo(num)
    print(res, '-> 러닝타임:', round(time.time() - start, 2), '초')

 

위 코드로 $x$ 값이 늘어남에 따라 함수 러닝타임이 어떻게 변하는지 살펴보자.

 

다이나믹 프로그래밍으로 구현한 결과의 러닝타임

 

단순 재귀함수로 구현한 것과는 다르게 $x$ 값이 증가해도 함수 러닝타임이 기하급수적으로 증가하지 않는 것을 볼 수 있다.

이렇게 재귀함수를 사용해 구현하는 다이나믹 프로그래밍 방법은 메모제이션 기법을 활용한 Top-Down 방식이라고 한다.

즉, 큰 문제를 해결하기 위해 작은 문제를 호출하는 것이다.

 

반면에 재귀함수를 사용하지 않고 단순 반복문을 사용해 다이나믹 프로그래밍을 구현할 수 있다. 하단의 코드를 살펴보자.

 

d = [0] * 100

d[1] = 1 # 첫 번째 항
d[2] = 1 # 두 번째 항
N = 99   # 피보나치 수열의 99번째 숫자는?

for i in range(3, N+1):
    d[i] = d[i-1] + d[i-2]

print(d[N])

 

위와 같은 방식은 작은 문제부터 차근차근 답을 도출해서 큰 문제를 해결한다고 하여 Bottom-Up 방식이라고 한다. 참고로 Top-Down 방식에서는 이미 수행한 결과를 저장하는 것을 메모제이션, Bottom-Up 방식에서는 DP 테이블이라고 한다.

Top-Down 방식의 메모제이션 기법은 사전(dictionary) 자료 형을 이용할 수도 있는데, 이는 수열처럼 연속적이지 않은 자료가 주어질 때 유용하다고 한다. 즉, $a_n$을 계산하기 위해 $a_0$ 부터 $a_{n-1}$ 모두를 살펴보는 것이 아닌 일부의 결과만 필요할 경우이다.

 

마지막으로 책의 저자 나동빈님은 단순 반복문을 활용하는 Bottom-Up 방식으로 다이나믹 프로그래밍 방법을 해결하라고 권장한다. 만약 재귀함수를 사용하는 Top-Down 방식을 사용하다 보면 재귀 횟수 제한 오류가 걸릴 수도 있기 때문이다. 물론 이러한 오류가 나타났을 때 sys 라이브러리의 setrecursionlimit() 메서드를 호출해서 재귀 제한 횟수를 늘려주는 방법도 있다고 한다.