LeetCode 509 - Fibonacci Number (Easy)

출처: https://leetcode.com/problems/fibonacci-number/

// LeetCode 509 - Fibonacci Number (Easy)
// https://leetcode.com/problems/fibonacci-number/

// 문제 설명
// 피보나치 수열 F(n)을 계산하여 반환
// F(0) = 0, F(1) = 1
// F(n) = F(n-1) + F(n-2)  (n > 1)

// 제약 조건
// 0 <= n <= 30

// 예시
// n = 2 → 1   (F(2) = F(1) + F(0) = 1 + 0 = 1)
// n = 3 → 2   (F(3) = F(2) + F(1) = 1 + 1 = 2)
// n = 4 → 3   (F(4) = F(3) + F(2) = 2 + 1 = 3)

// 풀이 비교
// 재귀 (단순)      : 시간 O(2^n) / 공간 O(n)  — 중복 계산 폭발, n=30이면 약 10억 호출
// DP (메모이제이션) : 시간 O(n)   / 공간 O(n)  — Top-down, 캐시 활용
// DP (반복)        : 시간 O(n)   / 공간 O(1)  — Bottom-up, 변수 두 개만 사용 → 최적

#include <vector>
using namespace std;

// 내 풀이 #1 — 단순 재귀 O(2^n) / 공간 O(n)
// 중복 계산이 많아 n=30이면 약 10억 호출 — 비효율적이지만 로직 이해에 적합
//재귀 사용하라는줄알고 작성
class Solution {
public:
    int fib(int n)
    {
        int answer = 0;

        if(n <= 0) return 0;
        if(n == 1) return 1;

        answer += fib(n -1) + fib(n-2);

        return answer;
    }
};

// 추천 풀이 #2 — DP 반복 (Bottom-up) O(n) / 공간 O(1)
// 이전 두 값만 변수로 유지하며 앞에서부터 계산 — 재귀 호출 없음, 가장 효율적
class Solution2 {
public:
    int fib(int n)
    {
        if (n <= 0) return 0;
        if (n == 1) return 1;

        int prev2 = 0, prev1 = 1;
        for (int i = 2; i <= n; i++)
        {
            int cur = prev1 + prev2;
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
};