파이썬에서 피보나치 수열 사용하는 방법

[

#파이썬을 이용한 피보나치 수열

피보나치 수열은 매우 유명한 정수 수열입니다. 이 수열은 여러 문제에서 자연스레 나타나며 재귀적인 정의를 갖고 있습니다. 이 튜토리얼에서는 피보나치 수열이 무엇이며 파이썬을 이용해 어떻게 생성하는지에 대해 배워보겠습니다.

이 튜토리얼에서는 다음과 같은 내용을 배우게 됩니다:

재귀 알고리즘을 사용하여 피보나치 수열 생성하기
메모이제이션을 사용하여 재귀적인 피보나치 알고리즘 최적화하기
반복적인 알고리즘을 사용하여 피보나치 수열 생성하기

이 튜토리얼에서는 기본적인 Big O 표기법, 객체 지향 프로그래밍, 파이썬의 특수 메소드, 조건문, 함수, 기본적인 자료 구조 (리스트, 큐, 스택 등)에 대한 기본 지식이 필요합니다. 이러한 개념에 대한 어느 정도의 이해도가 있으면 튜토리얼에서 새로운 개념을 쉽게 이해하실 수 있습니다.

자, 바로 시작해봅시다!

피보나치 수열 소개

레오나르도 피보나치는 이태리의 수학자로, 스와비아의 프리드리히 2세 황제에게 다음과 같은 질문에 빠르게 대답할 수 있었습니다: “죽음의 경우를 제외하고, 각 짝은 매달 다음 짝을 낳으며, 가장 어린 짝들은 이미 태어난 지 두 달째부터 번식이 가능하다고 가정할 때, 1년 동안 몇 쌍의 토끼가 얻어지나요?”

대답은 다음 수열을 바탕으로 했습니다:

0과 1로 시작하는 피보나치 수열과 같은 패턴은 각 숫자가 그 앞의 두 숫자의 합이라는 점에서 시작합니다. 인도 수학자들은 6세기부터 이 수열에 대해 알고 있었으며, 피보나치는 이를 활용하여 토끼 인구의 증가를 계산했습니다.

이제 피보나치 수열을 생성하는 방법에 대해 자세히 알아보겠습니다.

피보나치 수열 생성을 위한 시작

def fibonacci(n):
    if n <= 0:
        return []
    elif n == 1:
        return [0]
    elif n == 2:
        return [0, 1]
    else:
        fib = [0, 1]
        while len(fib) < n:
            fib.append(fib[-1] + fib[-2])
        return fib

위의 예제 코드에서는 입력된 숫자 n의 크기에 따라 피보나치 수열을 생성하는 함수 fibonacci를 정의하고 있습니다. 이 함수는 초기값으로 0과 1이 있는 리스트 fib를 생성하고, fib의 길이가 n이 될 때까지 마지막 두 숫자를 더하여 계속 리스트에 추가합니다. 이후 생성된 피보나치 수열 fib를 반환합니다.

이 함수를 이용하여 피보나치 수열을 생성해보겠습니다.

fib = fibonacci(10)
print(fib)

위의 코드를 실행하면 길이가 10인 피보나치 수열을 생성하고 출력합니다. 출력 결과는 다음과 같을 것입니다:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

이처럼 간단한 반복문을 통해 피보나치 수열을 생성할 수 있습니다.

재귀 알고리즘을 사용하여 피보나치 수열 생성하기

def fibonacci_recursive(n):
    if n <= 0:
        return []
    elif n == 1:
        return [0]
    elif n == 2:
        return [0, 1]
    else:
        fib = fibonacci_recursive(n-1)
        fib.append(fib[-1] + fib[-2])
        return fib

위의 예제 코드에서는 재귀적으로 피보나치 수열을 생성하는 함수 fibonacci_recursive를 정의하고 있습니다. 이 함수는 입력된 숫자 n이 2보다 작을 때는 빈 리스트, 2일 때는 초기값인 [0, 1] 리스트를 반환하며, 그 외의 경우에는 n-1번째 피보나치 수열을 재귀적으로 호출한 뒤 마지막 두 숫자를 더하여 리스트에 추가합니다. 이후 생성된 피보나치 수열 fib를 반환합니다.

이 함수를 이용하여 재귀적으로 피보나치 수열을 생성해보겠습니다.

fib = fibonacci_recursive(10)
print(fib)

위의 코드를 실행하면 재귀 알고리즘을 사용하여 생성된 길이가 10인 피보나치 수열이 출력될 것입니다.

재귀 알고리즘의 한계와 메모이제이션을 통한 최적화

재귀 알고리즘을 이용하여 피보나치 수열을 생성할 수 있지만, 큰 숫자에 대해서는 성능이 매우 저하될 수 있습니다. 이는 중복된 계산이 많이 발생하기 때문입니다.

이러한 문제를 해결하기 위해 메모이제이션을 사용하여 중복 계산을 피할 수 있습니다. 메모이제이션은 한 번 계산한 결과를 저장해두고, 다음에 필요할 때 저장된 결과를 바로 사용함으로써 중복 계산을 최소화하는 기법입니다.

def fibonacci_memo(n, memo={}):
    if n <= 0:
        return []
    elif n == 1:
        return [0]
    elif n == 2:
        return [0, 1]
    elif n in memo:
        return memo[n]
    else:
        fib = fibonacci_memo(n-1, memo)
        fib.append(fib[-1] + fib[-2])
        memo[n] = fib
        return fib

위의 예제 코드에서는 메모이제이션을 사용하여 피보나치 수열을 생성하는 함수 fibonacci_memo를 정의하고 있습니다. 이 함수는 입력된 숫자 n에 대해 memo 딕셔너리를 사용하여 이전에 계산된 결과를 저장합니다. 만약 n이 memo 딕셔너리에 이미 존재하는 경우, 저장된 결과를 바로 반환하며 중복 계산을 피합니다.

이 함수를 이용하여 메모이제이션을 활용한 피보나치 수열을 생성해보겠습니다.

fib = fibonacci_memo(10)
print(fib)

위의 코드를 실행하면 메모이제이션을 사용하여 생성된 길이가 10인 피보나치 수열이 출력될 것입니다.

반복적인 알고리즘을 사용하여 피보나치 수열 생성하기

def fibonacci_iterative(n):
    if n <= 0:
        return []
    elif n == 1:
        return [0]
    else:
        fib = [0, 1]
        while len(fib) < n:
            fib.append(fib[-1] + fib[-2])
        return fib

위의 예제 코드에서는 반복적인 알고리즘을 사용하여 피보나치 수열을 생성하는 함수 fibonacci_iterative를 정의하고 있습니다. 이 함수는 초기값으로 [0, 1] 리스트를 생성하고, fib의 길이가 n이 될 때까지 마지막 두 숫자를 더하여 리스트에 추가합니다. 이후 생성된 피보나치 수열 fib를 반환합니다.

이 함수를 이용하여 반복적인 알고리즘을 활용한 피보나치 수열을 생성해보겠습니다.

fib = fibonacci_iterative(10)
print(fib)

위의 코드를 실행하면 반복적인 알고리즘을 사용하여 생성된 길이가 10인 피보나치 수열이 출력될 것입니다.

결론

이 튜토리얼에서는 피보나치 수열이 무엇인지 그리고 파이썬을 이용하여 피보나치 수열을 생성하는 방법에 대해 배웠습니다. 재귀 알고리즘, 메모이제이션, 반복적인 알고리즘 등 다양한 방법을 사용하여 피보나치 수열을 생성할 수 있다는 것을 알 수 있었습니다. 이를 통해 재귀와 반복의 차이, 메모이제이션을 사용한 최적화, 반복적인 알고리즘의 간단한 구현 등에 대해 이해할 수 있었습니다.

피보나치 수열은 알고리즘과 수학에서 많이 활용되는 중요한 개념 중 하나입니다. 파이썬을 이용하여 피보나치 수열을 생성하는 방법을 습득하는 것은 알고리즘과 재귀적 사고 방식을 향상시키는 데 도움이 될 것입니다. 이러한 개념을 익힌 뒤에는 다양한 문제를 해결할 때 피보나치 수열을 적용할 수 있는 상황을 찾아보시기 바랍니다.