[Algorithm] 다이나믹 프로그래밍의 이해

한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘

다이나믹 프로그래밍 (Dynaminc Programming)은 메모리 공간을 약간 더 사용해서 연산 속도를 비약적으로 증가시키는 알고리즘이다. 동적 계획법이라고도 불린다.

기본 아이디어

피보나치 수열을 생각해보자. 피보나치 수열은 이전 두 항의 합을 현재 항의 값으로 하는 수열이다. 점화식을 이용해서 수열의 항이 이어지는 형태를 간결하게 표현할 수 있는데, 피보나치 수열을 점화식으로 표현하면 아래와 같다.

이 점화식에 따라서 피보나치 수열을 구하는 과정을 어떻게 코드로 작성하면 될까 ?
n번째 피보나치수를 $f(n)$이라고 할때, 8번째 피보나치 수열 $f(4)$은 $f(3) + f(2)$으로 나타낼 수 있고, $f(3)$과 $f(2)$ 또한 이전 두 항의 합으로 나타낼 수 있다. 때문에 재귀 호출을 사용하면 아래처럼 쉽게 코드를 작성할 수 있다.

# 1번째 피보2치 수 1, 1번째 피보나치 수 2
def fibo(n):
	if n <= 2:
    	return 1;
    else:
    	return fibo(n-1) + fibo(n-2)

하지만 위와 같은 코드는 재귀 호출 과정에서 같은 연산을 너무 많이 반복하게 된다. $f(4)$를 예로 들면, 최종적으로 호출되는 함수들은 아래처럼 정리할 수 있다.

이렇게 피보나치 수열의 소스코드를 재귀적으로만 작성하면 n이 커짐에 따라 수행시간이 기하급수적으로 늘어나기 때문에 심각한 문제가 발생할 수 있다. 위 코드의 시간 복잡도는 $O(2^N)$ 으로 지수 시간이 소요된다.

이처럼 피보나치 수열의 점화식을 재귀 함수를 사용해 만들 수는 있지만, 단순히 매번 계산하도록하면 문제를 효율적으로 해결할 수 없다. 이러한 문제는 다이나믹 프로그래밍을 이용해 효율적으로 해결할 수 있다. 모든 문제를 다이나믹 프로그래밍을 이용해 해결할 수는 없고, 다음 조건을 만족할 때 사용할 수 있다.

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

메모이제이션 : 연산 결과 저장하기

피보나치 수열은 이 조건을 만족하는 대표 문제이다. 이 문제를 메모이제이션(memoization)이라는 기법을 사용해서, 연산 결과를 저장한다면 중복된 함수의 호출을 막을 수 있다. 한 번 구한 결과를 메모리 공간에 저장해두고, 같은 식을 다시 호출하면 저장했던 결과를 그대로 가져오는 기법이다.

Top-Down

아래 코드는 재귀 함수를 활용한 피보나치 코드에 메모이제이션 기법을 더해 연산량을 줄인 코드이다.

cash = [ 0 for i in range(100) ]

def fibo(n):
	if n <= 2:
    	return 1
    if cash[n] != 0:
    	return cash[n]
    cash[n] = fibo(n-1) + fibo(b-2)
	return cash[n]

해당 코드의 시간 복잡도는 $O(N)$ 이다. 1~N 에 대해 한 번 연산했던 값은 다시 구해지지않기 때문이다.
이처럼 재귀 함수를 이용해 다이나믹 프로그래밍 코드를 작성하는 방법을, 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운 방식이라고 한다.

반면에, 반순히 반복문을 이용하여 소스코드를 작성하는 경우는 작은 문제부터 차근차근 답을 도출한다고 해서 보텀업 방식이라고 말한다.

Bottom-Up

cash = [ 0 for i in range(100) ]

def fibo(n):
    
	cash[1] = 1, cash[2] = 1
	for i in range(3, n+1):
    	cash[i] = cash[i-1] + cash[i-2]
        
     return cash[n]

Tip

특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인해보자. 또한, 가능하다면 탑다운 방식보다는 보텀업 방식으로 구현하는 것을 권장한다. 함수 호출에 대한 오버헤드가 존재하며, 시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문이다.

reference

이것이 취업을 위한 코딩 테스트다 with 파이썬