Dynamic Programming
2020-1νκΈ°, λνμμ βμκ³ λ¦¬μ¦β μμ μ λ£κ³ 곡λΆν λ°λ₯Ό μ 리ν κΈμ λλ€. μ§μ μ μΈμ λ νμμ λλ€ :) μ 체 ν¬μ€νΈλ Algorithm ν¬μ€νΈμμ νμΈνμ€ μ μμ΅λλ€.
DPλ μ λ§ μκ³ λ¦¬μ¦ PSλ₯Ό νλ©΄μ, λΉ μ§ μ μλ μ£Όμ λ€!! μ€μ λμνλ λ§μ μκ³ λ¦¬μ¦μ΄ DPμ ν ν¬λμ μ¬μ©νκ³ μμΌλ©°, μ°λ¦¬λ DPκ° κ°μ Έλ€μ£Όλ ν¨μ¨μ±μ λ λλ¦¬κ³ μλ€.
DPμ 컨μ μ μλμ κ°λ€.
1. Identifying a collection of subproblems.
2. Tackling them one by one.
2.1. smallest first.
2.2. using the result of small ones to solve the larger ones.
2.3. repeat this until solve the whole problems!
μ’λ μΆμνν κ΄μ μμ DPλ₯Ό λ°λΌλ³΄λ©΄, βDAG ordering on btw subproblemsβ, and βsmaller subproblemμ νΈλ λ°©μμ΄ bigger subproblemμ νΈλ λ°μ κ·Έλλ‘ μ¬μ©λλ€βλΌκ³ λ§ν μ μλ€.
DP ν ν¬λμ μ€μ¬μ <Memoization>μ΄λΌκ³ ν μ μλ€. subproblemμ κ²°κ³Όλ₯Ό λ°νμΌλ‘ problemμ νκΈ° λλ¬Έμ λΉμ°ν subproblemμ κ²°κ³Όλ₯Ό μ μ₯(memo)ν νμκ° μκ³ , μ΄λ μ°λ ν ν¬λμ΄ λ°λ‘ <Memoization>μ΄λ€. κ°λ¨ν λ§νμλ©΄, <Memoization>μ κ·Έλ₯ subproblemμ κ²°κ³Όλ₯Ό λ°°μ΄μ μ μ₯νλ€!μ΄λ€. μ΄ Memoizationμ μ΄λ»κ² ν κ»μ§ κ³ λ―Όνλ κ² μμ DPμμ μ€μν λΆλΆμ΄κΈ° λλ¬Έμ λ§μ μ°μ΅μ΄ νμνλ€.
μ΄λ² μ±ν°μμ λ€λ£¨λ λ¬Έμ λ€μ μλμ κ°λ€.
- LIS; Longest Increasing Subsequences
- Edit Distance
- Knapsack
- Chain Matrix Multiplication
- Shortest Reliable Paths
- All Pairs Shortest Paths; Floyd-Warshall
- TSP; Traveling Salesman Problem
- μμ νμ
- DP
- Independent Sets in Tree
- Weighted Interval Scheduling
- Segmented Least Squares
(μλΉν λ§μ λ¬Έμ κ° DPμ ν ν¬λμ μ¬μ©νλ€. κ·Έλ§νΌ DPκ° μ€μνλ€λ λ§!)