알고리즘: 다이나믹 프로그래밍(dynamic programming) 공부하기! (Memorization, Tabulation, 공간최적화)

다이나믹 프로그래밍(Dynamic Programming)이란?

 

 

다이나믹 프로그래밍은 부분 문제들의 답을 중복되지 않게 최적의 방법으로 구하고 

이를 통해 기존의 답을 구하는 방식이다.

 

 

정리하자면 어떤 한 문제가 최적부분구조와 중복되는 부분 문제가 있을 때

동적 프로그래밍을 사용하면 효율적이다.

(두 조건을 만족하지 않아도 다이나믹 프로그래밍을 할 수 있다.) 

 

 

→ 최적부분구조(Optimal substructure)

 

  어떤 문제가 최적 부분구조로 이루어져 있을 때,

부분 문제들의 최적의 답을 구해서 기존 문제의 최적의 답을 구할 수 있다.

 

예를 들면, 최단경로를 찾는 문제가 있다.

 

 

→ 중복되는 부분 문제(Overlapping subproblems)

 

  주로 재귀(recursion)을 사용하는 경우, 중복되는 문제들이 생겨난다.

 

예를 들어 재귀를 이용해서 피보나치 수열, 팩토리얼 함수등을 구현할 때 중복되는 문제가 발생한다. 

 

 

 

 

그래서 어떻게 하면 효율적으로 프로그래밍을 할 수 있을까?

 

다이나믹 프로그래밍은 두 가지 방법으로 나뉜다. 

 

 

cache에 값을 기록하는 메모라이제이션(Memorization)과

 

(메모라이제이션은 그냥 필요한 내용을 메모한다고 생각하면 된다.)

 

리스트에 값을 기록하는 타뷸레이션(tabulation)이 있다. 

 

(타뷸레이션은 테이블에 정리한다는 의미)

 

 

피보나치함수를 기준으로 비교해보자

 

 

 

1. 메모라이제이션(Memorization)

 

 

  재귀를 이용하여 값을 위에서부터 계산하기 때문에 하향식 접근(top-down approach) 방식이다. 

 

def fib_memo(n, cache):

    if n < 3:         # base case
        return 1
        
        
    # 이미 n번째 피보나치값이 cache에 들어있으면 바로 리턴
    if n in cache:
        return cache[n]
    
    
    # 아직 n번째 피보나치 수를 계산하지 않았으면 계산을 한 후 cache에 저장
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)

    
    return cache[n]



def fib(n):
    
    fib_cache = {}

    return fib_memo(n, fib_cache)



print(fib(10))
print(fib(50))
print(fib(100))

 

55
12586269025
354224848179261915075

 

 

 

2. Tabulation

 

 

  단순히 반복문을 이용하여 밑에서부터 값을 계산하기 때문에 상향식 접근(bottom-up approach)방식이다.

 

def fib_tab(n):
   
   fib_table = [0, 1, 1]  # 0번째, 1번째, 2번째 값을 먼저 설정 
   
   for i in range(3, n + 1):
   
       fib_table.append(fib_table[i - 1] + fib_table[i - 2])
   
   
   return fib_table[n]
   


print(fib_tab(10))
print(fib_tab(56))
print(fib_tab(132))

 

55
12586269025
354224848179261915075

 

 

 

3. 다이나믹 프로그래밍의 공간 최적화

 

 

 메모라이제이션과 타뷸레이션은 O(n)이라는 공간을 사용한 반면,

 

 이런식으로 공간을 최적화하면 O(1)만의 공간으로도 구현이 가능하다.

 

def fib_optimized(n):
 
    if n < 3:
        return 1
    
    num1, num2 = 1, 1
        
    for i in range(3, n + 1):
        
        num2, num1 = num2 + num1, num2
        
    return num2



print(fib_optimized(10))
print(fib_optimized(16))
print(fib_optimized(53))
print(fib_optimized(213))

 

55
12586269025
354224848179261915075

 

 

 

4. 각각의 장단점

 

 

  Memorization의 경우,  재귀를 이용하기 때문에 값을 위에서부터 계산하여 필요 없는 계산은 안해도 된다.

 

하지만 스택이 너무 많이 쌓여서 과부화가 걸려 문제가 생길 수도 있다.

 

반면에, Tabulation은 그럴 위험은 없지만 표를 하나씩 밑에서부터 채워야 하기때문에

 

필요없는 값을 계산해야 할 수도 있다.