[알고리즘] 다이나믹 프로그래밍

다이나믹 프로그래밍 (Dynamic Programming)

다이나믹 프로그램은 동적 계획법이라고도 불리운다.

다이나믹 프로그램의 기본 모토는 중복되는 연산을 줄이는 것이다. 한번 실행한 연산들은 DP 테이블(리스트)에 저장해두고 그 연산이 필요할 때마다, 연산을 하지 않고 그 DP 테이블에서 연산데이터를 호출하는 방식이다. 이런 기법은 메모제이션 기법이다.

 

다이나믹 프로그래밍의 대표적인 예제로 피보나치 수열이 있다.

피보나치 수열의 점화식은 a(n) = a(n-1) + a(n-2), a(1) = 1, a(2) = 1 이다. 즉 이전 데이터와 전전 데이터를 더하여 현재 데이터가 된다.

 

피보나치 수열을 재귀적으로 구현한 코드는 다음과 같다.

# 피보나치 함수(Fibonacci Function)을 재귀함수로 구현
def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x - 1) + fibo(x - 2)

print(fibo(4))

 

위 코드의 시간 복잡도는 O(2**n) 이다. 40을 구하려고 해도 시간이 꽤 지나도 답이 구해지지 않는다.

이유는 반복되는 연산회수가 많기 때문이다.

 

다이나믹 프로그래밍을 사용하여 위 문제를 효율적으로 해결할 수 있다.

메모이제이션은 다이나믹 프로그래밍 구현방법 중 한 종류로, 한 번 구현한 결과를 메모리 공간에 메모해두고 같은 식을 호출하면 메모리 공간에서 꺼내와 쓰는 기법을 의미한다. 메모이제이션은 값을 저장하는 방법으로 캐싱이라고도 한다.

 

 

메모이제이션을 활용한 코드를 살펴보자

# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
d = [0] * 100

# 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
def fibo(x):
    # 종료 조건(1 혹은 2일 때 1을 반환)
    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]

print(fibo(99))

 

전에 계산한 값은 d 배열에 저장하여 반복되는 연산을 없앴다. 즉 다이나믹 프로그래밍은 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 플어 문제를 효율적으로 해결하는 알고리즘인 것이다.

 

위와 같이 메모이제이션을 사용한 재귀적 코드의 시간복잡도는 O(N) 이다. 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을, 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운방식이라고 말한다. 반면에 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여 보텀업방식이라고 말한다.

 

보텀업방식을 활용한 소스코드는 다음과 같다.

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99

# 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
for i in range(3, n + 1):
    d[i] = d[i - 1] + d[i - 2]

print(d[n])

 

다이나믹 프로그래밍의 전형적이 구현방법은 보텀업방식이다. 시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문이다. 파이썬에서 재귀 호출 제한 오류는 자주 발생하는데, 이는 sys 라이브러리의 setrecursionlimit(n)을 사용해서 해결 가능하다.