⚙️ Dynamic Programming

Last updated Dec 12, 2022 Edit Source

• Algorithm
• Dynamic programming

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

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

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

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

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import time

dp = [0] * 50

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

for num in range(5, 40, 10):
    start = time.time()
    res = fibo(num)

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

dp = [0] * 100

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

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

print(dp[N])

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

일반적으론 단순 반복문을 활용하는 Bottom-Up 방식으로 다이나믹 프로그래밍 방법을 해결하라고 권장한다. 만약 재귀함수를 사용하는 Top-Down 방식을 사용하다 보면 재귀 횟수 제한 오류가 걸릴 수도 있기 때문이다.