피보나치 수열

피보나치 수열은 1, 1, 2, 3, 5, 8... 과 같이 전개되는 수열로 처음 두 항이 모두 1이고 세번째 항 부터는 앞의 두 항의 합으로 이루어지는 수열이다. 중학교 과정에서 수열을 배울 때 잠깐 언급이 되는데, 프로그래밍을 공부하다보면 재귀와 관련하여 꼭 다시 만나게 되는 수열이다. 피보나치 수열의 수학적 정의는 다음과 같다.

F*{1}= 1, F*{2} = 1\\ F*{n} = F*{n-1} + F_{n-2}

이 식을 바탕으로 피보나치 수열의 일반항을 구하는 코드를 파이썬으로 작성해보면 다음과 같은 함수를 작성할 수 있다.


def fibonacci(n):
    if n < 3:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

원래 점화식으로 만들어지는 수열은 이처럼 재귀를 이용해서 구현하기 매우 쉽다. 하지만 여기에는 큰 문제가 하나 있는데, 36번째 항을 구하는 경우에 보통 5초 이상이 걸리는 이해하기 힘든 경우를 만나게 된다. (이후부터는 소요 시간이 지수적으로 증가하기 때문에 n이 100보다 크거나 하는 경우는 어지간한 인내력으로는 구할 수가 없다.)

재귀구현을 통한 피보나치 수열의 문제

이는 위 재귀 코드는 불필요하게 중복 계산을 계속해나가기 때문이다. 따라서 보통은 여기서 메모이제이션과 같은 기법을 동원해서 중복 계산을 줄여서 성능을 높이는 식으로 문제를 풀어나간다.


cache = {1:1, 2:1}
def fibonacci2(n):
    if n not in cache:
        f = fibonacci2(n-2) + fibonacci2(n-1)
        cache[n] = f
    return cache[n]

메모이제이션을 통해서 반복 계산을 줄이면, 989번째 항을 구하는데 2ms 정도로 비약적인 성능향상을 보인다.

하지만 메모이제이션은 중간 계산 결과를 모두 메모리에 캐시해두는 방법을 쓰고 있기 때문에 많은 양의 메모리를 소모한다는 단점이 있다.

따라서 첫항부터 반복적으로 계산하여 원하는 결과를 얻는 방법이 실질적으로는 가장 경제적인 방법이라 하겠다.


def fib3(n):
    if n < 2:
        return 1
    a, b = 0, 1
    while n > 0:
        a, b = b, a+b
        n -= 1
    return a

심지어 이는 위에서 캐시를 사용한 재귀형태의 함수보다도 빠르다.

활용

그런데 보통의 문제는 피보나치 수열을 처음부터 전개해 나가면서 특정 조건을 검사하는 식의 문제가 많다. 예를 들어,

4백만 이하의 피보나치 수열의 항 중 짝수인 항의 합은?
처음으로 50자리가 되는 피보나치 수열의 항은 몇 번째의 항인가?

이런 종류의 문제들은 위의 반복문 형식의 피보나치 수열 구하는 방법을 활용할 수 있다. 파이썬이라면 피보나치 수열을 순차적으로 생성하는 제너레이터를 만들어서 간단하게 풀 수 있다.


def fib():
    a, b = 0, 1
    while True:
        yield b
        a, b = b, a + b
        
def ex01():
    """4백만 이하의 피보나치 수열의 짝수항의 합"""
    g, s, n = fib(), 0, 0
    while n <= 4000000:
        n = next(g)
        if n % 2 is 0:
            s += n
    print(s)

이 제너레이터를 이용하면 두 번째 문제도 간단하게 풀 수 있다. 정수의 자리수를 구할 때 보통 이를 문자열로 바꿔서 len() 같은 함수를 써서 글자수를 세던데, 상용로그를 이용하면 간단히 자리수를 알 수 있다. 밑이 10인 상용로그값을 취했을 때, 한자리수는 0.xxxx, 두 자리수는 1.xxx 이니, 500자리 숫자라면 로그값이 499.xxx 가 될 것이다.

파이썬의 경우 상용로그는 math 모듈에 정의되어 있다. 따라서 다음과 같이 간단히 해결할 수 있다.


from math import log10

def ex02():
    """처음으로 500자리가 되는 피보나치 수열의 항은 몇 번째?"""
    g, f, n = fib(), 0, 0
    while True:
        n += 1
        f = next(g)
        if log10(f) >= 499:
            print(n)
            break

그외의 피보나치 수열을 구하는 방법

일반적으로 컴퓨터에서 피보나치 수열의 일반항을 빠르게 계산하는 것은 위에서 소개한 두 가지 방법이다. 그 외에는 행렬의 거듭제곱을 이용한 방법 (빠른 피보나치 변환)이 있다.

\begin{pmatrix} 1 & 1 \\ 1& 0 \end{pmatrix} ^n \begin{pmatrix} 1 \\ 1\end{pmatrix} = \begin{pmatrix} F_{n-1} \\ F_n \end{pmatrix}

행렬을 거듭제곱하여 계산하는 것이다. 이는 n이 크면 클 수록 앞서 소개한 제너레이터나, 앞에서부터 수열을 만들어서 n 항까지 진행하는 것보다도 계산횟수가 적어서 더 빠르게 일반항을 구할 수 있다.


def multiply(x, y):
    a, b = x
    c, d = y
    return (a*c + b*d, a*d + b*c + b*d)

def power(x, n):
    if n is 0:
        return (1, 0)
    if n % 2 == 0:
        return power(multiply(x, x), n // 2)
    return multiply(power(multiply(x, x), n // 2), x)

def fib_fast(n):
    return power((1, 1), n)[0]

53Percent

피보나치 수열