파이썬으로 n번째 피보나치 수 구하기: 재귀와 동적 프로그래밍 완벽 가이드

이 글에서는 파이썬(Python)을 활용해 n번째 피보나치 수를 계산하는 방법을 알아보겠습니다.

피보나치 수(Fibonacci number)는 아래와 같은 점화식으로 정의되는 수열입니다.

Fn = Fn-1 + Fn-2

단, 초기값은 F₀ = 0, F₁ = 1입니다.

피보나치 수열의 처음 몇 개 항은 다음과 같습니다.

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

피보나치 수는 크게 재귀(recursion) 방식과 동적 프로그래밍(dynamic programming) 방식으로 계산할 수 있습니다. 그럼 지금부터 각각의 구현 방법을 파이썬 코드로 살펴보겠습니다.

방법 1: 재귀(Recursion)를 이용한 구현

예제 코드

# 재귀 방식
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

재귀 방식은 정의 그대로 코드를 옮기기 때문에 매우 직관적이라는 장점이 있습니다. 하지만 같은 값을 반복해서 계산하게 되어, 입력값이 커질수록 실행 시간이 기하급수적으로 늘어난다는 단점이 있습니다.

위 코드에서 선언된 모든 변수의 스코프는 아래 그림과 같습니다.

방법 2: 동적 프로그래밍(Dynamic Programming)을 이용한 구현

예제 코드

# 동적 프로그래밍 방식
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

동적 프로그래밍 방식은 이미 계산한 피보나치 수를 리스트(Fib_Array)에 저장해 두었다가 필요할 때 재사용합니다. 덕분에 불필요한 중복 연산을 제거할 수 있어, 재귀 방식보다 훨씬 빠르고 효율적으로 동작합니다.

위 코드에서 선언된 모든 변수의 스코프는 아래 그림과 같습니다.

마무리

이 글에서는 재귀와 동적 프로그래밍 두 가지 방법을 사용해 n번째 피보나치 수를 계산하는 방법을 배웠습니다. 재귀 방식은 코드가 단순하고 이해하기 쉬운 반면 성능이 떨어지며, 동적 프로그래밍 방식은 결과를 저장하고 재활용함으로써 시간 복잡도 측면에서 훨씬 유리합니다. 따라서 실전에서는 입력 크기가 큰 경우 동적 프로그래밍 방식을 사용하는 것이 좋습니다.