[ BAEKJOON ] No. 10870 : 피보나치 수 5

문제 ) 

https://www.acmicpc.net/problem/10870

10870번: 피보나치 수 5

 

 

풀이 )

< 피보나치 수열 >

F(0) =0 ,   F(1) =1
F(n)= F(n-1) + F(n-2) 

 

피보나치 수열을 재귀 함수를 통해 구현하면 중복계산이 많아짐으로 수행속도가 매우 느려진다. 

그러므로,  for문을 이용해 피보나치 수열을 구현하는 것이 더 효과적!!

 

 

- python code 1 ( Recursive )

# Solution 1 ) 재귀함수로 피보나치 수열 구하기
def findfib(n):
    if n<=1:
        return n 
    else:
        fib=findfib(n-1)+findfib(n-2)
        return fib

N=int(input())
print(findfib(N))

 

 

- python code 2 ( Iterative )

# Solution 2 ) 배열과 for문 이용해서 피보나치 수열 구하기
def findfib_iter(n):
    fiblist=[0,1]
    for i in range(2,n+1):
        fib=fiblist[i-1]+fiblist[i-2]
        fiblist.append(fib)
    return fiblist[n]    

N=int(input())
print(findfib_iter(N))