피보나치 함수

백준 1003

다이나믹 프로그래밍은 시간, 메모리가 많이 필요한 경우에 하위 문제를 풀고 결과를 기록하고 문제를 해결하는 방식이다. 이제 막 동적계획법에 대해 공부를 진행한 만큼 문제를 더 많이 풀어봐야할 것 같다.

방법1. dynamic programming

---

n = int(input())
 
zero = [1,0]
one = [0,1]
 
def fibo(a):
    if len(zero) <= a:
        for i in range(len(zero), a+1):
            zero.append(zero[i-1] + zero[i-2])
            one.append(one[i-1] + one[i-2])
    print(zero[a], one[a])
 
for i in range(n):
    a = int(input())
    fibo(a)

함수 없이 하기

t = int(input())

dp_o = [1,0]
dp_l = [0,1]

for _ in range(t):
    n = int(input())
    if len(dp_o) <= n:
        for i in range(len(dp_o), n+1):
            dp_o.append(dp_o[i-1]+dp_o[i-2])
            dp_l.append(dp_l[i-1]+dp_l[i-2])
    print(dp_o[n], dp_l[n])   

0을 참조하는 숫자끼리 피보나치 수열을 이루고
1을 참조하는 숫자들도 피보나치 수열을 이루므로 각각의 dp테이블을 만들었다.

동적계획법

시간, 메모리가 많이 필요한 경우에 하위 문제를 풀고 결과를 기록하고 문제를 해결하는 방식.

피보나치를 재귀함수로 구현할 경우 어마어마하게 많은 시간이 걸리기 때문에 0을 참조하는 수를 나타내는 zero리스트와
1을 참조하는 수를 나타내는 one리스트를 메모하였다.
둘다 입력받은 값이 0과 1일때까지만 나타나있다.
fibo함수를 구현해보면, 입력받은 값보다 zero리스트 혹은 one리스트 길이가 작거나 같으면 a라는 수에 대한 메모가 없다는 뜻이므로 비어있는 만큼 채워준다.
그 후 원래 알고자 했던 zero[a]와 one[a]를 출력한다.

참고