[LeetCode] fibonacci 수열의 다양한 풀이

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

Fibonacci Number - LeetCode

1. 재귀 

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

런타임은 1402ms 
메모리는 13.8MB 차지했다 

2. DP (1) - 메모이제이션 / 상향식  

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

일차원 선형구조로 메모이제이션을 실행해서 이해하기도 쉽고 코드 짜기도 쉽다. 

3. DP(2) - 메모이제이션 / 하향식 

import collections
dp = collections.defaultdict(int)

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

이때 n의 값을 모르는 상태에서 dp 테이블을 초기화하기 위해서 defaultdict 모듈을 사용했다. 
dp[n] 에 각각의 피보나치수열 연산 결과를 저장하기 때문에 연산이 한번씩만 수행되므로 재귀 호출 방식에 비해 효율적이다 ! 

4. 두 변수만 사용 - 공간 복잡도 절약하기 

import collections
dp = collections.defaultdict(int)

class Solution:
    
    def fib(self, n: int) -> int:
        
        x, y = 0, 1 
        for i in range(n):
            x, y = y, x+y
        return x

모든 값을 저장하지 않고 변수 2개만을 이용해서 수열의 값을 저장, 갱신하기 때문에 공간복잡도 측면에서 다른 방법보다 우수하다.