[BOJ백준 1003번] 피보나치 함수 with 파이썬

오늘은 다이나믹 프로그래밍 문제 중 가장 기초적인 문제 중 하나를 풀어봤습니다.

다이나믹 프로그래밍은 큰 문제를 작은 문제들로 해결할 수 있는 경우 사용할 수 있는 알고리즘 기법입니다. 

 

접근

1003번에서는 f(0)과 f(1)이 호출되는 횟수를 구하라고 합니다. 제한시간을 보시면 0.25초 입니다. 문제에 나와 있는대로 재귀함수로 구성하면 100% 시간이 부족합니다. 왜냐하면 그림대로라면 O(2^n)의 시간복잡도를 가지고 있는데 (이는 함수 호출을 그래프로 그리면 답이 나옵니다.) n은 40이하입니다. 2^40은 대략 1000000000000 입니다.  10억의 연산을 1초로 수행한다고 하면 0.25초를 훨씬 초과합니다. 

 

이때 적용할 수 있는 방법은 다이나믹 프로그래밍, 동적 계획법입니다.

그 중에서도 bottom up 방식으로 문제를 풀면 매우 빠르게 문제를 해결할 수 있습니다.

 

방식

dp로 문제를 해결하기로 정했습니다. n이 40 이하이고, 이는 작은 숫자이니 리스트를 생성하고 인덱스 40까지 bottom up 방식으로 값을 채워나가면 좋겠다고 생각했습니다.

 

f(1) 호출횟수의 경우는 인덱스가 0이면 0, 1이면 1입니다. f(2)부터는 f(1) + f(0)의 형식이기 때문에 쉽게 구할 수 있습니다.

 

구현

따라서 저는 아래와 같이 구현을 하였습니다.

d0 = [0]*41
d1 = [0]*41

d0[0] = 1
d1[1] = 1


for i in range(2,41):
  d0[i],d1[i] = d0[i-1]+d0[i-2],d1[i-1]+d1[i-2]

t = int(input())
s = ''

for i in range(t):
  n = int(input())
  s += str(d0[n])+' '+str(d1[n])+'\n'

print(s)