Fibonacci Number

 

Fibonacci Number

Fibonacci Number - LeetCode

 

다이나믹 프로그래밍(Dynamic Programming, 이하 DP)을 이해하는데 기본이 되는 문제입니다. 

DP 는 중복된 하위 문제들(Optimal Substructure)의 결과를 저장해뒀다가 풀이에 활용하는 방식으로 문제를 하위 문제들로 분할하여 풀이한다는 점에서 분할정복, 그리디 알고리즘과 공통점이 있지만, 탐욕 선택 방식의 유무에 따라 그리디 알고리즘과 차이점이 있고 분할 정복과는 '중복된'  하위 문제들의 결과를 저장한다는 것에서 차이점이 있습니다.

 

결과를 저장하는 방식에는 ① Memoization ② Tabulation 이 있으며, Memoization의 경우 Top-Down 방식의 풀이, Tabulation은 Bottom-up 방식의 풀이에 사용되는 방식입니다. 보통의 경우 DP 문제라고 하면 Tabulation 방식을 뜻합니다. Tabulation 은 데이터를 테이블 형태로 만들면서 풀이하는 방식입니다.

 

DP 문제를 이해하는데 기본이 되는 피보나치 수열 문제는 4가지 방식으로 풀이가 가능합니다.

(참고 : 파이썬 알고리즘 인터뷰 책)

 

1. Brute-pos 방법

    재귀 구조를 활용하여 풀이하는 Top-down 방식으로 가장 속도가 느린 방법입니다.

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

2. Memoization

    재귀 구조를 활용하여 풀이하되 Dictionary를 사용하여 이미 계산된 결과를 저장하여 계산량을 줄이는 방법입니다.

class Solution:
    
    dic = collections.defaultdict(int)
    def fib(self, N: int) -> int:
        
        # Memoization
        
        if N<= 1:
            return N
        
        # 결과를 저장하는 것
        if self.dic[N]:
            return self.dic[N]
        
        self.dic[N] = self.fib(N-1)+self.fib(N-2)
        
        return self.dic[N]
        
        

 

3. Tabulation

    재귀 구조가 아닌 반복문의 형태로 풀이하되 풀이 결과를 Table 형태로 저장하여 활용하는 방식입니다.

class Solution:
    dic = collections.defaultdict(int)
    def fib(self, N: int) -> int:
        # Tabulation
        
        # 재귀를 사용하지 않고 반복으로 풀이, 
        # 작은 값부터 직접 계산하여 타뷸레이션 한다. 
        self.dic[1]= 1
        
        for i in range(2, N+1):
            self.dic[N] = self.dic[N-1]+self.dic[N-2]
        
        return self.dic[N]
        

4. 두 변수만 활용하여 공간 절약

    이전의 값들을 모두 저장할 필요없이 바로 직전의 두 수만 알면 풀이가 가능하다는 특징을 이용한 방식입니다.

class Solution:
    def fib(self, N: int) -> int:
        # Bottom up 방식을 사용하긴 하되
        # Tabulation 하지 않는 방법
        # 공간복잡도가 O(1)
        
        x,y = 0, 1
        
        for i in range(0,N):
            x,y = y, x+y
            
        return x