해당 포스팅은 "이것이 취업을 위한 코딩 테스트다 with 파이썬" 책을 기반으로 포스팅 하였습니다. ✍️✍️
다이나믹 프로그래밍
연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 짜도록 해야한다.
어떤 문제에 대해 약간의 메모리를 더 사용함으로써, 연산 속도를 매우 증가시킬 수 있는 다이나믹 프로그래밍 기법(동적 계획법)이 있다. 이를 개념적으로 설명하자면, 큰 문제를 중복이 일어나지 않는 작은 문제들로 나누어 푸는 방식이다. 이때, 작은 문제들이 반복하는 경우에 해당 문제에 대한 정답이 동일하다. 따라서 한번 계산한 작은 문제들을 각각 저장을 해놓고 나중에 반복이 될 때 다시 사용할 수 있도록 한다. 이를 메모이제이션(Momoization)이라고 한다.
이 다이나믹 프로그래밍은 탑다운(Top-down)과 보텀업(Bottom-up)으로 2가지의 방식이 있다.
-
탑다운(Top-down)
일반적으로 재귀함수로 구현
큰 문제를 풀다가 작은 문제가 풀리지 않았을 때, 해당 문제를 해결하는 방식
-
보텀업(Bottom-up)
작은 문제부터 해결해나가는 방식
이 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 문제로는 피보나치 수열이 있다.
피보나치 수열은 이전 두 항의 합을 현재의 항으로 갖는 수열이다. 이를 점화식을 이용하여 간결하게 표현하면 다음과 같다.
-
n번째 피보나치 수 = (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수
-
단, 1번째 피보나치 수, 2번째 피보나치 수 = 1
프로그래밍에서 이러한 수열을 배열 또는 리스트로 표현할 수 있다. 수열은 여러 개의 수가 규칙에 따라 배열된 형태이기 때문이다. 파이썬의 경우에는 보통 리스트 자료형으로 이를 처리한다.
이 피보나치 함수를 재귀함수로 작성한 코드는 다음과 같다.
# 피보나치 함수를 재귀함수로 구현
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x-1) + fibo(x-2)
print(fibo(4))그러나 위 소스코드는 f(n)에서 n이 커지면 코드 수행시간이 기하급수적으로 늘어난다는 문제점이 있다. 일반적으로 O(2N)의 지수 시간이 소요된다고 볼 수 있다. 예를 들어 N=30이면, 약 10억 가량의 연산을 수행해야 한다.
f(6)일 때의 호출과정을 시각적으로 표현하면 다음과 같다.
이를 보면, 이미 계산이 되었던 함수들도 여러번 반복 호출이 되는 것을 확인할 수 있다.
이런 불필요한 연산은 f(n)에서 n이 커질수록 매우 많아지게 된다.
이러한 반복되는 연산을 저장하기위해 메모이제이션을 사용하는데, 이는 한번 구한 정보를 리스트에 저장하는 방식으로 구현한다. 이에 대한 파이썬 코드는 다음과 같다.
# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
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)) 재귀 함수 대신에 반복문을 사용할 수 있다. 일반적으로 재귀함수보다 반복문을 이용한 다이나믹 프로그래밍이 더 성능이 좋다. 이 다이나믹 프로그래밍의 시간복잡도는 O(N)이다.
각각의 문제에 대해 한번씩만 계산이 되기 때문이다.
반복문을 사용하여 피보나치 수열을 해결하는 파이썬 코드는 다음과 같다.
# 앞서 계산된 결과를 저장하기 윈한 DP 테이블 초기화
d = [0] * 100
d[1] = 1
d[2] = 1
n = 99
# 피보나치 함수를 반복문으로 구현 (보텀업 다이나믹 프로그래밍)
for i in rane(3, n+1):
d[i] = d[i-1] + d[i-2]
print(d[n])보텀업 방식에서 사용되는 결과 저장용 리스트를 'DP 테이블'이라고 부른다.
메모이제이션을 사용 시, 일부의 문제에 대해서만 저장된 결과가 필요한 경우에는 사전 자료형을 사용하면 더 효과적이다.
