[Leetcode] 리트코드 - 피보나치 수(fibonacci-number) 파이썬(python) 풀이

문제

피보나치 수를 구하라.

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

입력 : n = 2
출력 : 1

입력 : n = 3
출력 : 2

입력 : n = 4
출력 : 3

코드

"""
fixme. https://leetcode.com/problems/fibonacci-number/
fixme. Q85. 피보나치 수
fixme. 피보나치 수를 구하라.
fixme. 입력 : n = 2
fixme. 출력 : 1
"""
import collections
import numpy as np


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

    dp = collections.defaultdict(int)

    def fibMemorization(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]

    def fibTabulation(self, N: int) -> int:
        self.dp[1] = 1

        for i in range(2, N + 1):
            self.dp[i] = self.dp[i - 1] + self.dp[i - 2]
        return self.dp[N]

    def fibTwoVariable(self, N: int) -> int:
        x, y = 0, 1
        for i in range(0, N):
            x, y = y, x + y
        return x

    def fibNumpy(self, n):
        M = np.matrix([0, 1], [1, 1])
        vec = np.array([0], [1])

        return np.matmul(M ** n, vec)[0]

풀이

메모이제이션

브루트 포스 풀이와 유사하게 재귀로 계산해 나가지만, 이미 계산한 값은 저장해뒀다가 바로 리턴한다. 앞서 fib(5)일 때 15번의 연산을 진행하던 구조는 이 메모이제이션 풀이에서는 아래의 그림과 같이 9번의 연산 만으로 풀이할 수 있게 된다. 한번 계산한 수는 더이 상 계산하지 않으므로 fib(2)와 fib(3)은 한 번만 계산하게 되어 매우 효율적이다.

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

self.fib(N - 1)쪽에서 계속 재귀 호출이 이루어져서 self.fib(N - 2)에서 저장한 값을 쓸 수 있게 된다.

출처
파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]