🎮 코딩테스트 [ ALL IN ONE ] 27. DP(Dynamic Programming) 총정리

DP(Dynamic Programming)

---

1. Overlapping subproblem
   👉 Problem을 작은 subproblem으로 분해
   👉 subproblem의 계산값을 재사용
2. Optimal substructure
   👉 subproblem의 최적 해법으로 원래 문제의 최적 해법을 구할 수 있다.

---

🚿 Top-down 방식

📢 $f(n)$부터 $f(1)$까지 접근하는 방식

1. 🌟재귀🌟 => 구현이 빠르다
2. 재귀풀이에서 중복되는 계산값을 저장하여(memoize) 동일한 함수 호출시에 재활용한다.
3. hashtable 또는 list에 계산 결과를 저장한다.

memoization : Top-down 방식에서 memo를 채워 나가는 것

---

🗾 Bottom-up 방식

📢 $f(1)$부터 $f(n)$까지 접근하는 방식

1. 🌟반복문🌟 => 실행시간이 빠르다
2. 더 작은 subproblem에 대한 계산결과를 DP table에 저장하여 더 큰 문제의 계산에 활용한다.
3. hashtable 또는 list에 계산 결과를 저장한다.

tabulation : Bottom-up 방식에서 memo를 채워 나가는 것

---

접근 방법

보통 문제를 풀 때 완전탐색으로 먼저 접근을 합니다.
완전탐색은 1. 재귀를 많이 이용합니다.
재귀는 하위문제로 나누기 작업을 하는 것입니다.
재귀가 아니더라도 2. 반복문을 사용할 때

중복된 값이 나올 때 -> 계산결과를 (memo) 저장하여 재활용

---

문제 적용

1. Optimum value(최대, 최소), 방법의 개수 등을 구할 때
   • ~의 최소 비용은?
   • ~의 최대 이익은?
   • ~를 하는 방법의 개수는?
   • What is the longest possible...
   • 특정 지점에 도달할 수 있는지?
2. 미래의 계산이 앞선 계산 결과에 영향을 받을 때

+문제 속에 답이 있다.

• 🌟recurrence relation🌟 (재귀 관계식 = 점화식)
• 🌟base case🌟

---

정리

DP : 다이나믹 프로그래밍이란 크고 복잡한 문제를 작게 나누고, 중복되는 문제라면 한 번 계산한 결과값을 저장해놓고 재사용함으로써 문제를 효율적으로 해결하는 알고리즘

문제 풀이 : 특정한 문제를 완전 탐색 알고리즘으로 접근해보고, 시간복잡도가 너무 높다면 DP를 적용할 수 있는지 생각해보자. subproblem의 중복 여부를 판단하는 것이 첫번째 순서다.

구현 방법 :
1. 일단 재귀함수로 비효율적인 🌟완전탐색🌟 코드를 작성한다.
2. 중복되는 🌟subproblem🌟의 계산 결과를 저장🌟(memoize)🌟한다.
3. 🌟탑다운 -> 바텀업🌟으로 코드 전환을 고려한다.

코테 출제 : DP는 문제에 적용하기에 어려운 개념이라서 코딩테스트에서는 기본에 충실만 문제 위주로 출제할 수 밖에 없다.

개념만 정리하고

문제를 많이 풀어보자!!

---

출처

📘 Inflearn - 코딩테스트 [ALL IN ONE]