[leetcode] 509. Fibonacci Number

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

출처: https://june13.tistory.com/12?category=873278 [Made for More]

 

1. 문제분석

 

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

Fibonacci Number - LeetCode

난이도 : easy

 

Note:

0 ≤ N ≤ 30.

 

 피보나치 수열 문제이다. 원래 피보나치 수열을 몰랐더라도 식이 그대로 나와있기에 상관 없다. 식을 그대로 알고리즘으로 구현 하는 문제이다.

 

포인트 

- N이 30까지 갈 수 있다.

2. 풀이

 

- 첫번째 시도는 재귀호출이었다.

class Solution:
    def fib(self, N: int) -> int:
        #recursive
        if N==0:
            return 0
        elif N==1 :
            return 1
        
        return Solution().fib(N-1)+Solution().fib(N)

재귀호출은 직관적이다.  그냥 식을 그대로 사용했다.

(처음에 Solution().fib 대신 그냥 fib라고 썼더니 정의가 안되어있다고,, ㅎ  self.fib 라고 해도 된다.)

 

그런데 이런 run time error 가 나왔다.

RecursionError: maximum recursion depth exceeded in comparison
 if N==0: Line 4 in fib (Solution.py) 
[Previous line repeated 996 more times] 
return Solution().fib(N-1)+Solution().fib(N) Line 9 in fib (Solution.py) 
return Solution().fib(N-1)+Solution().fib(N) Line 9 in fib (Solution.py) 
return Solution().fib(N-1)+Solution().fib(N) Line 9 in fib (Solution.py)

재귀호출을 이용해서 fib(30)을 계산하려면 엄청나게 많은 함수호출이 소요된다.

fib(2) 는  fib(1) + fib(0) 만 하면 되는데 - >2 번 호출

fib(3) 는 ( fib(2) = fib(1) +fib(0) ) + fib(1) ->4번 호출

fib(4) 는  (  fib(3)= (   ( fib(2) = fib(1) +fib(0) ) + fib(1) ) ) + ( fib(2) = fib(1) +fib(0) )  -> 8번 호출 

 

이렇게 호출이 기하급수적으로 늘어난다...

fib(N)의 경우 2^(N-1) 번 재귀호출을 해야한다. 

2^(29) 를 계산해보면 -> 536870912 이다.. ㄷㄷㄷ

 

이때 Time complexity : O(2^N) 으로 지수 알고리즘을 갖는다.

 

정신차리고 다시 시도한 방법은 greedy algorithm이다.

 

class Solution:
    
    def fib(self, N: int) -> int:
        # greedy algorithm
        ans =[0]*(N+1)
        for i in range(N+1):
            if i ==0:
                ans[0]=0
            elif i ==1:
                ans[1]=1
            else:
                ans[i]=ans[i-1]+ans[i-2]

        return ans[N]
        

fib(2)를 만들기위해서는 fib(1)과 fib(0)이 필요하다

fib(3)을 만들기 위해서는 fib(2) 와 fib(1) 이 필요하다. 재귀호출에서는 정직하게 둘씩 호출해서 값이 커질수록 수행시간이 엄청 늘어났다. fib(N)을 만들기 위한 이전값들을 단 한번만 구하고 저장해두면 다음 값을 만들때 사용할 수 있다.

 

for 문 하나를 사용하는 아주 단순한 구조이다.

Time complexity : O(N)    -> 0부터 N까지의 for문 한번만 돌면 된다.

space complexity : O(N)     -> 0~N까지 값을 저장한다.
 

3. 다른 풀이

 

-> 풀이 이후 보니 무려 5가지 방법의 풀이법이 있었다. 그중에는 내가 푼 방법과 비슷하거나 같은 방법들도 있었다.

풀이가 여러가지라서 그 코드들만 쭉 다시 한번 보면서 포스팅을 해봐야겠다.

 

4. 후기 

 leet code 문제를 정할 때 "pick one" 을 하면서 easy 문제가 나오면 읽어보고 풀지를 결정한다. 피보나치는 간단하고 아는 문제라 선택했는데 아무생각없이 재귀를 썼다가 런타임 에러가 나왔다..ㅎ 평소 내가 얼마나 시간복잡도를 생각 안하고 코딩하는지 알 수 있었다.  앞으로는 그냥 생각없이 하지 말자!