[알고리즘] 피보나치 함수(백준 1003/파이썬)

필요한 개념: 동적계획법

 

동적계획법이란?

영어로는 Dynamic Programming / DP라고 하며 특정 범위까지의 값을 구하기 위해서 각 부분 문제의 구해놓은 답을 저장하고 나중에 중복 되는 수가 나왔을때 전에 구해놓은 답을 가지고와 사용하는 효율적으로 값을 구하는 알고리즘 설계 기법입니다.

<동적 계획법 핵심 기술>
메모이제이션(memoization): 하향식 접근법

컴퓨터 프로그램이 동일한 계산을 반복해야 할때 함수 값을 계산한뒤 계산된 값을 메모리에 저장하여 프로그램 실행 속도를 빠르게 하는 기술입니다.

[문제]

 

[문제해결방법]

피보나치 수는 앞에 두 수를 더하여 그 다음 수를 만들어내는 방식으로

ex) 0+1=1 , 1+1=2 , 1+2=3, 2+3=5, 3+5=8, 

문제를 풀어야 하기 때문에 반복계산을 막기 위해 이전에 계산했던 값을 저장하고 불러오는 식으로 문제를 해결해야 합니다.

 

[코드리뷰]

import sys

#구한 값을 저장해주기 위해 cnt0과 cnt1을 만들어 줍니다.
cnt0 = [1, 0]
#0의 갯수 cnt0=[1, 0, 1, 1, 2, 3]
cnt1 = [0, 1] 
#1의 갯수 cnt1=[0, 1, 1, 2, 3, 5]

for i in range(2, 41):
    cnt0.append(cnt0[i-1]+cnt0[i-2])
    cnt1.append(cnt1[i-1]+cnt1[i-2]) 
    #동적계획법을 사용하여 계산된 값을 리스트에 저장합니다.


T = int(sys.stdin.readline())

for _ in range(T):
    n = int(sys.stdin.readline())
    print(cnt0[n], cnt1[n])

[결과]