피보나치 수열

📌 피보나치 수열(Fibonacci Sequence)

피보나치 수열은 수학에서 매우 유명한 수열로, 간단하면서도 다양한 분야에서 응용되는 특징을 가진다.

📍 피보나치 수열의 정의

피보나치 수열은 다음과 같은 규칙으로 정의된다:

첫 번째 항은 0, 두 번째 항은 1로 시작한다.
이후의 항은 바로 앞의 두 항을 더한 값이다.

수열의 일반식:

F(0)=0F(0) = 0
F(1)=1F(1) = 1
F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2) (단, n≥2n \geq 2)

예시로 본 피보나치 수열:
0,1,1,2,3,5,8,13,21,34,55,…0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

📍 피보나치 수열의 특징

점차 빠르게 증가하는 수열로, 큰 값일수록 지수 함수적인 성장을 보인다.
두 항의 비율이 점점 **황금비(1.618)**에 가까워진다.

📌 피보나치 수열의 구현 방법

피보나치 수열은 다양한 방식으로 구현할 수 있다. 대표적인 방법으로는 재귀적 구현과 반복문을 이용한 구현이 있다.

✅ 1. 재귀적 구현 (Recursive)

int Fibonacci(int n)
{
    if (n <= 1)
        return n;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

🔴 단점

재귀 방식은 계산량이 많아질 경우 중복 호출로 인해 성능이 매우 느려진다.

✅ 2. 반복문을 이용한 구현 (Iterative)

int Fibonacci(int n) 
{
    if (n <= 1)
        return n;

    int a = 0, b = 1, result = 0;
    for (int i = 2; i <= n; ++i) {
        result = a + b;
        a = b;
        b = result;
    }
    return result;
}

🟢 장점

반복문 방식은 불필요한 중복 계산을 피하므로 큰 숫자에서도 더 효율적이다.

✅ 3. 동적 프로그래밍 (Dynamic Programming)

재귀 호출의 중복 계산 문제를 해결하기 위해 메모이제이션(Memoization) 기법을 활용한다.

int Fibonacci(int n, vector<int>& dp) 
{
    if (n <= 1)
        return n;
    if (dp[n] != -1)
        return dp[n];

    dp[n] = Fibonacci(n - 1, memo) + Fibonacci(n - 2, memo);
    return dp[n];
}