파이썬 알고리즘 133번 | [백준 1003번] 피보나치 함수 - dp

단순 재귀로 피보나치 수를 구하면 왜 느릴까요? 함수 호출의 개수가 기하급수적으로 늘어나기 때문입니다.

133. 피보나치 함수

1) 어떤 전략(알고리즘)으로 해결?

2) 코딩 설명

• dp의 메모지에이션 방식을 사용!

<내 풀이>

dp=[0]*41
res=[]
dp[0]=(1,0)
dp[1]=(0,1)
dp[2]=(1,1)
for i in range(3,41):
    dp[i]=(dp[i-1][0]+dp[i-2][0],dp[i-1][1]+dp[i-2][1])
t=int(input())
for i in range(t):
    num=int(input())
    res.append((dp[num][0], dp[num][1]))
for i in res:
    print(i[0],i[1])
    

<다른 분의 풀이 or 내 틀린 풀이, 문제점>

(1) 시간초과 풀이

def fibo(n):
    global zero
    global one
    if n==0 :
        zero+=1
        return 0
    elif n==1 :
        one+=1
        return 1
    elif n==2 : 
        return fibo(0)+fibo(1)
    else :
        return fibo(n-1)+fibo(n-2)

if __name__=="__main__":

    t=int(input())
    for i in range(t):
        zero=0
        one=0
        fibo(int(input()))
        print(zero,one)

<반성 점>

<배운 점>