동적 계획법(Dynamin programming)
개요
동적 계획법이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이는 분할 정복(Divide and conquer)과 비슷하지만, 한 가지 큰 차이는 '작은 문제의 중복이 발생하지 않도록 한다'는 것이다. 중복이 발생하지 않으므로 분할 정복 방법에 비해 시간복잡도가 크게 감소한다.
따라서 조건으로 주어지는 값의 범위가 크고 경우의 수가 매우 많은 문제들을 해결하고자 할 경우 동적 계획법(이하 DP)를 활용하여 푸는 것이 적절할 수 있다.
방법
DP에서는 각기 나누어진 '작은 문제'를 한 번만 풀어야 하며, 따라서 그렇게 풀이한 작은 문제의 정답은 어딘가에 메모해 두어야 한다. 그리고 더 큰 문제를 풀어 나갈 때 동일한 작은 문제가 나타나면 앞서 메모해 둔 작은 문제의 결괏값을 대입해 문제를 해결하는 것이 DP이다.
즉, 상향식 접근법에 해당하며, 가장 작은 부분의 답을 구한 뒤 이를 저장하고 저장한 값을 이용하여 상위의 문제를 풀어 가는 방식이라고 볼 수 있다. 이때 Memoization이라는 기법이 핵심으로 작용한다.
동적 계획법의 조건
우선 DP를 적용할 수 있는 조건을 확인해 보자. DP를 적용하기 위해서는 두 가지 조건을 모두 만족해야 한다.
부분 반복 문제(Overlapping subproblem)
DP의 등장은 '피보나치 수열'이라고 한다. 피보나치 수열은 대표적인 재귀함수로서 다음과 같이 표현할 수 있다.
def fibo(n):
if n <= 1:
return n
else:
return fibo(n-1) + fibo(n-2)fibo(7)을 구하는 과정을 도식화하면 다음과 같이 나타낼 수 있다.
7번째 값을 구하기 위해서 fibo 함수가 총 25번 호출되는 것을 확인할 수 있다. 그런데 이 과정에서 fibo(5), fibo(4), fibo(3) 등 앞서 진행했던 연산을 다시 반복적으로 진행하는 것을 볼 수 있다.
이러한 반복적인 연산을 부분 반복 분제(Overlapping subproblem)라고 하며, 어떤 문제가 여러 개의 부분 문제로 나누어질 수 있음을 의미한다. 그리고 이때 부분 문제는 새로운 부분 문제를 생성하는 것이 아니라 계속해서 같은 부분 문제가 재사용되거나 재귀 등으로 해결되는 문제를 말한다.
최적 부분 구조(Optimal substructure)
최적 부분 구조란 작은 부분 문제에서 구한 최적의 답을 이용해 더 큰 문제의 최적의 답을 구할 수 있어야 한다는 것이다. 따라서 어떤 부분 문제의 정답은 문제의 크기와 관계없이 동일해야 한다.
다시 피보나치 수열을 예로 살펴보자. fibo(5)를 구한다고 할 때 큰 문제인 fibo(5)의 답이 최적의 답이 되려면 작은 부분 문제인 fibo(4)와 fibo(3)이 최적의 답이어야 한다. 즉, 작은 부분 문제(fibo(3), fibo(4))의 최적의 답을 이용해 더 큰 문제(fibo(5))의 최적의 답을 구하게 된다.
이때 fibo(4)를 구하기 위해 다시 fibo(3)과 fibo(2)를 구해야 하는데, 이렇게 되면 fibo(3)의 계산이 중복되게 된다. 이렇게 중복되는 연산을 없애는 것이 DP가 분할 정복 방식과 다른 점이며, 여기에서 바로 Memoization이라는 개념이 등장하게 된다.
메모이제이션(Memoization)
중복 연산 과정을 해결하기 위해 등장한 개념으로, '이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하는 방식'이다.
앞서 살펴본 피보나치 수열을 메모이제이션을 이용해 다시 구현해 보자.
memoization = [0] * 100 # 결괏값을 기억하기 위한 리스트
def fibo_mem(n):
if n == 1 or n == 2:
return 1
if memoization[n] != 0: # 이전에 계산한 적이 있는 식이라면 해당 결괏값을 그대로 반환
return memoization[n]
else:
memoization[n] = fibo_mem(n-1) + fibo_mem(n-2)
return memoization[n]
결과는 동일하지만 이전에 계산한 결괏값을 리스트에서 불러와 그대로 사용하므로 효율적인 계산이 가능하다.
동적 계획법의 2가지 접근 방법
Top-down
큰 문제에서 작은 부분 문제로 나누어 가면서 재귀 호출을 통해 문제를 푸는 방식이다. 앞서 구현했던 피보나치 수열이 Top-down 방식을 이용한 것이다. 이 방식은 점화식을 이해하기가 쉽다는 장점이 있다.
Bottom-up
Top-down과는 반대로 작은 문제들의 답부터 구하고 이를 이용해 전체 문제의 답을 찾는 방식이다. 재귀 호출을 하지 않기 때문에 시간과 메모리 사용량을 줄일 수 있다는 장점이 있다.
상향식으로 문제를 해결할 경우 결괏값을 저장하는 방식을 tabulation이라고 한다. 명칭은 다르지만 근본적인 개념은 크게 차이가 없으므로 간단히 보고 넘어가자.
그러면 피보나치 수열을 상향식으로 구현해 보자.
tabulation = [0] * 100 # 결괏값을 기억하기 위한 리스트
tabulation[1], tabulation[2] = 1, 1
def fibo_tab(n):
if n == 1 or n == 2:
return tabulation[n]
for i in range(3, n+1):
tabulation[i] = tabulation[i-1] + tabulation[i-2]
return tabulation[i]참고 자료
관련 코딩테스트 풀이
