[Leetcode]509. Fibonacci Number

문제:

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.
Given n, calculate F(n).

 

Example 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

 

solution:

첫 번째

## solution1 : recursive tree; time complexity O(2^n) ; space complexity O(n);
    def fib(self, n: int) -> int: 
        if n <= 1:
            return n
        return self.fib(n-1) + self.fib(n-2)

이 solution은 recursive tree를 이용하여 푸는 것이다. 일단 , 재귀함수를 쓸 수 있으려면 2가지 조건을 충족해야 한다. 첫 번째, 내가 똑같은 일을 반복해서 할 수 있는가?(쪼개고 또 쪼개서 값을 찾을 수 있는가? 예를 들면, 상자 안에 상자가 들어있을 수도 있고, 인형이 들어있을 수도 있다고 가정해 보자. 이때, 상자를 열었을 때, 상자가 들어있을 수도 있다. 이때는 또 상자를 열어야 한다. 열었더니, 또 상자가 들어있다. 또 상자를 연다. 상자를 열었더니 , 인형이 나온다. return 한다. ) 두 번째 조건은, base case가 존재하냐이다. base case라는 것은 무한루프에 빠지지 않고, 구제할 조건을 말한다. 위의 예제에서, 인형이 나온다면 loop를 빠져나온다. 이러한 조건이 fib(self, n:int))에 구현할 수 있기 때문에 재귀함수를 사용할 수 있다. 

코드에 대한 설명:

1. 일단 n값이 1 이하면 return n을 한다. 1이면 1을 반환, 0이면 0을 반환

2. 1번 조건을 만족하지 않을 시, n>2 이상이라는 소리다. 즉, 재귀함수를 한번 더 돈다. 왜냐하면, 피보나치수열을 잘 살펴보면 , f(2)를 구하려면 f0 , f1을 알고 있어야 하고, f(3)을 구하려면 f2와 f1을 알고 있어야 한다. 즉 f3을 구하기 위해서는 f2를 알아야 하는데, f2를 알려면 f1과 f0을 알아야 한다. 즉 base case에 도달한다는 것이다. 

3. base case에 의해 call stack에 쌓여있는 method들이 하나씩 없어져간다. 

4. 최종값을 return 한다. 

 

결론 : recursive tree는 감이 잡힐 듯 잡히지 않는다. 이때, 나만의 대원칙이 필요하다.  첫 번째, 크게 크게 보자. 어떻게 해야 답을 찾을 수 있을까를 일단 구현한다. 예를 들면, fn-1 + fn-2를 더해야 한다. 이런 식으로 큰 틀을 짠다. 그리고 base case를 설정한다. 마지막으로 , 얘네들이 loop를 돌게 한다. 그리고 마지막으로 얘네가 loop를 끝났는데, 어떤 값을 return 받을지 고민해 본다. 

 

두 번째,

## solution2 : Dynamic programming; time complexity O(n) ; space complexity O(n);
    def fib(self, n: int) -> int:
        if n <= 1:
            return n 
        f = [0] * (n+1) 
        f[0] = 0 
        f[1] = 1 
        for i in range(2,n+1):
            f[i] = f[i-1] + f[i-2] 
        return f[n]

이 문제 같은 경우는 Dynamic programming을 이용해서 푸는 풀이 같다. 아직 Dp를 배우지는 않았지만, 현재까지의 상황을 저장해서 다음번에도 이용한다는 개념인 것 같다. 

 

코드에 대한 설명:

1. return n을 한다. 만약 n <=1이라면 (base case 설정) 

2. n+1개의 칸이 들어있는 list를 만든다. n개가 아닌 n+1개인 이유는 f(0)이 명시적으로 존재하기 때문이다. 예를 들어 , f5를 구하기 위해서는 6개의 칸이 필요하다. [0,1,2,3,4,5]. 

3. list를 만들고 f0 f1값을 각각 0과 1로 설정해 준다. 그 이유는 초기값을 설정해야 하기 때문이다. 

4. loop를 돌며 f [n+1] 값까지 설정해 준다. 

5. fn을 return 해준다. 

 

결론 : 생각보다 간단해서 놀랐다. 1번 풀이보다 직관적이다. 이 풀이에서 빈리스트를 설정하고 값을 할당해 저장하는 것을 배웠다. 앞으로 종종 써먹어야겠다. 

 

세 번째, 

 

## solution3 : Dynamic programming Memorization(Top-Down); time complexity O(n) ; space complexity O(n);
    dp = [-1] * 31 
    def fib(self, n: int) -> int:
        if n <= 1:
            return n 

        first = self.dp[n-1] if self.dp[n-1] != -1 else self.fib(n-1)
        second = self.dp[n-2] if self.dp[n-2] != -1 else self.fib(n-2) 

        self.dp[n] = first + second 
        return self.dp[n]

이 풀이는 Dp memorization을 이용한 풀이라고 한다. 2번 방법과 비슷하지만 약간 다른 점이 있다. 2번은 순차적으로 더해가는 방법이라면 , 이 친구는 값이 들어있다면 바로 꺼내쓸 수 있는 친구다. 

 

코드에 대한 설명:

1. dp라는 리스트를 만든다. -1 * 31개를 만든다. 왜 31인지는 모르겠다. 

2. n <=1 이면 return 해준다. 

3. if else문이다. self.dp [n-1]에 -1이 들어있으면 fib함수를 재귀적으로 돌려준다. 왜냐하면 값이 업데이트가 안되었다는 이야기는 그전의 값이 필요하다는 이야기이기 때문이다. 값이 들어있다면 바로 꺼내다 쓴다. 

4. self.dp [n]은 first + second를 해준다. 

5. 값을 return 한다. 

 

결론 : 이렇게 코드를 작성하면, 여러 번 쓸 때 유용하다는 생각을 했다. 왜냐하면 이미 dp라는 리스트에 저장되어 있어서, 언제든 값을 꺼내쓸 수 있기 때문이다.