다이나믹 프로그래밍이란?
우리가 컴퓨터를 활용해도 해결하기 어려운 문제는 대표적으로 최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 많이 필요하는 문제이다.
그래서 우리는 연산 속도와 메모리 공간을 최대한으로 활용해하는 효율적인 알고리즘을 작성해야 한다.
어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있는데 이것이 바로 Dynamic Programming이다.
다이나믹 프로그래밍으로 해결할 수 있는 대표적인 문제는 피보나치 수열이다. 다음은 피보나치 수열에 대한 그림이다.
수학자들은 점화식을 이용해 수열의 항이 이어지는 형태를 간결하게 표현한다. 우리는 점화식을 이용해 현재의 항을 이전의 항에 대한 식으로 표현할 수 있다.
다음은 피보나치 수열에 대한 점화식이다.
첫 번째 항과 두 번째 항의 값은 모두 1이다.
프로그래밍에서는 이런 수열을 배열이나 리스트로 표현할 수 있다.
이 점화식을 이용하여 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)
하지만 피보나치 수열을 이렇게 작성하면 심각한 문제가 발생한다. 바로 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어나기 때문이다. 해당 코드의 시간복잡도는 O(2^n)이다. 예를들어 N이 30이면, 약 10억번의 연산을 수행해야 한다.
f(6)일때의 수행과정을 그려보자.
그림을 보면 동일한 함수가 반복적으로 호출되는 것을 알 수 있다. 이미 한 번 계산했지만, 계속 호출할 때마다 계산하는 것이다. 즉 n이 커지면 커질수록 반복해서 호출하는 수가 많아진다.
이처럼 피보나치 수열의 점화식은 재귀 함수를 이용해 간단하게 만들 수 있지만, 문제를 효율적으로 해결할 수 없다. 이러한 문제는 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있다.
다만 항상 다이나믹 프로그램을 사용할 수는 없으며, 다음 조건을 만족해야만 한다.
1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
피보나치 수열은 이러한 조건을 만족하는 대표적인 문제로, 이 문제를 메모이제이션(Memoization) 기법을 사용하여 해결하자.
메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 메모이제이션은 값을 저장하는 방법이므로 캐싱(Caching)이라고도 한다.
그렇다면 실제로 메모이제이션은 어떻게 구현될 수 있을까? 한 번 구한 정보는 리스트에 저장을 하는 것이다. 다이나믹 프로그래밍을 재귀적으로 수행하다가 같은 정보가 필요할 때는 이미 구한 정답을 그대로 리스트에서 가져오면 된다. 이를 소스코드로 표현하면 다음과 같다.
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]
이처럼 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법은 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운(Top-Down)이라 한다.
반면 단순히 반복문을 이용하여 소스코드를 작성하는 경우는 작은 문제부터 차근차근 답을 도출한다고 하여 바텀업(Bottom-Up)이라 한다.
#1로 만들기
#1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
#2. X가 2로 나누어 떨어지면, 2로 나눈다.
#3. 1을 뺀다.
#1로 만드는 연산의 최솟값을 구한다.
n = int(input())
d = [0] * (n+1) #메모제이션
for i in range(2, n+1):
d[i] = d[i-1] + 1 #1을 빼는 거는 디폴트로
if i % 3 == 0:
d[i] = min(d[i], d[i // 3] + 1) #3으로 나누어지면 3으로 나누어진 것과 1을 뺀거중 최솟값.
if i % 2 == 0:
d[i] = min(d[i], d[i // 2] + 1) #2으로 나누어지면 2으로 나누어진 것과 위의 최솟값의 최솟값
print(d[n])