다이나믹 프로그래밍

최적의 해를 구하기 위해 시간 소요가 많거나 메모리를 많이 차지하는 문제는 컴퓨터로도 해결하기 어렵다. 그래서 연산 속도, 메모리를 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다. 어떤 문제는 메모리 공간을 약간만 더 사용하면 속도를 비약적으로 증가시킬 수 있다. 이런 것을 동적 계획법이라고 한다. 다이나믹 프로그래밍 방식은 탑다운, 보텀업 2가지 방식이 있다. 특히 다이나믹 프로그래밍을 위해 자주 사용되는 메모이제이션 기법도 있다.

프로그래밍에서 다이나믹은 '프로그램 실행되는 도중에'라는 의미이다. 하지만 다이나믹 프로그램에서 '다이나믹'은 이런 의미가 아니다.

 

-피보나치 수열

다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시는 피보나치 수열이 있다.

피보나치 수열의 점화식(인접한 항들 사이의 관계식을 의미)이다. 프로그래밍에서는 이러한 수열을 배열이나 리스트로 표현할 수 있다.

수학적 점화식을 프로그래밍으로 표현하려면 재귀 함수를 사용하면 간단하다.

 

-피보나치 함수 소스코드

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

print(fibo(4))

4번째 위치의 값을 구해준다.

하지만 이렇게 코드를 작성하면 문제가 생길 수 있다. 값이 커질 수록 수행 시간이 기하급수적으로 늘어나기 때문이다.

 

f(6)일 때 호출 과정

이렇게보면 동일한 함수가 반복적으로 호출된다. 이러한 문제는 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있다.

 

-다이나믹 프로그래밍의 조건

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 답은 그것을 포함하는 큰 문제에서도 동일하다.

 

탑다운 방식

피보나치 수열은 저 조건을 만족하는 대표적인 문제이다. 다이나믹 프로그래밍의 한 종류인 메모이제이션을 이용해 풀면 효율적으로 풀 수 있다. 메모이제이션은 한 번 구한 결과를 메모리 공간에 메모하고 같은 식을 다시 호출하면 메모한 결과를 가져온다. 이런 방법으로 동작해서 캐싱(caching)이라고도 한다.

한 번 구한 정보를 리스트에 저장하고 같은 정보가 필요하면 그 리스트에서 정답을 가져오면 된다.

 

-캐싱을 활용한 피보나치 수열

d = [0] * 100

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

print(fibo(99))

리스트 d에다가 저장을 하고 캐시처럼 꺼내서 사용하면 효율적으로 구현 가능하다.

 

=> 다이나믹 프로그래밍은 큰 문제를 작게 나누고, 같은 문제는 한번씩만 풀게 하는 것이다. 이런 큰 문제를 작게 나누는 방법은 퀵 정렬에서도 사용했다. 퀵 정렬은 리스트를 분할하며 전체적으로 정렬이 될 수 있도록 분할 정복 알고리즘을 사용한다. 다이나믹 프로그램과 분할 정복의 차이는 다이나믹 프로그래밍은 문제들이 서로 영향을 미친다는 점이다. 

 

물론 재귀 함수를 사용하면 함수를 다시 호출했을 때 메모리에 적재되는 과정에 의해 오버헤드가 발생할 수 있다. 따라서 재귀 함수 대신에 반복문을 사용하면 오버헤드를 줄일 수 있다. 일반적으로 반복문을 이용한 다이나믹 프로그래밍이 더 성능이 좋기 때문이다. 

반복문을 활용한 다이나믹 프로그래밍

이런식으로 사용되기 때문에 시간 복잡도가 O(N)이다.

이처럼 재귀 함수를 이용해서 다이나믹 프로그래밍 소스코드를 작성하는 법을 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운 방식이라고 한다.

 

보텀업 방식

반복문을 이용해서 작성하는 경우 작은 문제부터 차근차근 답을 호출한다고 해서 보텁업 방식이라고 한다.

 

-반복문을 이용한 피보나치 수열

d = [0] * 100

d[1] = 1
d[2] = 1
n = 99

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

print(d[n])

동일한 원리를 적용하되 단순히 반복문을 이용하여 문제를 해결하면 된다.

 

정리

탑다운 메모이제이션 방식은 하향식이라고 한다. 반대로 보텀업 방식은 상향식이라고 한다. 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이고 이 때 사용되는 결과 저장용 리스트는 DP 테이블이라고 부른다.

다이나믹 프로그래밍과 메모이제이션은 별도의 개념이다. 메모이제이션은 전에 사용했던 결과를 저장해두는 개념을 의미하여 다이나믹 프로그래밍과는 별도의 개념이다. 메모이제이션은 딕셔너리 자료형을 이용할 수도 있다. 전체중에서 작은 일부의 문제에 해답만 필요한 경우에는 딕셔너리가 유용하다.

문제를 풀 때 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍이 적용될 수 있는지 부분 문제들의 중복 여부를 확인하면 된다. 일단 비효율적인 재귀 함수로 작성한 뒤에 작은 문제에서 구한 답이 큰 문제에서 그대로 사용되는 메모이제이션을 적용할 수 있으면 코드를 개선하는 방법도 좋은 아이디어이다.

가능하다면 재귀 함수를 이용하는 탑다운 방식보다는 반복문을 활용하는 보텀업 방식으로 구현하는 것이 좋다. 시스템상 재귀 함수의 스택 크기가 한정되어 있을 수도 있기 때문이다. 만약 재귀적인 피보나치 수열에서 5,000번째 이상의 수를 구하도록 하면 recurison depth(재귀 함수 길이) 오류가 발생할 수 있다. 이 경우에는 sys 라이브러리에 포함되어 있는 setrecursionlimit() 함수를 통해 재귀 제한을 완화 해야한다.

 

-setrecursionlimit 함수

import sys
sys.setrecursionlimit(10 ** 6)

이런식으로 재귀 함수의 최대 깊이를 10**6으로 바꿔주면 에러가 잡힐 수도 있다.