컴퓨터는 사람이 현실적으로 해결하기 어려운 문제를 해결해준다.
하지만, 시간이 너무 많이 필요하거나, 메모리 공간이 너무 많이 필요한 문제는
컴퓨터도 해결하기 어렵다.
때문에, 우리는 연산 속도와 메모리 공간을 최대한 활용할 수 있는 알고리즘을 작성해야 한다.
다이나믹 프로그래밍(동적 계획법)은 메모리 공간을 약간 더 사용하여,
연산 속도를 비약적으로 증가시킨다.
즉, 일반적으로 컴퓨터 공학에서 사용되는 동적(Dynamic)과 크게 관련이 없다고 생각한다.
피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정한다.
f(3) = f(2) + f(1)
점화식을 재귀 함수를 사용해 쉽게 작성할 수 있다.
def fibo(n):
if n == 1 or n == 2: return 1
return fibo(n-2) + fibo(n-1)f(2)와 f(1)은 항상 1이기 때문에, 호출을 멈춘다. (Base)
이렇게 간단하게 작성할 수 있지만, 심각한 문제가 생길 수 있다.
이 코드의 시간 복잡도는 O(2^N)으로 N이 30이면, 10억 가량의 연산을 수행해야 한다.
연산시간이 기하급수적으로 늘어나는데, 6일 때 호출 과정을 살펴보면, 비효율성을 알 수 있다.
f(6) => f(5)+f(4)
f(5) => f(4)+f(3) f(4) => f(3)+f(2)
f(4) => f(3)+f(2) f(3) => f(2)+f(1) f(3) => f(2)+f(1)
f(3) => f(2)+f(1)
f(3)만 3번이 호출된다. n이 커질수록 반복해서 호출하는 횟수도 많아진다.
위와 같이, 단순히 매번 계산하도록 하면 문제를 효율적으로 해결할 수 없다.
다음 조건을 만족한다면, 다이나믹 프로그래밍을 사용한다.
1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 답은, 그것을 포함하는 큰 문제에서도 동일하다.
피보나치 수열을 다이나믹 프로그래밍 중 하나인 메모이제이션 기법을 사용하여 해결한다.
메모이제이션 기법은 결과를 저장하고, 같은 호출은 저장한 값을 사용하여, 캐싱이라고도 한다.
한번 계산된 결과는 다시 계산 할 필요 없이 저장하고 사용하면 된다.
# 저장하기 위한 리스트
d = [0] * 100
def fibo(n):
if n==1 or n==2: return 1
# 저장되어 있다면
if d[n] != 0 : return d[n]
#아니라면 저장하고 반환
d[n] = fibo(n-1) + fibo(n-2)
return d[n]정리하면, 큰 문제를 작게 나누고, 작게 나눈 문제가 같은 문제라면 한번만 풀어, 저장하여 사용한다.
예시처럼 재귀 함수를 이용해, 큰 문제 해결을 위해 작은 문제를 호출하는 것을 탑다운 방식 이라고 한다.
반복문을 사용하여, 작은 문제부터 답을 도출하는 것을 바텀업 방식 이라고 한다.
피보나치 수열 문제를 바텀업 방식으로 풀면 다음과 같다.
d = [0] * 100
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])시간복잡도는 O(N)으로 동일하나
코딩테스트 에서, 시스템상 재귀함수의 스택 크기가 한정되어 있을 수 있으므로,
바텀업 방식 구현이 유리하다.
완전 탐색으로 접근했을 때, 시간이 오래 걸린다면,
다이나믹 프로그래밍이 가능한지 확인해본다.
작은 단위로 나눠지고, 작은 문제들이 중복되는지 여부를 확인해본다.
