[LeetCode] - 509. Fibonacci Number

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Fibonacci Number" 문제입니다.

--> https://leetcode.com/problems/fibonacci-number/description/

 

문제 : 

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1.

That is, F(0) = 0, F(1) = 1 F(n) = F(n - 1) + F(n - 2), for n > 1. Given n, calculate F(n).

---

Example 1 :

Input : n = 2

Output : 1

Explanation : F(2) = F(1) + F(0) = 1 + 0 = 1.

 

Example 2 :

Input : n = 3

Output : 2

Explanation : F(3) = F(2) + F(1) = 1 + 1 = 2.

 

Example 3 :

Input : n = 4

Output : 3

Explanation : F(4) = F(3) + F(2) = 2 + 1 = 3.

 

Constraints : 0 <= n <= 30

---

수학을 좋아하시는 분 들이거나 컴공이신 분들은 수도 없이 봐왔을 것 같은 피보나치 문제입니다. 주로 Recursion 문제의 대표로 자주 나오죠. 피보나치 수열이란?

피보나치수열은 F(0)=0, F(1)=1에서 시작하며, 이후 각 숫자는 두 이전 숫자의 합으로 정의됩니다.

주어진 n에 대해 F(n)을 계산합니다.

 

예시: n=2일 때 F(2)=1, n=3일 때 F(3)=2, n=4일 때 F(4)=3이 됩니다.

 

이 문제를 풀 때의 저는 이제 막 recursion이 뭔지 배운 상태라서 효율적인 코드가 뭘까라기 보다는 recursion 써서 어떻게 풀지? 에 더 집중해서 효율성에는 생각을 많이 미치지는 못했습니다. 그래도 코드를 보여드리겠습니다. 그 후에 더 나은, 나중에 개선된 코드가 어떻게 생겼는지도 써보겠습니다.

 

1. 生코드 :

class Solution {
    public int fib(int n) {
            if (n == 0 || n == 1) {
                return n;
            } else {
                return fib(n - 1) + fib(n - 2);
            }
    }
}

 

문제 설명에서 나왔듯이 n이 0 또는 1일 때는 n을 내보내고, 아닐 경우에는 두 이전 숫자의 합을 반환합니다.

---

2. 개선된 코드 :

class Solution {
    public int fib(int n) {
        if (n < 2) return n;

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

 

• 특수 경우 처리:
  • n이 0이나 1인 경우, F(n)은 각각 0과 1이므로 바로 반환합니다. 즉, 2보다 작을 때
• 반복문을 통한 계산:
  • 초기 값 a와 b를 각각 0과 1로 설정합니다.
  • n이 2 이상인 경우, 반복문을 통해 F(n)을 계산합니다.
  • 각 반복에서 a와 b를 업데이트하여 F(n)을 구합니다.

이로써, 시간 복잡도는 O(n) 이 됩니다.

---

개선되기 전과 후 Runtime 결과