<aside> 📎 목차

</aside>

Dynamic Programming

<aside> 📎 캐싱을 사용하는 최적화 기법

• 최적화 문제를 해결

• 중복된 연산을 피하기 위해 사용

• 작은 하위 문제들의 해결책을 조합 ⇒ 전체 문제를 해결 </aside>

• CodeSandbox : https://codesandbox.io/s/dp-dynamic-programming-f3cwre?file=/src/dp/memoizationWithCloser.js:388-498

<aside> 📎 주로 사용되는 예제

• 피보나치 수열
• Longest Common Substring (최장 공통 부분 문자열)
• 0/1 Knapsack Problem (0/1 배낭 문제)
• 그래프의 최단 경로

추가 문제

1. House Robber
2. Best Time to Buy and Sell Stock
3. Climbing Stairs </aside>

동적(다이나믹) 프로그래밍이란?

• 분할 정복 Divide & Conquer과 메모이제이션 Memozation의 결합입니다.

<aside> 🤔 다이나믹 프로그래밍을 고려하기

1. 문제를 하위 문제로 나눌 수 있는가?
2. 재귀로 해결하는 문제인가? - tree
3. 하위 문제가 반복적인가?
4. Memoize할 수 있는가?

• 문제를 작은 하위 문제로 쪼갤 수 있고, 반복적인 재귀 해결책들의 결과를 캐싱하여 성능을 개선할 수 있을 때 사용합니다. </aside>

1. Overlapping Subproblems 중복되는 하위 문제

• 큰 문제를 하위 문제로 쪼갭니다.
• 하위 문제들은 서로 중복될 수 있습니다.
• 중복된 하위 문제들을 한 번만 해결하고 저장하여, 중복된 계산을 피합니다.

2. Optimal Substructure 최적 부분 구조

• 부분 문제의 최적 해결책을 조합하여 최적의 해결책을 구합니다.

3. Top-down + Memoization 메모이제이션 📌

• 하위 문제의 해결책을 저장하고 재사용합니다.

4. Bottom-up Approach

• 부분 문제의 최적 해결책을 구한 후, 이를 이용하여 전체 문제의 최적 해결책을 구합니다.

Memoization

캐싱 Caching