🤷♀️ Dynamic programming이란?
Dynamic programming이란 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘이다. 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결한다.
🤷♀️ 피보나치 수열
프로그래밍에서는 수열을 배열이나 리스트로 표현할 수 있다.
피보나치 수열은 다음과 같이 정의할 수 있다.
피보나치 수를 f(n)이라할 때, f(1)이나 f(2)를 만나면 호출을 정지한다.
피보나치 수를 재귀 함수로 표현하면 아래와 같다.
# 피보나치 함수를 재귀 함수로 구현
def fibo(x) :
if x == 1 or x == 2 :
return 1
return fibo(x-1) + fibo(x-2)하지만 코드를 위처럼 작성할 경우, n이 커질수록 수행 시간이 기하급수적으로 늘어난다. 빅오 표기법으로 O(2^N)의 시간이 소요된다.
이유는 동일한 함수가 반복적으로 호출되기 때문인데, 예를 들어 f(6)을 생각해보자. f(6)은 f(5)와 f(4)를 호출한다. f(5)는 f(4)와 f(3)을 호출하고 f(4)는 f(3)과 f(2)를 호출한다. 또 f(5)가 호출한 f(4)는 f(3)과 f(2)를 호출한다. 이때 f(3)이 여러 번 호출되는 것을 발견할 수 있다. n이 더욱더 커지면 어떻게 될까? 반복해서 호출하는 수가 훨씬 많아질 것이다.
이러한 문제는 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있다. 다만 다음 조건을 만족할 때 다이나믹 프로그래밍이 사용 가능하다.
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
피보나치 수열은 이러한 조건을 만족하는 대표적인 문제이다. 이 문제를 메모제이션 기법을 사용하여 해결해보자.
👉 메모제이션 기법이란 ?
다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법이다. 값을 저장하는 방법으로 캐싱(Caching)이라고도 한다.
메모제이션을 구현하는 방법은 한 번 구한 정보를 리스트에 저장하기만 하면 된다. 다이나믹 프로그래밍을 재귀적으로 수행하다가 같은 정보가 필요하면 이미 구한 정답을 리스트에서 그대로 가져오면 된다.
# 한 번 계산된 결과를 메모제이션하기 위한 리스트 초기화
d = [0] * 100
# 피보나치 함수를 재귀함수로 구현 (top-down)
def fibo(x) :
# 종료 조건 (1 or 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]재귀함수를 이용해 다이나믹 프로그래밍 소스코드를 작성하는 방법을, 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운(Top-Down) 방식이라고 한다.
재귀 함수를 사용하면 메모리 상에 적재되는 일련의 과정을 따라야 하므로 오버헤드가 발생할 수 있다. 따라서 반복문을 이용한 다이나믹 프로그래밍을 사용하여 오버헤드를 줄인다. 다이나믹 프로그래밍을 적용했을 때의 시간 복잡도는 O(N)이다. f(1) 값이 f(2)를 푸는 데 사용되고, f(2)의 값이 f(3)을 푸는 데 사용되는 방식이기 때문이다.
# 앞서 계산된 결과를 저장하기 위한 DP 테이블
d = [0] * 100
d[1] = 1
d[2] = 1
n = 99
# 피보나치 함수를 반복문으로 구현 (Bottom-Up)
for i in range(3, n + 1) :
d[i] = d[i-1] + d[i-2]Top-Down 방식은 '하향식'이라고도 하며, Bottom-up 방식은 '상향식'이라고도 한다. DP의 전형적인 형태는 Bottom-up 방식이다. Bottom-up 방식에서 사용되는 결과 저장용 리스트를 'DP 테이블'이라고 부르며, 메모제이션은 Top-Down 방식에 국한되어 사용되는 표현이다. DP와 메모제이션은 다른 개념이라는 것을 기억해두자.
✔ 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하기
특정 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸린다면, 다이나믹 프로그래밍을 적용할 수 있는지와 해결하고자 하는 부분 문제들의 중복 여부를 확인해보자.
일단 단순히 재귀 함수로 비효율적인 프로그램을 작성한 뒤, 메모제이션을 적용할 수 있으면 (작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면) 소스코드를 수정하는 것도 좋은 방법이다. 하지만 가능하다면 Top-Down 방식보다는 Bottom-Up 방식으로 구현하는 것을 권장한다.
Reference
『이것이 코딩 테스트다 with 파이썬』, 나동빈 지음
