피보나치 수열(Fibonacci sequence)

피보나치 수열(Fibonacci sequence)

피보나치 수열(Fibonacci sequence)은 0과 1로 시작하며, 이전 두 개의 항을 더해서 다음 항을 만들어가는 수열이다.

$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots$

$F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2} (n ≥ 2)$

즉, 첫 번째 항과 두 번째 항은 각각 0과 1이며, 이후에는 이전 두 개의 항을 더해서 다음 항을 만들어가는 것이다. 이를 수식으로 나타내면 다음과 같다.

$F_n = F_{n-1} + F_{n-2}$

• 피보나치 수열의 특징

급격히 증가한다. 피보나치 수열의 각 항은 이전 항보다 약 1.618배 정도 더 크다는 특징을 가지며, 이를 "황금비율"이라고도 한다.
자연계에서 발견되는 비례관계에 적용된다. 삼각형, 나팔꽃, 소라 등의 자연현상에서도 피보나치 수열이 나타난다.

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

위 함수는 n번째 항의 값을 반환한다. 이 함수는 각 항마다 중복된 계산이 이루어지기 때문에, n이 커질수록 연산 시간이 급격히 증가하여 비효율적이다. 이를 개선하기 위해 중복 계산을 방지하는 방법을 사용해야 한다.

def fib(n):
    if n <= 1:
        return n

    fib_list = [0] * (n + 1)
    fib_list[1] = 1

    for i in range(2, n + 1):
        # i번째 피보나치 수 계산
        fib_list[i] = fib_list[i-1] + fib_list[i-2]

    return fib_list[n]

print(fib(20))

위 코드에서는 fib_list라는 배열을 만들어 메모이제이션을 구현한다. 이 배열의 인덱스 i는 i번째 피보나치 수를 의미하며, i번째 피보나치 수를 계산할 때는 이전 두 피보나치 수(fib_list[i-1]과 fib_list[i-2])를 더해주면 된다. 이를 통해 중복 계산을 피하면서 빠르게 피보나치 수열을 구할 수 있다.