[DP] Memorization 과 Tabulation

[DP] Memorization 과 Tabulation

[DP] Memorization 과 Tabulation

DP : Dynamic Programing 의 방법은 Memorization 과 Tabulation 이 있다.

 

1. Memoization

Memorization - 기억, 암기.

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

cache에 값을 기록하여 중복 계산을 방지.

# fibonacci

def fibonacci(n, memo):
    if n < 3:
        memo[n] = 1
        return memo[n]
        
    # n번째 피보나치값이 memo 에 있을경우
    if memo[n]:
        return memo[n]
        
    # n 번째 값을 계산하지 않았을 경우, 재귀호출로 계산 후 Memorization
    memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)

    return memo[n]

 

 

2. Tabulation

Tabulation - 도표 작성, 표, 목록

밑에서부터 값을 계산하기 때문에 상향식 접근(bottom-up approach)방식.

리스트에 값을 기록.

# fibonacci

def fibonacci(n):
   
   table = [0, 1]
   
   # 점화식을 이용하여 n 까지 구하기
   for i in range(2, n + 1):
       table.append(table[i - 1] + table[i - 2])
   
   return table[n]

 

 

---

참고 블로그

seungjuitmemo.tistory.com/22

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

https://velog.io/@nninnnin7/Dynamic-programming-1

DP의 종류 - Tabulation과 Memoization