[Python] 피보나치(Fibonacci) 수열 구하기

---

Python으로 피보나치(Fibonacci) 수열 구하기 (DP, 재귀)

DP, Recursion(재귀) 모두에서 기본 문제로 꼽히는 피보나치 수열을 구해보고, 걸리는 시간을 실제로 비교해보자!

 

 

 

Recursion(재귀) 방식

---

def recursion_fibo(n):
    return 1 if n<=2 else recursion_fibo(n-2) + recursion_fibo(n-1)

 

• 굉장히 심플하게 구현이 가능하다.
  
  
• n이 2보다 작으면 1을 반환하고, 그 외의 경우에는 n-2와 n-1을 더하는 식으로 재귀를 진행한다.
  
  
• 원래 가독성 생각하면 if문 넣고 이쁘게 짜도 되는데, 요즘 쓸데 없는 겉멋이 들어서 짧게 코딩하는데에 맛이 들려버렸다.
  
  
• 해당 방식의 문제점은, 이미 구했던 값을 다시 구하는 반복 연산이 굉장히 많다는 것이다.
  
  
• 시간복잡도가 무려 2^n이며, n이 조금만 커져도 값을 계산할 수 없을 지경의 연산량을 가진다.
  

 

DP(Dynamic Programming) 방식

---

def dp_fibo(n):
    dp = [0] * (n+1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n+1):
        dp[i] = dp[i-2] + dp[i-1]
    return dp[n]

 

• 마찬가지로 간단하게 구현이 가능하다.
  
  
• dp table을 만들고, 처음 값 0과 1만 넣어준다. 그 다음부터는 for문을 돌면서 계산을 진행한다.
  
  
• 이미 한 번 구한 값은 다시 연산하지 않으므로 연산량이 크게 감소한다. 
  
  
• 시간복잡도 O(N)을 가진다.
  
  

 

실제 동작 시간 비교

---

import time

def recursion_fibo(n):
    return 1 if n<=2 else recursion_fibo(n-2) + recursion_fibo(n-1)

def dp_fibo(n):
    dp = [0] * (n+1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n+1):
        dp[i] = dp[i-2] + dp[i-1]
    return dp[n]

start = time.time()
print(f"Fibonacci at 40 with Recursion : {recursion_fibo(40)}, Time : {time.time() - start:.16f}sec")
start = time.time()
dp_fibo(10000)
print(f"Fibonacci at 10000 with Dynamic Programming : ..., Time : {time.time() - start:.16f}sec")


# 결과
# Fibonacci at 40 with Recursion : 102334155, Time : 10.0029354095458984sec
# Fibonacci at 10000 with Dynamic Programming : ..., Time : 0.0030002593994141sec

 

• 재귀 방식의 경우 fibo(40)을 구하는데 무려 10초의 시간이 걸렸다.
  
  
• DP 방식의 경우 fibo(40)을 구하는데에는 0.1ms조차도 안걸려서 표시가 되지 않아, 10000에서 실험해보았더니, 
  대략 3ms 정도 소요되는 것을 확인할 수 있었다.
  
  
• DP의 중요성을 알게 해주는 대표적인 사례이다.