여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘
→ 문제를 해결하기 위한 점화식을 찾아낸 후 점화식의 항을 밑에서부터 차례로 구해나가서 답을 알아내는 형태의 알고리즘
피보나치 수열은 DP로 해결할 수 있는 문제들 중 하나이다.
(Ex) 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
피보나치 수열을 점화식으로 표현해보자.
수학적 점화식을 프로그래밍으로 표현하려면 단순 재귀함수를 사용하면 간단하다. Python 코드로 작성해보자.
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x - 1) + fibo(x - 2)
print(fibo(4))
>> 3
재귀함수의 호출을 그림으로 표현하면 아래와 같다.
위와 같이 코드를 작성하게 되면 심각한 문제가 생길 수 있다. f(n)
함수에서 n
이 커지면 커질수록 수행 시간이 기하급수적으로 늘어나기 때문이다. 아래 그림을 보자.
f(6)
을 계산할 때에 그림과 같이 f(2)
가 여러 번 호출되는 것을 확인할 수 있다. (중복되는 부분 문제)
즉, 같은 연산을 여러 번 수행하므로 시간 복잡도가 엄청 커지게 된다.
피보나치 수열의 시간 복잡도는 O(2 ** N)
이다.
예를 들어 f(30)
을 계산하기 위해 약 10억번의 연산을 수행해야 한다.
우리는 DP를 사용하면 이러한 문제를 효율적으로 해결할 수 있다.
DP는 항상 사용할 수 없기 때문에 DP의 사용 조건을 만족하는지 확인해보자.
피보나치 수열은 위 2가지 조건을 만족하므로 DP를 사용할 수 있다!
이 문제를 메모이제이션 (Memoization) 기법을 사용해서 해결해보자.
※ 메모이제이션 (Memoization) 이란?
- DP를 구현하는 방법 중 한 종류이다.
- 한 번 구한 결과를 메모리 공간에 메모해두고 --> 같은 식을 호출하면 메모한 결과를 그대로 가져오는 기법이다. (값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 한다.)
# 메모이제이션하기 위한 리스트 초기화
memoization = [0] * 100
# 피보나치 함수를 재귀함수로 구현 (Top-down DP)
def fibo(x):
if x == 1 or x == 2:
return 1
# 이미 계산한 적 있으면 그대로 반환
if memoization[x] != 0:
return memoization[x]
# 계산한 적 없으면 점화식에 따라 피보나치 결과 반환
memoization[x] = fibo(x - 1) + fibo(x - 2)
return memoization[x]
print(fibo(6))
메모이제이션을 사용하여 f(6)
을 구하는 과정은 아래의 그림과 같다.
메모이제이션을 사용하게 되면 그림의 색칠된 노드만 방문하게 된다.
실제 코드에서 호출되는 함수만 보게되면 아래의 그림과 같이 방문한다.
f(6) -> f(5) -> f(4) -> f(3) -> f(2) -> f(1) -> f(2) -> f(3) -> f(4)
DP를 적용했을 때의 피보나치 수열 알고리즘의 시간 복잡도는 O(N)
이다.
왜냐하면 f(1)
을 구한 다음 그 값이 f(2)
를 구하는 데 사용되고,
f(2)
의 값이 f(3)
을 푸는 데 사용되는 방식으로 이어지기 때문이다.
또한, 메모이제이션 때문에 한 번 구한 결과는 다시 구해지지 않는다.
주어진 문제가 DP 유형인지 파악하는 것이 중요
수열은 배열이나 리스트로 표현할 수 있다고 했는데, 메모이제이션은 때에 따라서 다른 자료형, 예를 들어 딕셔너리 자료형을 이용할 수도 있다. --> 사전 자료형은 수열처럼 연속적이지 않을 때 유용하다.
DP를 사용할 때, 일단 단순히 재귀 함수로 비효율적인 프로그램을 작성한 뒤에 (Top-Down) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 즉 메모이제이션을 적용할 수 있으면 코드를 개선하는 방법도 좋은 방법이다.