다이나믹 프로그래밍 정복기1 - 기본이론 -

1. 중복되는 연산을 줄이기

 

현실 세계의 다양한 문제중에 컴퓨터를 활용해도 해결하기 어려운 문제란..?

 

최적의 해를 구하는데 시간이 매우 많이 필요하거나, 메모리 공간이 매우 많이 필요한 문제 등이 컴퓨터로도 해결하기 어려운 문제

 

컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적

 

그래서 연산속도와 메모리 공간을 최대한 활용할 수 있는 효율적인 알고리즘이 필요하다

 

 

2. 다이나믹 프로그래밍

 

어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다

 

대표적인 방법이 다이나믹 프로그래밍(동적계획법)이다.

 

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

 

피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징을 가진다

 

 

수학자들은 점화식을 사용해 수열의 항이 이어지는 형태를 간결하게 표현

 

점화식은 인접한 항들 사이의 관계식을 의미하며, 수열 ${a_{n}}$에 대하여 각 항을 $a_{n}$라고 부르자.

 

점화식을 이용해 위 피보나치 수열을 간단하게 표현한다면.. 첫번쨰 항과 두번째 항이 각각 1이므로

 

$a_{n+2} = a_{n+1} + a_{n}$, $a_{1} = a_{2} = 1$

 

이러한 점화식을 해석해보면???

 

n번째 피보나치 수 = (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수

 

단, 1번째 피보나치 수 = 2번째 피보나치 수 = 1

 

그런데 프로그래밍에서는 이러한 수열을 배열이나 리스트로 표현할 수 있다.

 

수열 자체가 여러개의 수가 규칙에 따라 배열된 형태를 의미하기 때문이다.

 

파이썬에서는 리스트 자료형이 이를 처리한다.

 

이 점화식으로 실제 피보나치 수를 구하는 과정을 어떻게 표현할 수 있을까?

 

n번째 피보나치 수를 f(n)이라고 한다면, 4번째 피보나치 수 f(4)는 다음과 같이 함수를 반복 호출하여 구한다

 

 

그런데, f(2)와 f(1)은 반드시 1이므로, 함수를 반복 호출하다가 f(2)와 f(1)을 만나면 호출을 정지하면 된다

 

 

3. 재귀함수 구현

 

수학적 점화식은 기본적으로 재귀함수를 사용하면 간단하다

 

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

print(fibo(4))

그런데 피보나치 수열을 재귀함수로 구현하면 심각한 문제가 생길 수 있다.

 

f(n)함수에서 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어나기 때문이다.

 

일반적으로 시간복잡도가 $O(2^{n})$이라고 표현함

 

N=30만 해도 10억번이나 연산을 해야해서 버벅거리기 시작함

 

 

 엄청 느린건 아니네??

 

아무튼 f(6)을 계산하는 과정을 보면..

 

 

동일한 함수가 반복적으로 호출된다는 것을 확인할 수 있다

 

f(3)은 3번이나 반복호출된다

 

이미 한번 계산했지만, 호출할때마다 또 계산해야한다는 것이 문제다.

 

30만해도 느려지기 시작하는데, n이 매우 클때, 이 느려지기 시작한 30을 여러번 계산한다고 생각하면..?

 

f(100)은 1000000000000000000000000000000번 연산해야한다는데?? 1초에 1억번 연산한다고 해도 수백억년 걸린다는데??

 

 

4. 메모이제이션(memoization)

 

피보나치 수열의 점화식을 재귀 함수로 구현할 수는 있지만, 단순히 매번 계산하도록 만든다면 문제를 효율적으로 해결할 수 없다.

 

이런 경우 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있지만, 매번 가능한 것은 아니다.

 

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

 

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

 

메모이제이션(memoization)은 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로,

 

한번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법이다.

 

값을 저장하는 방법이므로 캐싱(caching)이라고도 한다.

 

실제로 메모이제이션은 어떻게 구현할 수 있을까? 한번 구한 정보를 리스트에 저장하면 된다

 

재귀적으로 다이나믹 프로그래밍을 수행하다가, 같은 정보가 필요할 때는 이미 구한 정답을 그대로 리스트에서 가져오면 된다.

 

#한 번 계산한 결과를 메모이제이션 하기 위한 리스트 초기화

d = [0] * 100

#피보나치 함수를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)

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))
218922995834555169026

 

실행하자마자 답을 낼정도로 매우 빨라짐

 

메모이제이션을 위한 배열을 초기화하고, 0이 아니라면, 값이 저장되어있다는 뜻이니까 그걸 return하고 그렇지 않다면 값이 저장되어 있지 않다는 것이니까 점화식으로 계산하고 값을 저장한다음에 return함

 

#memoization

def fibo(n):
    
    if memo[n] == -1: ##계산된 값이 아니라면...
        
        memo[n] = fibo(n-1) + fibo(n-2) #직접 계산하고 저장
    
    return memo[n]

memo = [-1]*201

memo[0] = 0
memo[1] = 1

for i in range(201):
    
    print(i,fibo(i))

5. 정리

 

다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘

 

퀵 정렬은 정렬을 수행할 때 정렬할 리스트를 분할하며 전체적으로 정렬이 될 수 있도록 분할 정복을 한다

 

