Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

Python으로 N번째 피보나치 수 구하기: 재귀부터 동적 프로그래밍까지

이 글에서는 Python을 이용해 N번째 피보나치 수(Fibonacci number)를 계산하는 방법을 다룹니다.

피보나치 수란?

피보나치 수는 아래의 점화식으로 정의되는 수열입니다.

Fn = Fn-1 + Fn-2

단, 초기값은 F0 = 0, F1 = 1입니다.

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

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

피보나치 수는 재귀(Recursion) 방식과 동적 프로그래밍(Dynamic Programming) 방식으로 계산할 수 있습니다. 지금부터 각각의 방법을 Python 코드로 살펴보겠습니다.

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

예제 코드

# 재귀적 접근
def Fibonacci(n):
    if n < 0:
        print("Fibonacci can't be computed")
    # 첫 번째 피보나치 수
    elif n == 1:
        return 0
    # 두 번째 피보나치 수
    elif n == 2:
        return 1
    else:
        return Fibonacci(n-1) + Fibonacci(n-2)

# 메인
n = 10
print(Fibonacci(n))

실행 결과

34

위 코드는 함수가 자기 자신을 호출하는 재귀 구조로 되어 있습니다. n이 1이면 0을, n이 2이면 1을 반환하고, 그 외의 경우에는 바로 앞의 두 항을 더한 값을 반환합니다.

다만 재귀 방식은 동일한 하위 문제를 반복해서 계산하므로, n이 커질수록 실행 시간이 기하급수적으로 늘어난다는 단점이 있습니다.

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

예제 코드

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

def fibonacci(n):
    if n < 0:
        print("Fibonacci can't be computed")
    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)에 저장해 두었다가 재사용하는 메모이제이션(Memoization) 기법을 활용합니다. 덕분에 같은 값을 여러 번 계산하지 않으므로, 재귀 방식에 비해 훨씬 빠른 성능을 보여줍니다.

마무리

이번 글에서는 재귀와 동적 프로그래밍 두 가지 방법으로 N번째 피보나치 수를 계산해 보았습니다. 작은 입력에는 재귀 방식도 충분하지만, 큰 n을 다룰 때는 중간 결과를 저장하는 동적 프로그래밍 방식이 시간 복잡도 측면에서 훨씬 유리하다는 점을 기억해 두시기 바랍니다.