[다이나믹 프로그래밍] 중복되는 연산을 줄이자

중복되는 연산을 줄이자

컴퓨터를 사용하여 해결하기 어려운 문제들 중에는 최적의 해를 찾는 데 많은 시간이 필요하거나 많은 메모리 공간이 필요한 문제들이 있다.

컴퓨터는 계산 속도와 메모리 공간을 제한하고 있기 때문에 이러한 문제들을 해결하는 데에는 제약이 많이 있다.

그래서 우리는 속도와 메모리 공간을 최대화할 수 있는 효율적인 알고리즘을 작성해야 한다.

그러나 일부 문제의 경우에는 약간의 메모리 공간을 더 사용하여 계산 속도를 현저하게 높일 수 있는 방법이 있다. 

 

대표적인 방법 중 하나는 이 장에서 다루는 동적 프로그래밍이다. 

먼저 동적 프로그래밍의 기본 아이디어를 소개하고, 그 다음 동적 프로그래밍의 두 가지 방법 (탑다운과 바텀업)을 알아보자.

특히, 동적 프로그래밍에서 자주 사용되는 메모이제이션 기법도 알아 보자.

 

 

다이나믹 프로그래밍을 활용하면 효율적인 문제(피보나치)

피보나치 함수(Fibonacci Function)을 재귀함수로 구현

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번 f(3)이 호출된다.

다시 말해, f(n)의 n이 커짐에 따라 반복 호출 횟수가 증가힌다.

 

비록 재귀 함수를 사용하여 이와 같이 피보나치 수열에 대한 방정식을 만들 수는 있지만, 단순히 매번 계산만 하면 문제를 효율적으로 해결할 수 없다.

 

이러한 문제들은 동적 프로그래밍을 사용하여 효율적으로 해결할 수 있다.

그러나 동적 프로그래밍은 항상 사용할 수 있는 것은 아니며, 다음 조건이 충족될 때 사용할 수 있다.

1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.
2. 작은 문제에서 찾은 올바른 답은 그것을 포함하는 큰 문제에서도 동일해야 한다. 

 

메모이제이션 기술을 사용하여 해결해 보자. 

한 번 얻은 결과를 메모리 공간에 기억하고, 동일한 방정식이 다시 호출될 때 기억된 결과를 검색한다.

 

동적 프로그래밍을 재귀적으로 수행하는 동안 동일한 정보가 필요할 때, 이미 정의된 답변을 목록에서 가져오기만 하면 된다.

피보나치 함수(Fibonacci Function)을 동적 프로그래밍으로 구현

# 한 번 계산된 결과를 메모이제이션(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))

위 코드는 실제로 1초도 걸리지 않고 빠르게 출력이 된다.

 

큰 문제를 작은 문제로 나누는 방법은 정렬할 리스트를 분할하여 정렬한 '분할 정복' 알고리즘인 퀵 정렬에서도 소개되었었다.

퀵정렬과 다이나믹 프로그래밍의 차이점은 내부의 작은 문제들이 서로 영향을 미치냐이다.

퀵정렬의 경우 피벗이 자리를 잡게 되면 그 기준 원소의 위치는 더이상 바뀌지 않고 이전의 그 피벗값을 다시 처리하는 부분문제는 존재하지  않는다.

반면에 다이나믹 프로그래밍은 한번 해결 했던 문제를 다시금 해결한다.

 

재휘 함수를 이용하는 메모이제이션에서는 한번 푼 문제는 그 결과를 저장해 놓았다가 나중에 동일한 문제를 풀어야할 때 이미 저정한 값을 반환한다. f(6)을 메모이제이션으로 찾은 그림은 아래와 같이. (색칠된 노드만 방문하게 된다)

 

처음 방식으로 호출했던 부분은 실선으로 노드를 표현했지만 실제로는 호출되지 않는다고 이해하자.

왜냐하면 호출하더라도 다시 계산을 하지 않고 리스트에 저장된 값을 바로 가져오기 때문이다.

 

물론 재귀함수를 사용하면 컴퓨터 시스템에 오버헤드가 발생할 수 있다.

따라서 주로 다이나믹 프로그래밍은 반복문을 이용해서 구현한다.

 

그렇다면 다이나믹 프로그래밍을 적용한 피보나치의 시간복잡도는 어떻게 될까? 바로 O(N)이다.

왜냐하면 f(1)을 구한다음 그 값이 바로 f(2)를 푸는데 사용되어 아래 그림과 같이 쭉쭉 이어지기 때문이다.

 

 

 

함수가 종료될 때 어떤 함수를 호출 했는지 확인하는 코드

d = [0] * 100

def fibo(x):
    print('f(' + str(x) + ')', end=' ')
    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]

fibo(6)

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

 

이처럼 재귀 함수를 이용하여 DP를 구현하는 방법을, 큰문제를 해결하기 위해 작은 문제를 호출 한다고 하여 탑다운(Top-down)방식이라고 한다.

반대로 단순히 반복뭄을 이용하여 작은 문제부터 차근차근 답을 도출하는 방식을 보텀업(Bottom-UP)방식이라고 한다.

 

보텀업 방식으로 구현한 피보나치

# 앞서 계산된 결과를 저장하기 위한 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])

 

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

결과 저장용 리스트를 DP테이블이라고 부른다.

 

또한 메모이제이션은 때에 따라 사전형(dict)과 같은 다른 자료형을 이용할 수도 있다.

an을 계산 하고자 할때 a0~an-1의 모두가 아닌 일부의 작은 문제에 대한 해답만 필요한 경우 사용한다.

3차원 리스트를 이용해야하는 복잡한 문제는 이후 배울 '최단경로'의 '플로이드 워셜 알고리즘'에서 학습하자.