python 피보나치 수열

def fib(N:int)->int:
    if N <= 1:
        return N
    return fib(N - 1) + fib(N - 2)

만약 5 를 넣었다고 하면 ,

이런식의 결과를 얻게 되어 return 값 5가 나오게 된다.
이풀이는 논리적으로 맞지만 시간이 오래걸린다고 한다.

그래서 다른 풀이

class Solution:
    dp = collections.defaultdict(int)

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

        if self.dp[N]:
            return self.dp[N]

        self.dp[N] = self.fib(N - 1) + self.fib(N - 2)
        return self.dp[N]

이 풀이를 추천한다.
한번 계산한 수는 더이상 계산하지 않으므로 fib(2) 와 fib(3) 은 한 번만 계산하게 되어 효율적이다
처음의 계산 을 보면 우리는 앞서 fib(2) 와 fib(3) 의 결과를 두번 계산하고있지만
두번째 풀이는 한번만 계산해서 dp[N] 에 넣어준다.

defaultdict(<class 'int'>, {5: 0, 4: 0, 3: 0, 2: 1})
defaultdict(<class 'int'>, {5: 0, 4: 0, 3: 2, 2: 1})
defaultdict(<class 'int'>, {5: 0, 4: 3, 3: 2, 2: 1})
defaultdict(<class 'int'>, {5: 5, 4: 3, 3: 2, 2: 1})

이런식으로 저장하게 된다.