하지만 분할 정복과는 다르게 다이나믹 프로그래밍은 문제들이 서로 영향을 미친다.

 

퀵 정렬은 한 번 기준 원소 pivot이 자리를 변경해서 자리를 잡게 된다면 그 기준 원소의 위치는 더 이상 바뀌지 않고 그 피봇값을 다시 처리하는 부분 문제는 존재하지 않는다

 

반면에 다이나믹 프로그래밍은 한 번 해결한 문제를 다시 해결한다는 점이 특징이다.

 

그래서 이미 해결된 부분 문제에 대한 답을 저장해 놓고 이 문제는 이미 해결이 됐던 것이니까 다시 해결할 필요가 없다고 반환한다

 

예를 들어 재귀함수를 이용하는 메모이제이션 방법에서는 한번 푼 문제를 결과를 저장해놓았다가

 

나중에 동일한 문제를 풀어야할 때 이미 저장한 값을 반환한다

 

f(6) 해법을 메모이제이션 기법을 이용해 그려보면 6번째 피보나치 수는 다음과 같은 노드들만 방문하게 된다

 

 

이 경우 시간복잡도는 O(N)이다.

 

f(1)을 구한 다음 그 값이 f(2)를 푸는 데 사용되고 f(2)의 값이 f(3)을 푸는 데 사용되는 방식으로 이어진다.

 

한번 구한 결과는 다시 구해지지 않는다

 

함수가 종료될 때 어떤 함수를 호출했는지, 현재의 피보나치 수를 출력하도록 코드를 만든다면..?

 

d = [0] * 100

def pibo(x):
    
    print('f(' + str(x) + ')', end = ' ')

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

    return d[x]

pibo(6)
f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4) 8

 

재귀함수를 이용하여 다이나믹 프로그래밍을 하는 방법을 큰 문제를 해결하기 위해 작은 문제를 호출한다고 해서 탑다운(top down)방식이라고도 말한다

 

 

6. 반복문을 이용한 피보나치 메모이제이션

 

사실 함수가 호출되지 않는다고 말했지만,

 

재귀함수를 이용해 구현하면 컴퓨터 시스템에서는 함수를 다시 호출했을때 일련의 과정을 따라야 하므로 오버헤드가 발생할 수 있다

 

그래서 재귀함수 대신에 반복문을 사용하여 오버헤드를 줄일 수 있다

 

일반적으로 반복문을 이용한 다이나믹 프로그래밍이 더 성능이 좋다

 

반복문을 이용하여 다이나믹 프로그래밍을 하는 방법을 작은 문제부터 차근차근 답을 도출한다고 하여 바텀업(bottom up)방식이라고 부른다

 

#앞서 계산한 결과를 저장하기 위해 dp테이블을 초기화

d = [0] * 100

#첫번째 피보나치 수와 두번째 피보나치 수는 1

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])
218922995834555169026

 

아래도 똑같은 코드긴 함

 

def fibo_dp(n):
    
    table[0] = 0

    table[1] = 1

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

table = [0] * 101
fibo_dp(100)
print(table[100])

 

7. 정리

 

탑다운 메모이제이션 방식은 하향식이라고도 부르고 바텀업 방식은 상향식이라고도 부른다.

 

다이나믹 프로그래밍의 전형적인 형태는 바텀업 방식이다.

 

바텀업 방식에서 사용되는 결과 저장용 리스트는 DP 테이블이라고도 부른다

 

메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다 ㄹㅇ?

 

메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓은 넓은 개념을 의미해서 다이나믹 프로그래밍과는 별도의 개념

 

메모이제이션으로 때로는 사전 자료형을 이용할 수도 있다

 

이는 수열처럼 연속적이지 않은 경우에 유용하다

 

$a_{n}$을 계산하고자 할 때 $a_{0}$ ~ $a_{n-1}$ 모두가 아닌 일부의 작은 문제에 대한 해답만 필요한 경우가 존재할 수 있다 이런 경우에 사전 자료형을 사용하면 효과적이다.

 

다이나믹 프로그래밍을 이용하여 피보나치 수열 문제를 풀었던 방법을 잘 알아두면 다른 다이나믹 프로그래밍 문제에 접근하는 방법 또한 떠올릴 수 있을 것

 

문제를 푸는 첫번째 단계는 주어진 문제가 다이나믹 프로그래밍의 유형임을 파악하는 것

 

특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인해본다

 

일단 단순히 재귀함수로 비효율적인 탑다운 프로그램을 작성한 뒤에, 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있다면

 

메모이제이션을 적용할 수 있으면 코드를 개선하는 방법도 좋은 아이디어다.

 

앞서 다루었던 피보나치 수열의 예제처럼 재귀 함수를 작성한 뒤에 나중에 메모이제이션을 적용해 수정하는 것도 좋다

 

가능하다면 재귀 함수를 이용한 탑다운보다는 반복문을 이용한 바텀업 방식으로 구현하는 것을 권장한다

 

시스템상 재귀함수의 스택 크기가 한정되어 있을 수 있다.

 

실제로 앞에서 제시한 재귀함수 피보나치 수열에서 5000번째 이상의 큰 피보나치 수를 구한다면 recursion depth 에러가 발생할 수 있다.

 

이런 경우 sys.setrecursionlimit()를 이용해서 제한을 완화할 수도 있다