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

필요성

알고리즘 문제를 풀 때, 완전 탐색 + 정직한 계산으로 풀어나가다 보면 최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제들이 생길 때가 있다.

이럴 때 어떤 문제의 경우는 메모리 공간을 약간만 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 존재한다. 이 중 대표적인 방법이 바로 최적화 이론 중 하나인 다이나믹 프로그래밍 기법, 동적 계획법이다.

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

우선 피보나치 수열의 수학적 점화식을 재귀 함수를 사용하여 코드로 작성해보면 다음과 같다.

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

위와 같은 피보나치 수열의 코드는 매우 간결하지만, 실제로 컴퓨터가 계산하기에는 매우 부적합한 형태이다. 바로 fibo(n) 함수에서 n이 커지면 커질수록 자잘한 하위 함수들이 함께 실행돼 수행 시간이 기하 급수적으로 늘어나기 때문이다. 이때의 시간 복잡도는 O(2^n)의 지수 시간이 된다.

또한 공간의 문제도 있다. 함수가 호출되면 프로그램 메모리의 스택에 데이터가 쌓이게 되고, 그 함수의 실행이 끝났을 때 다시 메모리가 해제되는데, 함수가 끝나기전에 계속해서 함수의 중첩이 쌓이게 되고 조금만 n이 증가 되어도 한 번의 함수 실행에 수 십, 수 백개의 함수가 실행되기 때문이다.

다이나믹 프로그래밍

위와 같이 피보나치 수열의 점화식을 재귀 함수를 사용해 만들 수는 있지만, 숫자가 조금만 커져도 시간 복잡도와 공간 복잡도가 지수 스케일로 폭발하므로 문제를 효율적으로 해결할 수 없게 된다.

이러한 문제는 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있다.

다이나믹 프로그래밍을 사용하기 위한 조건은 다음과 같다.

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

피보나치 수열은 이러한 조건을 만족하는 대표적인 문제다.

이 문제를 메모이제이션(Memoization) 기법을 사용해서 해결해보자.

메모이제이션이란 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 즉 메모이제이션은 값을 저장하는 방법이므로 캐싱(Caching)이라고도 한다.

메모이제이션을 구현하는 방법은 간단하다. 한 번 구한 정보를 리스트에 저장하기만 하면 된다. 다이나믹 프로그래밍을 재귀적으로 수행하다가 같은 정보가 필요할 때는 이미 구한 정답을 그대로 리스트에서 가져오면 된다.

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

이를 소스코드로 나타내면 다음과 같다.

d = [0] * 100

def fibo(x):
    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))

위와 같이 다이나믹 프로그래밍을 적용했을 때의 피보나치 수열 알고리즘의 시간 복잡도는 무려 O(N)이다. 왜냐하면 fibo(1)을 구한 다음 그 값이 fibo(2)를 구하는데 사용되고, 또 fibo(2)의 값은 fibo(3)을 푸는 데 사용되는 방식으로 동작하기 때문이다.

이렇게 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을, 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운(Top-Down) 방식이라고 말한다. 탑다운 방식은 ‘하향식’이라고도 하며 메모이제이션을 사용한다는 특징이 있다.

하지만 다이나믹 프로그래밍을 이용하여 빠른 시간안에 문제를 풀 수 있다고 하더라도, 이렇게 재귀 함수를 이용하여 문제를 풀이했다면 함수가 호출될 때마다 메모리 상에 적재되는 컴퓨터 시스템 특성상 오버헤드가 발생할 수도 있다.

따라서 재귀 함수 대신에 반복문을 사용하면 오버헤드를 줄일 수 있다. 일반적으로 반복문을 이용한 다이나믹 프로그래밍이 더 성능이 좋기 때문이다.

다음은 다이나믹 프로그래밍의 동일한 원리를 적용하되 단순히 반복문을 이용한 소스코드이다.

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

위와 같이 반복문을 이용하여 문제를 해결하는 방식을 작은 문제부터 차근차근 답을 도출한다고 하여 보텀업(Bottom-Up) 방식이라고 말한다. 보텀업 방식은 ‘상향식’이라고도 하며 이는 다이나믹 프로그래밍의 전형적인 형태이다.

보텀업 방식에서 사용되는 결과 저장용 리스트는 DP 테이블이라고 부르며, 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다.

엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미하므로, 다이나믹 프로그래밍과는 별도의 개념이다.

분할 정복(Divide and Conquer)과의 차이점

사실 큰 문제를 작게 나누는 방법은 퀵 정렬(Quick Sort)에서도 등장했지만 이는 분할 정복(Divide and Conquer) 알고리즘으로 분류된다. 그럼 분할 정복과 다이나믹 프로그래밍의 차이점은 무엇일까?

다이나믹 프로그래밍은 문제들이 서로 영향을 미치고, 분할 정복 알고리즘은 문제들이 서로 영향을 미치지 않는다.

퀵 정렬을 예로 들면 한 번 기준 원소인 pivot이 자리를 잡으면 그 기준 원소의 위치는 더 이상 바뀌지 않고, 따라서 그 pivot을 다시 처리하는 부분 문제는 존재하지 않는다.

하지만 다이나믹 프로그래밍은 이미 해결된 부분 문제에 대한 답을 저장해 놓고 해당 문제를 다시 해결해야 한다는 점이 특징이다.