피보나치 수열 최적화: 다이나믹 프로그래밍 적용법

피보나치 수열은 컴퓨터 과학과 수학에서 빈번하게 다루어지는 중요한 수열입니다. 피보나치 수열은 첫 두 항(F(0)과 F(1))이 각각 0과 1이고, 그 이후의 각 항은 바로 앞 두 항의 합인 수열을 말합니다. 즉, 피보나치 수열은 다음과 같은 점화식을 가집니다:

F(n) = F(n-1) + F(n-2) (n >= 2)

피보나치 수의 간단한 계산 방법은 재귀를 사용하는 것이지만, 이 방법은 비효율적입니다. 본 글에서는 다이나믹 프로그래밍을 사용한 피보나치 수열 최적화 방법을 다룹니다.

기본 재귀 방법

python
# 기본 재귀 방식의 피보나치 수열 계산

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

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

위 코드는 매우 직관적이지만, 시간 복잡도는 O(2^n)으로 매우 비효율적입니다. 이는 동일한 계산이 여러 번 반복되기 때문입니다.

메모이제이션 (상향식 접근법)

메모이제이션 기법을 통해 동일한 계산을 반복하지 않도록 할 수 있습니다. 메모이제이션은 부분 문제의 답을 저장해 두고, 필요할 때 재사용하는 방식입니다.

python
# 메모이제이션 사용한 피보나치 수열 계산

memo = {}

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

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

이 방법은 부분 문제의 답을 저장하기 때문에 시간 복잡도를 O(n)으로 줄여줍니다.

동적 프로그래밍 (하향식 접근법)

동적 프로그래밍을 사용하여 피보나치 수열을 계산할 수 있습니다. 이는 메모이제이션의 하향식 접근법과 달리, 하위 문제부터 해결해 나가는 상향식 접근법입니다.

python
# 동적 프로그래밍 사용한 피보나치 수열 계산

def fibonacci(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

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

이 방법 또한 시간 복잡도는 O(n)이며, 공간 복잡도 역시 O(n)입니다. 그러나 더 효율적인 공간 복잡도를 가진 해결 방법도 존재합니다.

공간 최적화

우리는 사실 피보나치 수열을 계산할 때 두 개의 변수만 필요하다는 사실을 알 수 있습니다. 이를 통해 공간 복잡도를 O(1)로 줄일 수 있습니다.

python
# 공간 최적화된 피보나치 수열 계산

def fibonacci(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(10))  # 출력: 55

위 코드에서는 배열이나 리스트를 사용할 필요 없이 두 개의 변수 a와 b만을 사용하여 피보나치 수를 계산합니다.

요약

본 글에서는 피보나치 수열을 계산하는 다양한 방법을 살펴보았습니다. 기본 재귀 방식은 단순하지만 비효율적이며, 메모이제이션과 동적 프로그래밍을 통해 이를 최적화할 수 있습니다. 또한, 공간 최적화를 통해 공간 복잡도를 최소화할 수 있음을 알아보았습니다. 다이나믹 프로그래밍 접근법을 통해 우리는 더 효율적인 알고리즘을 설계할 수 있습니다. 이는 단순한 피보나치 수열 계산을 넘어 복잡한 문제 해결에도 응용할 수 있는 강력한 도구입니다.