[Algorithm]_2. 파이썬으로 피보나치수를 구하는 방법들

피보나치수열

이탈리아의 수학자 피보나치는 아라비아에서 발전된 수학을 유럽에 소개하여 유럽 전역에 수학을 발전시키는데 기여하였습니다. 피보나치는 1202년 자신의 저서 Liber abaci 에서 다음과 같은 토기 번식에 문제를 제시하였습니다. 

 

갓 태어난 토끼 암수 한 쌍이 있다. 이 토끼 한 쌍은 태어난 지 두 달이 되는 달부터 매달 암수 한 쌍의 토끼를 낳으며, 새로 태어난 토끼 한 쌍도 태어난 지 두 달이 되는 달부터 매달 아뭇 한 쌍의 토끼를 낳는다. 일 년 후 토끼는 모두 몇 쌍이 될까? (토끼는 중간에 죽지 않는다.)

 

이를 수열로 나타내면 아래와 같습니다.

"1,1,2,3,5,8,13,21..."

 

위와 같이 어떤 수열의 항이, 앞의 두 항의 합과 같은 수열을 레오나르도 피보나치의 이름을 따서 피보나치 수열이라고 합니다. 

알고리즘 입문 문제에 피보나치수열에 대한 문제가 종종 등장하는데요 오늘은 피보나치의 수를 구할 수 있는 방법들에 알아보려고 합니다. 

피보나치 넘버스

 

1. 반복문

가장 기본적으로 사용되고 직관적인 방법입니다. 반복문이 시작되면  a의 값이  b 값으로 변경되며 b 는 a+b 로 변경됩니다. 

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b 
    return a

 

2. 재귀 함수

자기 자신을 호출하는 방법으로 알고리즘 문제에 자주 나오는 방법입니다.

def fib(n):
    if n == 0:
        return 0
    elif n == 1 or n == 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

재귀 함수의 단점은 n이 증가하면 시간 복잡도(O(2n))가 가파르게 증가한다는 점입니다. 이러한 문제를 해결하기 위해 메모이제이션(Memoization)을 적용할 수 있습니다.

 

3. 메모이제이션(Memoization) 

이전에 계산한 값을 저장해 중복된 계산을 하지 않는 방법입니다. 메모이제이션을 통해 재귀 함수의 속도를 대폭 향상할 수 있습니다. 파이썬에서는 functools을 임포트 해 간단히 구현할 수 있습니다. 

from functools import lru_cache


@lru_cache 
def fib(n):
    if n == 0:
        return 0
    elif n == 1 or n == 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

 

이 외에도 다양한 방법이 있겠지만 자주 사용하는 방법들 위주로 정리해보았습니다.