파이썬으로 n번째 피보나치 수 구하기: 재귀와 동적 프로그래밍 두 가지 방법

이 글에서는 n번째 피보나치 수를 계산하는 문제를 해결하기 위한 접근 방식과 솔루션을 단계별로 살펴보겠습니다.

문제 정의

우리의 과제는 n번째 피보나치 수(Fibonacci number)를 계산하는 것입니다.

피보나치 수열 Fn은 아래와 같은 점화식(recurrence relation)으로 정의됩니다.

Fn = Fn-1 + Fn-2

초기값(seed values)은 표준적으로 다음과 같이 주어집니다.

F0 = 0, F1 = 1

즉, 피보나치 수열은 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... 의 형태로 이어집니다.

이 문제는 크게 두 가지 방법으로 해결할 수 있습니다.

• 재귀적(Recursive) 접근 방법
• 동적 프로그래밍(Dynamic Programming) 접근 방법

방법 1 — 재귀적 접근 방법

재귀 방식은 점화식을 그대로 함수 호출로 옮긴 가장 직관적인 구현 방법입니다.

예제

# 재귀적 접근 방법
def Fibonacci(n):
    if n<0:
        print("피보나치 수를 계산할 수 없습니다")
    # 첫 번째 피보나치 수
    elif n==1:
        return 0
    # 두 번째 피보나치 수
    elif n==2:
        return 1
    else:
        return Fibonacci(n-1)+Fibonacci(n-2)
# 메인
n=10
print(Fibonacci(n))

출력 결과

34

아래 이미지에서 볼 수 있듯이 모든 변수는 전역 범위(global scope)에 선언되어 있습니다.

방법 2 — 동적 프로그래밍 접근 방법

동적 프로그래밍 방식은 이미 계산한 피보나치 수를 배열에 저장해 두었다가 필요할 때 재사용함으로써 불필요한 중복 계산을 제거합니다.

예제

# 동적 프로그래밍 접근 방법
Fib_Array = [0,1]

def fibonacci(n):
    if n<0:
        print("피보나치 수를 계산할 수 없습니다")
    elif n<=len(Fib_Array):
        return Fib_Array[n-1]
    else:
        temp = fibonacci(n-1)+fibonacci(n-2)
        Fib_Array.append(temp)
        return temp
# 드라이버 프로그램
n=10
print(fibonacci(n))

출력 결과

34

아래 이미지에서 볼 수 있듯이 모든 변수는 전역 범위(global scope)에 선언되어 있습니다.

두 방법의 성능 비교

재귀 방식은 코드가 간결하고 이해하기 쉽지만, 동일한 하위 문제를 여러 번 반복해서 계산하므로 시간 복잡도가 O(2ⁿ)에 달해 n이 커질수록 실행 속도가 급격히 느려집니다. 반면 동적 프로그래밍 방식은 한 번 계산한 값을 배열에 캐싱해 재사용하기 때문에 시간 복잡도가 O(n)으로 훨씬 효율적입니다. 따라서 n이 큰 경우에는 동적 프로그래밍이나 메모이제이션(memoization) 기법을 활용하는 것이 좋습니다.

결론

이 글에서는 파이썬으로 n번째 피보나치 수를 계산하는 두 가지 방법, 즉 재귀적 접근 방식과 동적 프로그래밍 접근 방식을 알아보았습니다. 각 방법의 특성과 성능 차이를 이해하고 상황에 맞는 방식을 선택하면 더욱 효율적인 코드를 작성할 수 있습니다.