TIL_24 : Dynamic Programming

🙄 Dynamic Programming

---

➡ Dynamic Programming?

• 한번 계산한 결과를 재활용하는 방식

➡ Dynamic Programming의 조건

• 최적 부분 구조 (Optimal Substructure)
  ➡ 부분 문제들의 최적의 답을 이용해 기존 문제의 최적의 답을 구할 수 있다

• 중복되는 부분 문제 (Overlapping Subproblems)
  ➡ 부분 문제들을 풀다보면 중복되는 문제들이 있을 수 있다

➡ Dynamic Programming 구현하는 방법

• Memoization

• Tabulation

🙄 Memoization

---

➡ Memoization?

• 중복되는 계산은 한 번만 계산 후 메모
• 하향식 접근 (Top-down Approach)
• 재귀

➡ 피보나치 Memoization

def fib_memo(n, cache):
    if n < 3:
        return 1
    if n in cache:
        return cache[n]
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]

def fib(n):
    # n번째 피보나치 수를 담는 사전
    fib_cache = {}
    return fib_memo(n, fib_cache)

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

# 55
# 12586269025
# 354224848179261915075

🙄 Tabulation

---

➡ Tabulation?

• Table 방식으로 정리
• 상향식 접근 (Bottom-up Approach)
• 반복문

➡ 피보나치 Tabulation

def fib_tab(n):
    table = []
    for i in range(n):
        if i <= 1:
            table.append(1)
        else:
            table.append(table[i-2]+table[i-1])
    return table[-1]
   
print(fib_tab(10))

# 55

🙄 Memoization vs Tabulation

---

• 공통점 : 둘 다 중복되는 부분 문제의 비효율을 해결

• 차이점

Memoization	Tabulation
재귀함수 사용	반복문 사용
과도한 Call stack으로 과부하, 오류가 날 수 있음	Call stack으로 인한 오류 위험 없음
필요없는 계산은 안해도 되는 장점	필요없는 계산까지 다 해야하는 단점