동적 계획법 알고리즘에 들어가기 앞서 Python이라는 언어는 동적인 언어라는 것을 인지하고 있으면 편합니다. Python은 C, C++처럼 변수의 자료형을 지정하지 않고 단순히 선언하는 것만으로도 값을 지정할 수 있으며, 변수의 자료형은 코드가 실행되는 시점에서 결정됩니다.
프로그래밍에서 정적(Static)과 동적(Dynamic)
정적과 동적의 차이점은 쉽게 말해서
정적(Static) - 한 번 정해놓으면 쉽게 변하지 않는 성질
동적(Dynamic) - 상황에 따라서 쉽게 변하는 성질
이라고 할 수 있습니다.
x = 10
print(type(x))
x = '10'
print(type(x))
>>> <class 'int'>
>>> <class 'str'>파이썬은 위와 같이 단순히 값을 다르게 선언하는 것 만으로도 동적인 모습을 보여줍니다.
동적 계획법(DP, Dynamic Programming)
동적 계획법은 하나의 문제를 여러 하위 문제로 나누어 풀면서 최종 목적에 도달하는 문제 해결 방식입니다.
이 알고리즘을 활용하면 똑같은 문제라고 할지라도 불필요한 반복적인 계산이 줄어들어 수행시간이 짧아지게 됩니다.
주로 동적계획법을 사용하는 문제에는 2가지 형태가 존재합니다.
1) Overlapping Subproblems(겹치는 부분 문제)
- 풀고자 하는 문제에 동일한 작은 문제들이 반복하여 나타나는 경우에 사용할 수 있는가?
2) Optimal Substructure(최적 부분 구조)
- 큰 문제를 작은 문제로 나눌 수 있고, 그 작은 문제들의 답으로 큰 문제를 해결할 수 있는가?
위 2가지 형태가 있는 문제일 때 일반적인 풀이보단 동적 계획법으로 풀 때 수행 시간을 짧게 가져갈 수 있습니다.
대체로 위의 2가지 형태를 설명하는데 제가 공부하면서 느낀바로는 "전에 했던 행동을 기억하면서 풀어나가는 방법"이라고 생각하면 이해하기 쉬운거 같습니다.
그러면, 이 동적계획법을 활용한 피보나치 수 구해보겠습니다.
피보나치 수
위와 같은 형태로 증가하는 수열을 피보나치 수열이라고 합니다.
이를 코드로 구현하면 아래처럼 구현할 수 있습니다.
def f(x):
if x == 0:
return 0
elif x == 1:
return 1
else:
return f(x-1) + f(x-2)위의 코드는 재귀라는 특성을 활용하여 피보나치 수를 표현한 것입니다.
예를 들어 X가 4일 때는,
다음과 같이 구현되는 것을 알 수 있습니다.
이처럼 재귀 함수를 이용해 코드를 구현하면 반복되는 값이 많아져 프로그램 구현 시간이 길어집니다.
동적 계획법은 이처럼 반복되는 코드의 구현 시간을 줄이는 경우로 많이 사용되어집니다.
대표적인 동적 계획법은 Top-down(상향식), Bottom-up(하향식)으로 두 가지 방식이 있는데 이를 이용해 피보나치 수를 풀어보겠습니다.
Top-down (하향식)
동적 계획법의 첫 번째 방식은 Top-down방식이며 하향식 방식이라고도 합니다.
위의 방식은 앞서 보여드린 재귀 함수 + 메모이제이션(Memoization)을 같이 써서 코딩합니다.
아래의 코딩에서 n번째 피보나치 수를 구하기 위해 dp 리스트에 계산된 값을 순차적으로 저장합니다.
이러한 방식을 쓰게 되면, n이 커질수록 메모리도 같이 증가하는 단점이 있으나, 수행 속도는 빠르게 가져갈 수 있습니다.
Memoization - 동일한 계산을 반복할 때, 이전의 계산한 값을 메모리에 저장함으로써
반복 수행을 제거하여 프로그램의 실행 속도를 빠르게 하는 기술입니다.
Top-down에서 n번째 피보나치 수를 구하기 위해선
"f(n) = f(n-2) + f(n-1)"과 같은 점화식을 먼저 호출하고 f(0)의 상태까지 내려가는 방식입니다.
이때, 이미 계산을 완료한 값은 dp리스트에 기억되어 있기 때문에 단순한 재귀 함수를 사용하는 것보다 수행 속도를 빠르게 가져갈 수 있습니다.
n = int(input()) # 구하고자 하는 n번째 피보나치 수
dp = [0] * (n+1) # 한 번 계산된 결과를 기억하기 위한 리스트
def Topdown(x):
if x == 0: # 0번째 피보나치 수 = 0
return 0
elif x == 1: # 1번째 피보나치 수 = 1
return 1
if dp[x] != 0: # 이미 계산된 n번째 수
return dp[x]
dp[x] = Topdown(x-1) + Topdown(x-2) # 피보나치 계산
return dp[x] # 계산된 값 리턴위의 식은 Top-down방식을 활용해서 피보나치 수를 구현해 보았습니다.
피보나치 수의 0번째와 1번째는 알고 있기 때문에 따로 dp리스트에 넣지 않고 바로 출력을 해주었고,
2번째 수부터는 계산식에 의해 계산이 되어 dp에 저장이 됩니다.
- '# 피보나치 계산' 밑에 print(dp)를 넣어주시면 직관적인 수행과정을 볼 수 있습니다.
Bottom-up (상향식)
두 번째 방식인 Bottom-up방식은 반복문으로 구현이 가능합니다.
Topdown과 같이 dp리스트에 수행과정을 기억 및 저장한다는 부분은 비슷하지만, Bottom-up은 아래에서 위
'f(0)에서 시작해서 f(n)'한다는 상향하는 방식을 가지고 있습니다.
n = int(input()) # 구하고자 하는 n번째 피보나치 수
dp = [0, 1] # 미리 0, 1번째 수 입력
def Bottomup(x):
for i in range(2, x+1) # 0, 1번째를 제외한 2번째 ~ x번째 까지 반복
dp.append(dp[i-1] + dp[i-2]) # 피보나치 수 계산
return dp[x] # 계산된 값 리턴위의 식은 Bottom-up방식을 활용해서 피보나치 수를 구현해 보았습니다.
dp리스트에 미리 0,1번째 수를 넣어 리스트를 구현했고, 나머지는 for문을 이용한 반복문으로 구현이 가능합니다.
이항 계수 동적 계획법
동적 계획법은 피보나치뿐만 아니라 다른 부분에서 많이 사용되는데, 그중 하나인 이항 계수도 한 번 풀어보겠습니다.
이항 계수는 밑의 그림처럼 간단히 표현할 수 있는데 이를 파스칼 삼각형이라고도 합니다.
보시는 것과 같이 1이 양쪽 끝에 반복되고 그 전의 숫자들을 이용해 다음 숫자를 찾기 때문에 반복성이 있어 동적 계획법으로 푸는 것이 좋다고 볼 수 있습니다.
n, k = map(int, input().split())
dp = [[1 for _ in range(k+1)] for _ in range(n+1)]
for i in range(1, k+1):
for j in range(i+1, n+1):
dp[j][i] = (dp[j-1][i-1] + dp[j-1][i])위의 식은 nCk의 위치한 숫자를 알기 위해 동적 계획법으로 이항 계수를 정리한 코드입니다.
dp는 양쪽에 1을 고정시키기 위해 처음부터 1을 반복해주어 만들었습니다.
위 식에 n, k = 4, 4를 대입해 보면,
dp = [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 2, 1, 1, 1], [1, 3, 3, 1, 1], [1, 4, 6, 4, 1]]
n, k = 4, 3을 대입하면
dp = [[1, 1, 1, 1], [1, 1, 1, 1], [1, 2, 1, 1], [1, 3, 3, 1], [1, 4, 6, 4]]
dp는 다음과 같이 필요한 부분만큼의 메모리를 차지한다는 장점이 있는 코딩입니다.
마치며
동적 계획법은 모든 해를 일일이 확인하며 최적의 해를 찾는 알고리즘이지만, 모든 해를 다 찾는다는 점에서 시간이 걸리는 단점도 있습니다.
하지만 수행 속도를 줄이거나, 반복성이 있는 코드를 짤 때 자주 사용하는 코드이므로 익혀두면 좋은 것 같습니다.
