피보나치 수열 구현(재귀함수, 동적계획법 활용)

1. 재귀함수 활용

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

print(fibo(7)) # 13 

 

---

 

2. 동적 계획법 활용

def fibo_dp(n):
    cache = [0 for x in range(n+1)]
    cache[0] = 0
    cache[1] = 1

    for x in range(2, n+1):
        cache[x] = cache[x-1] + cache[x-2]
    return cache[n]

print(fibo_dp(7)) # 13

• Memoization(메모이제이션) : 프로그램 실행시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술
  
  
  - 출처: FASTCAMPUS