📚 개념
현실 세계에는 다양한 문제가 있다. 그런데 이 중에서 컴퓨터를 활용해도 해결하기 어려운 문제는 무엇일까? 최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제 등이 컴퓨터로도 해결하기 어려운 문제이다. 컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이라는 점이 많은 제약을 발생시킨다. 그래서 우리는 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다.
다만, 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다. 대표적인 방법이 다이나믹 프로그래밍 기법으로 동적 계획법이라고 표현하기도 한다.
다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. 피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다. 피보나치 수열은 다음과 같은 형태로 끝없이 이어진다.
수학자들은 점화식을 사용해 수열의 항이 이어지는 형태를 간결하게 표현한다. 점화식이란 인접한 항들 사이의 관계식을 의미하는데, 예를 들어 수열 {an}이 있을 때 수열에서의 각 항을 an이라고 부른다고 가정하자. 점화식을 이용해 현재의 항을 이전의 항에 대한 식으로 표현할 수 있다. 예를 들어 피보나치 수열의 점화식은 다음과 같이 표현할 수 있다.
이를 해석하면 다음과 같다.
- n번째 피보나치 수 = (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수
- 단, 1번째 피보나치 수 = 1, 2번째 피보나치 수 = 1
그렇다면 이 점화식에 따라서 실제로 피보나치 수를 구하는 과정을 어떻게 표현할 수 있을까? n번째 피보나치 수를 f(n)이라고 표현할 때 4번째 피보나치 수 f(4)를 구하려면 다음과 같이 함수 f를 반복해서 호출할 것이다. 그런데 f(2)와 f(1)은 항상 1이기 때문에 f(1)이나 f(2)를 만났을 때는 호출을 정지한다.
수학적 점화식을 프로그래밍으로 표현하려면 재귀 함수를 사용하면 간단하다. 예시를 소스코드로 바꾸면 다음과 같다.
📌 예제 코드 - 피보나치 함수
#피보나치 함수를 재귀 함수로 구현
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x-1) + fibo(x-2)
print(fibo(4))⏰ 위 코드의 시간 복잡도
O(2^n)
❗ 참고
피보나치 수열의 소스코드를 위와 같이 작성하면 심각한 문제가 생길 수 있다. 바로 f(n) 함수에서 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어나기 때문이다. 이 소스코드의 시간 복잡도는, 엄밀히 말하면 피보나치 수열의 정확한 시간 복잡도는 빅오 표기법을 이용하여 O(2^n)의 지수 시간이 소요된다고 표현한다. 예를 들어 N = 30이면, 약 10억 가량의 연산을 수행해야 한다.
이처럼 피보나치 수열의 점화식을 재귀 함수를 사용해 만들 수는 있지만, 단순히 매번 계산하도록 하면 문제를 효율적으로 해결할 수 없다. 이러한 문제는 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있다. 다만 항상 다이나믹 프로그래밍을 사용할 수는 없으며, 다음 조건을 만족할 때 사용할 수 있다.
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
피보나치 수열은 이러한 조건을 만족하는 대표 문제이다. 이 문제를 메모이제이션 기법을 사용해서 해결해보자. 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 메모이제이션은 값을 저장하는 방법이므로 캐싱이라고도 한다.
메모이제이션을 구현하는 방법은 한 번 구한 정보를 리스트에 저장하는 것이다. 다이나믹 프로그래밍을 재귀적으로 수행하다가 같은 정보가 필요할 때는 이미 구한 정답을 그대로 리스트에서 가져오면 된다. 이를 소스코드로 나타내면 다음과 같다.
📌 예제 코드 - 메모이제이션
# 한 번 계산된 결과를 메모이제이션 하기 위한 리스트 초기화
d = [0] * 100
def fibo(x):
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))재귀 함수를 이용하는 방법(메모이제이션)에서는 한 번 푼 문제는 그 결과를 저장해 놓았다가 나중에 동일한 문제를 풀어야 할 때 이미 저장한 값을 반환한다. f(6) 해법을 다시 메모이제이션 기법을 이용하여 그려보면 6번째 피보나치 수를 호출할 때는 다음 그림처럼 색칠된 노드만 방문하게 된다.
⏰ 다이나믹 프로그래밍을 적용했을 때의 시간 복잡도
O(N)
왜냐하면, f(1)을 구한 다음 그 값이 f(2)를 푸는 데 사용되고, f(2)의 값이 f(3)를 푸는 데 사용되는 방식으로 이어지기 때문이다. 한 번 구한 결과는 다시 구해지지 않는다. 따라서 실제로 호출되는 함수에 대해서만 확인해보면 다음과 같이 방문한다.
이처럼 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을, 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운 방식이라고 말한다. 반면에 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여 보텀업 방식이라고 말한다.
피보나치 수열 문제를 아래에서 위로 올라가는 보텀업 방식으로 풀면 다음과 같다. 동일한 원리를 적용하되 단순히 반복문을 이용하여 문제를 해결한 것으로 이해하면 된다.
d = [0] * 100
# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99
# 피보나치 함수 반복문으로 구현(보텀업 다이나믹 프로그래밍)
for i in range(3, n+1):
d[i] = d[i-1] + d[i-2]
print(d[n])탑다운(메모이제이션) 방식은 '하향식' 이라고도 하며, 보텀업 방식은 '상향식' 이라고도 한다. 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다.
