[Algorithm] DP(Dynamic Programming), λμ κ³νλ² (Bottom-Up, Top-Down)
#. λμ κ³νλ²? γ
λμ κ³νλ² = λ€μ΄λλ―Ή νλ‘κ·Έλλ°(Dynamic Programming), DP- 벨λ§-ν¬λ μκ³ λ¦¬μ¦μ κ°λ°ν 벨λ§μ΄ λ§λ€μ΄λΈ μκ³ λ¦¬μ¦- μκ³ λ¦¬μ¦ μ΄λ¦μ μ΄λ»κ² μ§μΌλ©΄ κΈ°μ΅μ μ λ¨κ³ , κ°μ§(?)κ° λ μ§ μκ°νλ€κ° λ€μ΄λλ―Ήμ΄λΌλ λ¨μ΄κ° μ’μμ μ΄λ κ² λμλ€λ.. γ
νΉμ§- λ€μ μνλ₯Ό ꡬνκΈ° μν΄, μ΄μ μνλ₯Ό μ μ₯νκ³ , μ¬μ©(Memoization)- 무μμ μ΄λ»κ² μ μ₯ν μ§ μ νλ κ²μ΄ μ€μ- λ§μ΄ νμ΄λ³΄κ³ , μκ° κ³Όμ μ μ°μ΅νλ κ²μ΄ μ€μ.. γ
μ μ© μμ1. μν μ μ- dpλ°°μ΄μ λ§λ€μμ λ, indexκ°μ΄ μλ―Ένλ μν- λ¬Έμ μ μ΄κΈ°μνλ₯Ό μ μ(μ§κ΄μ μΈ μμ λ¬Έμ μ ν΄)2. μ νμ ꡬνκΈ°- λ€μ μνλ₯Ό λνλ΄κΈ° μν ννμ3. μκ°λ³΅μ‘λ κ³μ°4. ꡬν γ
μ μ© λ°©λ²1. Top..
https://data-make.tistory.com/384