[파이썬] 리트코드 509. Fibonacci Number 풀이

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

Fibonacci Number - LeetCode

다이나믹 프로그래밍에는 상향식 방법과 하향식 방법이 존재한다. 

상향식 방법은 타뷸레이션이라는 것인데, 작은 문제의 정답을 이용해 큰 문제의 정답을 풀어나가는 방식이다.

작은 문제들의 계산을 다 해두고 결과값을 저장해뒀다가 필요한 결과값을 반환하는 식이다. 

 

range(2,n+1)의 모든 숫자에 대해 결과를 계산하는데

1. 각각의 계산값을 dp라는 리스트에 저장하여 기억하고

2. 각각의 작은 계산값을 이용해서 더 큰 계산을 해준다

다이나믹 프로그래밍의 특징이 잘 드러나는 방법이다

 

class Solution:
    dp = collections.defaultdict(int)
    def fib(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]
    #dp 자체에 값을 저장하기. 

하향식 방법은 메모이제이션이라고 한다. 범위 안의 모든 수에 대해 계산하여 값을 기억하는 것이 아니라, 계산 유무를 확인하며 나아간다는 점이 특징이다. 재귀로 풀 때와 비교했을 때, 계산은 재귀로 하면서도 결과값을 저장한다는 점만 차이난다. 그래서 조금 더 수월하게 풀 수 있는 방법이기도 하다. 

class Solution:
    dp = collections.defaultdict(int)
    def fib(self, n: int) -> int:
        if n<= 1: 
            return n #n 값이 1보다 작다면 n을 반환한다 
        if self.dp[n]:
            return self.dp[n] #dp[n]이 존재한다면(계산되어 있다면) dp[n]을 반환한다 
        self.dp[n] = self.fib(n-1) + self.fib(n-2) #dp[n]에 값이 없다면(아직 계산하지 않았다면) 계산해준다
        return self.dp[n]

이 두 방식 모두 재귀로 푸는 것보다 훨씬 빠르고 효율적이다