[leetcode] 509. Fibonacci Number (2)

- 이전 블로그에서 2020. 7. 14.  에 본인이 직접 작성한 포스트를 옮겨온 글입니다.

 

 

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

Fibonacci Number - LeetCode

 

 

3. 다른풀이

 

라고 했지만 일단 solution으로 나와있는 모든 풀이를 하나씩 살펴보자.

 

1) Recursion

fib(5)를 얻기위해선 생각보다 많은 fib 호출이 필요하다. 그리고 중복이 많다.

위의 그림이 재귀 방법으로는 문제 풀이가 어렵다는 점을 잘 설명해주고 있다. 

• 시간 복잡도 : O(2ⁿ). 피보나치 수열문제를 해결하는 가장 "느린" 방법이다. 위와 같은 트리의 depth가 바로 n이 된다.
• 공간복잡도 : O(N). 재귀 과정에서 메모리의 stack을 사용하게된다. fib(N)의 fuction call이 일어날때마다 stack에 저장해야한다. 이렇게 계속 stack의 메모리를 쓰기 때문에  StackOverflowError 를 유발할 수 있다.  Java docs

StackOverflowError (Java Platform SE 7 )

 

 

2) using Memoization

 recursion 방식의 문제는 반복이 발생한다는 점이었다. 위의 그림에서 fib(3)은 3번이나 다시 계산해야 한다. N이 커질수록 현상은 심해진다. 방법은? 미리 만들어서 저장해 두면 된다. 

 solution에서는 두가지 방식으로 풀이했다. Top down 방식과 Bottom up 방식.

아래는 Top down 방식이다.

class Solution:
    def fib(self, N: int) -> int:
        if N <= 1:
            return N
        self.cache = {0: 0, 1: 1}
        return self.memoize(N)

    def memoize(self, N: int) -> {}:
        if N in self.cache.keys():
            return self.cache[N]
        self.cache[N] = self.memoize(N-1) + self.memoize(N-2)
        return self.memoize(N)

memoize를 재귀로 호출하는데 다른점은 한번 호출한거는 저장을 해놓기 때문에 다시 호출할때는 계산 대신 바로 return 할 수 있다. Bottom up 방식은 2부터 시작해서 계산해나가서 fib(N)을 마지막으로 만들어서 return 한다.

 

fib(1)부터 fib(N)까지 한번씩 계산하고 저장하게 되는 셈이다. 그래서 Time complexity, space complexity 모두 O(N)

 

 

3) Iterative Top-Down Approach

다음 방법은 위의 bottom up memoization 방식처럼 2->3->4 순서대로 만들어가는데 굳이 다 기억할 필요 없이 꼭 필요한 두 값만 가지고 움직이는방식이다. fib(N)을 만들기 위해서는 fib(N-1)과 fib(N-2) 두 값만 알고있어도 된다. 직전값과 전전값 딱 두개만 가지고 있으면 만들수 있으니 굳이 배열에 다 저장하지 않는다.

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

        current = 0
        prev1 = 1
        prev2 = 1

        # Since range is exclusive and we want to include N, we need to put N+1.
        for i in range(3, N+1):
            current = prev1 + prev2
            prev2 = prev1
            prev1 = current
        return current

이렇게하면 time complexity는 그대로 O(N) 이면서  공간은 딱 3개만 있으면 되므로 space complexity 는 O(1)이다. 

 

지금보니 내가 생각했던 방법은 2 momoization 의 bottom up 방식과 iterative top-down의 중간쯤? 되는 것 같다.

 

 

4) 수학적 방법들

 나머지 두 방법은 좀 신박하다. 하나는 행렬을 이용하는 방법이고 하나는 무슨 공식을 이용한다. 이것도 알고리즘 적인가 싶어서 일단 넘어가지만 시간나는데로 이 코드들도 리뷰를 해보겠다.