본 글은 “이것이 취업을 위한 코딩 테스트다 with 파이썬” 교재를 참고한 것임
메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가시킬 수 있는 방법이다.
점화식에 따라서 피보나치 수를 구하는 과정을 표현해보자. n 번째 피보나치 수를 f(n)이라고 표현할 때, f(4)를 구하려면 다음과 같이 함수 f를 반복해서 호출할 것이다. f(2)와 f(1)은 항상 1이기 때문에 f(2)이나 f(1)을 만났을 때는 호출을 정지한다.
수학적 점화식을 프로그래밍으로 표현하려면 재귀 함수를 사용하면 간단하다.
1
2
3
4
5
6
7
# 피보나치 함수( 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)$의 지수 시간이 소요된다고 한다.
f(6)을 구할 때, 동일한 함수가 반복적으로 호출되는 것을 볼 수 있다. 이미 계산됐지만 호출할 때마다 계산하는 것이다. f(n)에서 n이 커질수록 반복해서 호출하는 수가 많아진다.
이처럼 피보나치 수열의 점화식을 재귀 함수를 사용해 만들 수는 있지만, 단순히 매번 계산하도록 하면 문제를 효율적으로 해결할 수 없다. 이러한 문제는 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있다.
항상 사용할 수는 없으며 다음과 같은 조건을 만족해야 가능하다.
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
피보나치 수열은 조건을 만족하며, 이 문제를 메모이제이션(Memoization) 기법을 사용해서 해결해보자. 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법이다. 캐싱(Caching)이라고도 한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 한 번 계산된 결과를 메모이제이션( 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 ))
99번째 피보나치인데도 불구하고 금방 정답을 도출하는 것을 알 수 있다.
정리하자면 다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.
사실 큰 문제를 작게 나누는 방법은 퀵 정렬에서 본 적이 있다. 퀵 정렬은 정렬을 수행할 때 리스트를 분할하며 전체적으로 정렬이 될 수 있도록 하는 분할 정복(Divide and Conquer) 알고리즘으로 분류된다. DP와 분할 정복의 차이점은 DP는 문제들이 서로 영향을 미치고 있다는 점이다.
퀵 정렬을 예로 들면, 한 번 기준 원소(피벗)이 자리를 변경해서 자리를 잡게 되면 그 기준 원소의 위치는 더 이상 바뀌지 않고 그 부분을 다시 처리하는 부분 문제는 존재하지 않는다. 반면에 DP는 한 번 해결했던 문제를 다시금 해결한다는 점이 특징이다.
그렇기 때문에 이미 해결된 부분 문제에 대한 답을 저장해 놓고 이 문제는 이미 해결됐던 것이니까 다시 해결할 필요가 없다고 반환하는 것이다. 예를 들어 재귀 함수를 이용하는 방법(메모이제이션)에서 한 번 푼 문제는 그 결과를 저장해 놓았다가 나중에 동일한 문제를 풀어야 할 때 저장한 값을 반환한다.
f(6)을 메모이제이션으로 그려보면 위 그림처럼 색칠된 노드만 방문하게 된다. 함수가 종료될 때 어떤 함수를 호출했는지 출력하는 코드는 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
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 )
이처럼 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을, 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운(Top-Down) 방식이라고 한다.
반면 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 답을 도출한다고 하여 보텀업(Bottom-Up) 방식이라고 한다. 보텀업 방식은 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
# 앞서 계산된 결과를 저장하기 위한 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의 형태는 보텀업 방식이며, 여기서 사용되는 결과 저장용 리스트를 DP 테이블이라고 한다.
메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미하므로, 다이나믹 프로그래밍과는 별도의 개념이다. 한 번 계산된 결과를 어딘가에 담아 놓기만 하고 다니아믹 프로그래밍을 위해 활용하지 않을 수도 있다.
코딩 테스트에서 다이나믹 프로그래밍
코딩 테스트에서의 DP 문제는 대체로 간단한 형태로 출제된다.
다이나믹 프로그래밍 문제를 푸는 첫 번째 단계는 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이다.
특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인해보자.
일단 단순히 재귀 함수로 비효율적인 프로그램을 작성한 뒤에(탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 즉 메모이제이션을 적용할 수 있으면 코드를 개선하는 것도 좋은 방법이다.
또한 재귀 함수 스택 크기가 한정되어 있을 수 있기 때문에 가능하다면 탑다운 방식 보다는 보텀업 방식으로 구현하는 것을 권장한다.