[Python] 피보나치 구현 정리

피보나치를 구현하는 방법에 대해 정리

 

1. 기본 재귀

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

 

2. bottom up 방식

def fibo(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    memo = [0] * (n + 1)
    memo[1] = 1

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

위 코드는 공간 복잡도가 n이 커짐에 따라 선형적으로 증가하기 때문에 O(n)

 

3. bottom up 방식 + 공간 복잡도 효율

def fibo(n):
    if n == 0:
        return 0
    memo = [0, 1]
    for _ in range(2, n + 1):
        memo = [memo[-1], memo[-1] + memo[-2]]
    return memo[-1]

이 방식대로 하면 n이 커져도 공간 복잡도는 동일하기 때문에 O(1)

 

4. bottom up 방식 + 공간 복잡도 효율++

def fibo(n):
    if n == 0:
        return 0
    memo = (0, 1)
    for _ in range(2, n + 1):
        memo = (memo[-1], memo[-1] + memo[-2])
    return memo[-1]

리스트가 아닌 튜플로 선언하게 되면 효율이 더욱 증가하게 된다.

왜 그럴까?

리스트와 튜플의 차이는 mutable, immutable이다.

즉 리스트는 append, pop과 같은 메서드가 구현되어 있는데(수정 가능하니깐) tuple은 그런 기능이 없다.

 

그거랑 공간 효율이랑 무슨상관이지?

python에서 list(python의 리스트는 동적 배열) 구현할 때 요소 추가 동작을 빠르게 수행할 수 있도록 더 많은 공간을 저장해둔다.

반면에 tuple은 불변의 객체이기 때문에 이러한 작업이 필요 없기 때문에 더 효율적인 것.

 

이런 이유 때문에 python 함수 파라미터에 *args로 값을 받아오면 이는 tuple로 받게 되어있다.

def tuple_immutable(*args):
    print(type(args))
    print(args)

tuple_immutable(1,2,3,4,'123')

결과

 

5. Top down 방식 memoization

memo = dict()
def fibo(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n - 1 not in memo:
        memo[n-1] = fibo(n-1)
    if n - 2 not in memo:
        memo[n-2] = fibo(n-2)
    return memo[n-1] + memo[n-2]

 

6. LRU 캐시 데코레이터 활용

from functools import lru_cache
import sys
sys.setrecursionlimit(int(1e6))
@lru_cache(maxsize=None)
def fibo(n):
    if n < 2:
        return n
    return fibo(n-1) + fibo(n-2)

print(fibo(1000))

캐시는 기존에 나왔던 값을 저장하는 기술인데 이를 python에서 데코레이터로 구현해 놓음

데코레이터란? 어떤 함수에 추가적인 기능을 덧붙일 때 사용하는 함수

python 3.9 버전 이상에선 cache라는 데코레이터도 functools에 구현이 되어 있다고 한다.