피보나치 수열: 비효율부터 최적화까지

피보나치 수열(Fibonacci Sequence)은 간단하면서도 많은 학습 기회를 제공하는 수학적 문제입니다. 개발자들은 이를 통해 알고리즘의 효율성을 탐구하고 코드 최적화를 시도합니다. 이번 포스팅에서는 가장 비효율적이지만 직관적인 방법부터 점점 더 효율적인 방식으로 피보나치 수열을 계산하는 다양한 코드를 소개하겠습니다.

 

1. 순수 재귀(Pure Recursion) - 가장 비효율적인 접근법

가장 먼저 소개할 방법은 순수 재귀를 이용한 피보나치 수열입니다. 이 방식은 구현이 간단하지만, 시간 복잡도는 O(2^n)으로 매우 비효율적입니다.

# 순수 재귀 방식
def fibonacci_recursive(n):
    if n <= 1:
        return n
    return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

print(fibonacci_recursive(10))  # 출력: 55

이 코드는 작은 숫자일 때는 잘 동작하지만, n이 커질수록 계산에 엄청난 시간이 소요됩니다. 동일한 하위 문제가 반복적으로 계산되기 때문입니다.

 

2. 메모이제이션(Memoization) - 중복 계산 방지

메모이제이션은 순수 재귀의 단점을 보완하기 위한 방법으로, 이미 계산한 값을 저장하여 중복 계산을 피합니다. 이는 시간 복잡도를 O(n)으로 개선합니다.

# 메모이제이션을 사용한 재귀 방식
memo = {}

def fibonacci_memo(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_memo(n-1) + fibonacci_memo(n-2)
    return memo[n]

print(fibonacci_memo(10))  # 출력: 55

메모이제이션을 통해 중복 계산을 피하면서도 재귀의 간결함을 유지할 수 있습니다. 그러나 여전히 재귀 호출에 따른 함수 호출 스택의 부담이 존재합니다.

 

3. 동적 계획법(Dynamic Programming) - 반복적 접근법

동적 계획법을 활용한 반복적 접근법은 피보나치 수열을 계산하는 또 다른 효율적인 방법입니다. 이 방법은 공간을 절약하고 재귀 호출의 부담을 제거합니다.

# 동적 계획법을 사용한 반복적 방식
def fibonacci_dp(n):
    if n <= 1:
        return n
    fib = [0, 1]
    for i in range(2, n + 1):
        fib.append(fib[i-1] + fib[i-2])
    return fib[n]

print(fibonacci_dp(10))  # 출력: 55

이 코드는 O(n)의 시간 복잡도와 O(n)의 공간 복잡도를 가지며, 재귀의 문제를 해결하면서도 간단하게 구현됩니다.

 

4. 행렬 거듭제곱(Matrix Exponentiation) - 로그 시간의 효율성

이 방식은 O(log n)의 시간 복잡도를 가지며, 수학적 배경을 활용하여 매우 빠르게 결과를 얻을 수 있습니다.

import numpy as np

def fibonacci_matrix(n):
    def matrix_mult(A, B):
        return [[A[0][0] * B[0][0] + A[0][1] * B[1][0], A[0][0] * B[0][1] + A[0][1] * B[1][1]],
                [A[1][0] * B[0][0] + A[1][1] * B[1][0], A[1][0] * B[0][1] + A[1][1] * B[1][1]]]
    
    def matrix_power(A, n):
        result = [[1, 0], [0, 1]]  # 단위 행렬
        while n > 0:
            if n % 2 == 1:
                result = matrix_mult(result, A)
            A = matrix_mult(A, A)
            n //= 2
        return result

    if n <= 1:
        return n
    F = [[1, 1], [1, 0]]
    result = matrix_power(F, n - 1)
    return result[0][0]

print(fibonacci_matrix(10))  # 출력: 55

이 방법은 매우 빠르며, 특히 n이 큰 경우 유용합니다. 그러나 구현이 다소 복잡해지는 단점이 있습니다.

 

5. 피보나치 수열의 일반항 - 비네 공식(Binet's Formula)

피보나치 수열의 일반항을 계산하는 수학적 방법으로 비네 공식을 사용할 수 있습니다. 이 공식은 피보나치 수를 상수 시간 O(1)에 계산할 수 있습니다. 비네 공식은 다음과 같습니다

import math

def fibonacci_binet(n):
    phi = (1 + math.sqrt(5)) / 2
    return round((phi**n - (1 - phi)**n) / math.sqrt(5))

print(fibonacci_binet(10))  # 출력: 55

비네 공식은 O(1)의 시간 복잡도를 가지며, 매우 빠르게 피보나치 수를 계산할 수 있습니다. 그러나 이 방법은 부동소수점 연산에 의존하기 때문에 큰 n에 대해 정확도가 떨어질 수 있습니다.

 

6. 공간 최적화 - O(1) 공간 복잡도

동적 계획법을 좀 더 최적화하면, 공간 복잡도를 O(1)로 줄일 수 있습니다. 두 개의 변수만 사용하여 피보나치 수열을 계산하는 방식입니다.

# 공간 최적화를 통한 반복적 방식
def fibonacci_optimized(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

print(fibonacci_optimized(10))  # 출력: 55

이 방법은 O(n)의 시간 복잡도를 유지하면서도, O(1)의 공간만을 사용하여 매우 효율적인 계산을 제공합니다.

 

결론

피보나치 수열을 계산하는 다양한 방법들을 살펴보았습니다. 가장 단순한 순수 재귀 방식부터, 메모이제이션, 동적 계획법, 행렬 거듭제곱, 그리고 비네 공식까지 각기 다른 방식의 효율성을 탐구할 수 있습니다. 개발자로서 이러한 다양한 접근을 이해하고 적절한 상황에서 사용할 수 있다면, 더 나은 알고리즘 설계를 할 수 있을 것입니다.

각 방법의 장단점을 직접 코드로 테스트해보고 성능을 비교해 보는 것도 큰 도움이 될 것입니다. 피보나치 수열을 통한 학습은 알고리즘 최적화의 기초를 닦는 데 매우 유용합니다.