99클럽 코테 스터디 11일차 TIL + 피보나치 수열

F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
...

 

오늘의 공부 키워드

• 피보나치수열
• 509. Fibonaci Number

 

피보나치 수열

피보나치 수열은 수학에서 매우 유명한 수열 중 하나로, 각 숫자가 그 앞의 두 숫자의 합으로 이루어진 수열입니다. 이 수열은 이탈리아의 수학자 피보나치(Leonardo of Pisa, 피사르 피보나치)에 의해 서양에 소개되었습니다. 피보나치 수열은 다음과 같은 규칙을 따릅니다

 

• 첫 번째 숫자 (F(0))는 0입니다.
• 두 번째 숫자 (F(1))는 1입니다.
• 세 번째 숫자부터는 이전 두 숫자의 합입니다. 즉, F(n) = F(n-1) + F(n-2) (n > 1인 경우).

피보나치 수열의 초기 값은 다음과 같습니다:

F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
...

 

이 수열은 다음과 같이 시작됩니다: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

피보나치 수열의 특징

1. 재귀적 정의: 피보나치 수열은 간단한 재귀적 정의를 가지고 있습니다.
2. 기하학적 성질: 피보나치 수열은 황금비와 밀접한 관련이 있습니다. 두 연속된 피보나치 수의 비율은 황금비(약 1.618)에 점점 가까워집니다.
3. 자연과 예술에서의 응용: 피보나치 수열은 자연현상(예: 나선형 조개껍질, 해바라기 씨앗의 배열)과 예술작품에서 종종 발견됩니다.

피보나치 수열 대표적인 방법

1. 재귀적 방법

가장 간단한 방법으로, 피보나치 수열의 정의에 따라 재귀적으로 계산하는 방법입니다.

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        return self.fib(n - 1) + self.fib(n - 2)

 

 

 

• 장점: 구현이 매우 간단합니다.
• 단점: 같은 계산을 반복하기 때문에 시간 복잡도가 O(2^n)으로 매우 비효율적입니다.

2. 메모이제이션 (재귀적 방법의 개선)

재귀적 방법의 단점을 보완하기 위해 메모이제이션을 사용하여 이미 계산된 값을 저장합니다.

class Solution:
    def __init__(self):
        self.memo = {}
    
    def fib(self, n: int) -> int:
        if n in self.memo:
            return self.memo[n]
        if n <= 1:
            return n
        self.memo[n] = self.fib(n - 1) + self.fib(n - 2)
        return self.memo[n]

 

 

 

• 장점: 중복 계산을 피할 수 있어서 시간 복잡도가 O(n)으로 개선됩니다.
• 단점: 추가적인 메모리 공간이 필요합니다.

3. 반복적 방법

반복문을 사용하여 피보나치 수를 계산하는 방법입니다

class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        elif n == 1:
            return 1
        
        a, b = 0, 1
        for _ in range(2, n + 1):
            a, b = b, a + b
        return b

 

 

 

• 장점: 시간 복잡도가 O(n)으로 효율적이며, 추가적인 메모리 공간이 거의 필요하지 않습니다.
• 단점: 코드가 재귀적 방법보다 조금 복잡합니다.

4. 동적 프로그래밍 (탑다운 접근법)

DP 배열을 사용하여 각 피보나치 수를 저장하면서 계산하는 방법입니다.

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        
        dp = [0] * (n + 1)
        dp[1] = 1
        
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        
        return dp[n]

 

 

 

• 장점: 중복 계산을 피할 수 있고, 코드가 직관적입니다.
• 단점: O(n)의 추가 메모리 공간이 필요합니다.

5. 행렬 제곱 방법

피보나치 수열을 행렬을 사용해 계산하는 방법으로, 시간 복잡도가 O(log n)입니다.

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        
        def matrix_mult(A, B):
            return [
                [A[0][0] * B[0][0] + A[0][1] * B[1][0], A[0][0] * B[0][1] + A[0][1] * B[1][1]],
                [A[1][0] * B[0][0] + A[1][1] * B[1][0], A[1][0] * B[0][1] + A[1][1] * B[1][1]]
            ]
        
        def matrix_pow(M, power):
            result = [[1, 0], [0, 1]]
            base = M
            while power:
                if power % 2 == 1:
                    result = matrix_mult(result, base)
                base = matrix_mult(base, base)
                power //= 2
            return result
        
        F = [[1, 1], [1, 0]]
        result = matrix_pow(F, n - 1)
        return result[0][0]

 

 

 

• 장점: 시간 복잡도가 O(log n)으로 매우 효율적입니다.
• 단점: 코드가 복잡하며, 행렬 연산을 이해해야 합니다.

 

 

509 Fibonaci Number

 

피보나치 수열은 각 숫자가 이전 두 숫자의 합으로 구성된 수열입니다. 이 문제에서는 주어진 n에 대해 피보나치 수 F(n)을 계산하는 방법을 찾고자 합니다. 피보나치 수열은 다음과 같이 정의됩니다:

• F(0) = 0
• F(1) = 1
• F(n) = F(n - 1) + F(n - 2) (n > 1인 경우)

이를 바탕으로 몇 가지 예제를 살펴보겠습니다:

예제 1:

• 입력: n = 2
• 출력: 1
• 설명: F(2) = F(1) + F(0) = 1 + 0 = 1

예제 2:

• 입력: n = 3
• 출력: 2
• 설명: F(3) = F(2) + F(1) = 1 + 1 = 2

예제 3:

• 입력: n = 4
• 출력: 3
• 설명: F(4) = F(3) + F(2) = 2 + 1 = 3

문제 해결 방법

이 문제를 해결하기 위해 두 가지 방법을 고려할 수 있습니다: 재귀적 방법과 반복적 방법. 여기서는 반복적 방법을 사용하여 효율적으로 피보나치 수를 계산하겠습니다.

 

반복적 방법

반복적 방법은 시간 복잡도가 O(n)으로, 재귀적 방법보다 더 효율적입니다. 다음과 같은 단계를 따릅니다:

1. F(0)과 F(1)을 초기화합니다.
2. 반복문을 통해 F(2)부터 F(n)까지의 값을 계산합니다.
3. 최종적으로 F(n)을 반환합니다.

코드

class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        elif n == 1:
            return 1
        
        a, b = 0, 1
        for _ in range(2, n + 1):
            a, b = b, a + b
        return b

 

 

코드 설명:

1. n이 0인 경우 0을 반환합니다.
2. n이 1인 경우 1을 반환합니다.
3. a와 b를 각각 0과 1로 초기화합니다.
4. for 반복문을 통해 n까지 반복하면서 a와 b를 업데이트합니다. a는 이전 값, b는 현재 값이 됩니다.
5. 반복이 끝난 후, b는 F(n)의 값이 됩니다.

이 코드를 사용하면 주어진 n에 대해 피보나치 수를 효율적으로 계산할 수 있습니다.

 

오늘의 회고

 

• 새로운 개념인 피보나치 수열을 배울수 있었다.
• 좀더 끈질기게 고민하고 문제를 풀어야 하는데 쉽게 포기하는게 아닌가 하고 반성하게 된다.
• 코딩테스트 문제만 풀지말고 기록도 남겨야 함을 느낀다.
• 공부할것은 더욱 많음을 느낀다.
• 문제를 지금 거의 풀수는 없지만 복습하고 복습하고 복습하기 위해 기록을 남긴다.
• 부족함을 느끼지만 실력을 늘리는것이 제일 빠른길임을 명심하자