파이썬(Python)으로 피보나치(Fibonacci) 수 구하기

피보나치 수는 첫 번째와 두 번째 값이 1이고 다음부터는 그 전의 수와 그 전전의 수를 더하는 방식입니다.

첫 번째 값이 0으로 시작하는 경우도 있으며 다음과 같은 형태의 수열입니다.

(0), 1, 1, 2, 3, 5, 8, 13,...

2는 처음 1과 그다음의 1을 합쳐서 계산되며, 3 역시 1과 2의 합으로 계산됩니다.

파이썬으로 피보나치 수를 구하는 다양한 방법을 알아보겠습니다.

 

1. 반복문으로 구현

가장 기본적으로 사용되는 방법은 반복문으로 구현하는 방법입니다.

이 방법은 직관적이면서 가장 효율적인 방법입니다.

반복문으로 피보나치 수를 구현한 코드는 다음과 같습니다.

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

간단하게 몇 줄의 코드로 구현이 가능합니다.

0으로 시작해서 첫 번째(n=1)와 두 번째(n=2)에서 1을 리턴하도록 했습니다.

일반적인 프로그래밍의 0으로 시작하는 인덱스와 혼동이 될 수 있기 때문에 0을 추가했습니다.

반복문이 실행될 때마다 _curr 값이 _next 값으로 변경되며 _next는 _curr와 _next의 합으로 변경됩니다.

 

2. 제너레이터 구현

1번 방식과 같이 결과만 전달받는 대신에 n까지의 값을 하나씩 받을 수도 있습니다.

제너레이터를 구현하면 0부터 n번 째 값까지 값을 순차적으로 받을 수 있습니다.

def fib(n):
    _curr, _next = 0, 1
    for _ in range(n + 1):
        yield _curr
        _curr, _next = _next, _curr + _next


fib = fib(5)
for i, val in enumerate(fib):
    print('Fibonacci({}): {}'.format(i, str(val)))

반복문을 통해 호출하면 순차적으로 피보나치 수열의 값을 가져올 수 있습니다.

제너레이터 구현

각각의 피보나치 수열의 값을 반복문 호출마다 가져오는 것을 확인할 수 있습니다.

 

3. 재귀 함수로 구현

재귀 함수를 통해 피보나치 수열을 구하는 것도 가능합니다.

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

여기서도 0부터 시작하는 피보나치를 사용해서 n이 1이나 2일 때 1을 리턴하도록 작성했습니다.

재귀 함수의 베이스 조건을 추가해주고 피보나치의 특성인 이전 값과 전전 값을 더해서 값을 구합니다.

재귀 함수에 대한 자세한 설명은 아래 링크에서 확인 가능합니다.

2014/12/04 - [Programming/C&CPP] - 재귀 함수 & 재귀적 함수호출(recursive function call)

재귀 함수 & 재귀적 함수호출(recursive function call)

재귀 함수의 단점은 n이 증가하면 시간 복잡도(O(2ⁿ))가 가파르게 증가한다는 점입니다.

이러한 문제를 해결하기 위해 메모이제이션(Memoization)을 적용할 수 있습니다.

 

4. 메모이제이션(Memoization) 구현

메모이제이션은 이전에 계산한 값을 저장해서 중복된 계산을 피하는 방법입니다.

메모이제이션을 통해 재귀 함수 구현의 단점인 성능을 대폭 향상시킬 수 있습니다.

from functools import lru_cache


@lru_cache(maxsize=None)
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 = 50
print('Fibonacci({}): {}'.format(n, fib(n)))

functools의 lru_cache를 통해 간단하게 메모이제이션을 구현할 수 있습니다.

간단하게 @lru_cache 데코레이터를 추가해서 이미 연산된 값을 모두 저장합니다.

메모이제이션 결과

일반적인 재귀 함수 구현에서는 50번째 값을 구하는 것이 거의 불가능합니다.

이제 @lru_cache 데코레이터의 추가로 한 번 계산된 값은 바로 가져오기 때문에 빠르게 결과가 출력됩니다.

 

 

이외에도 행렬을 통한 방법 등을 활용해서 피보나치 수열을 구하는 방법도 존재합니다.

다양한 방법으로 구현하는 방법을 알아두면 프로그래밍에 대한 기초 지식을 쌓는데 도움이 됩니다.