문제

피보나치 수를 구하라

• Leetcode 509. Fibonacci Number

풀이

---

1. 재귀 방식의 풀이

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

• 재귀 방식의 Top-Down(하향식) 풀이이다.
• 코드는 간결하나 중복된 계산을 하여 성능이 좋지 않다.

2. 메모이제이션 방식의 풀이(중복된 계산 X)

class Solution:
    dp = collections.defaultdict(int)
    
    def fib(self, n: int) -> int:
        if n < 2:
            return n
        
        if self.dp[n]:
            return self.dp[n]
        # 중복된 계산을 하지않기 위해 계산한 값은 저장
        self.dp[n] = self.fib(n-2) + self.fib(n-1)
        
        return self.dp[n]

• 위의 풀이방식과 비슷하나 계산한 값은 딕트에 저장하여 중복된 계산을 하지 않는다. -> 성능이 10배가량 좋아졌다.

3. 타뷸레이션 풀이

class Solution:
    def fib(self, n: int) -> int:
        dp = [0, 1]

        while len(dp) <= n:
            dp.append(dp[-1] + dp[-2])
            
        return dp[n]

• 상향식(bottom-up) 방식의 타뷸레이션 풀이이다. 메모이제이션과 마찬가지로 중복된 계산은 하지않고 새로운 값을 저장하면서 피보나치 수를 구하는 풀이이다.

• 공간 복잡도 O(1)의 타뷸레이션 풀이

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