CHAPTER 02 μ¬κ· νΈμΆμ νΉμ§κ³Ό λ©λͺ¨ μ λ΅
2.1 μ΅μ μ νμ ꡬ쑰
μ΅μ μ νμ ꡬ쑰 νΉμ±μ κ°μ§ λ¬Έμ : ν¬κΈ°κ° nμΈ λ¬Έμ λ₯Ό ν λ ννλ κ°μ§λ§ n λ―Έλ§μ μμλ₯Ό κ°μ§λ λ μμ ν¬κΈ°μ λ¬Έμ μ νμ΄λ²μ μ¬μ©νλ κ²μ΄ μ΅μ μ νμ΄λ²μΈ λ¬Έμ
λ€μ΄λ΄λ―Ή νλ‘κ·Έλλ°μ μ¬κ· μ κ·Ό λ°©λ²μ λ©λͺ¨λ¦¬μ μκ°μ μΈ‘λ©΄μμ ν¨μ¨μ μΌλ‘ μ΅μ ννλ λ° μ¬μ©λλ μ κ·Ό λ°©λ²μ΄λ€. DPμ 첫 λ²μ§Έ λ¨κ³λ μ΄λ€ λ¬Έμ μ μ νμμ μμ±νκ±°λ μ΅μ μ νμ ꡬ쑰λ₯Ό μ μνλ κ²μ΄λ€.
λ€μ΄λ΄λ―Ή νλ‘κ·Έλλ°κ³Ό κ΄λ ¨λ λ¬Έμ κ° μ£Όμ΄μ§λ©΄ μ°μ μ νμ λλ μ¬κ· μ κ·Ό λ°©μμ μ¬μ©ν΄ λ¬Έμ λ₯Ό νΌ λ€μ κ°μ λ‘μ§μ μ¬μ©ν΄ μν₯μμΌλ‘ μ κ·Όνλ κ²μ΄ μ’λ€.
2.2 νμ λ¬Έμ μ λ°λ³΅ κ³μ°
νμ λ¬Έμ μ λ°λ³΅ κ³μ° : μμ ν κ°μ μΈμλ₯Ό μ¬μ©ν λ°λ³΅λ μ¬κ· νΈμΆμ΄ μ¬λ¬ λ² λ°μνλ κ²½μ°
μ¨λΌμΈ μ½λ©ν μ€νΈμμλ μκ°λ³΅μ‘λκ° μ€μνλ―λ‘ μλκ° λλ¦° μκ³ λ¦¬μ¦μ μ’μ μ μλ₯Ό λ°μ μ μμ§λ§, ꡬμ λ©΄μ μμ μ΅μ νλ μκ³ λ¦¬μ¦μ μκ°ν μ μμ λ μ°μ μ¬κ· μ κ·Ό λ°©μμ νμ΄λ²μ μ μνλ κ²λ μ’λ€. λ΅μ λ΄λ¦¬μ§ λͺ»νλ κ²λ³΄λ€λ νμ΄λ²μ λ©΄μ μμμ λνκ³Όμ μ ν΅ν΄ μ΅μ ννλ©΄ λλ€.
2.3 λ©λͺ¨ μ λ΅
λ©λͺ¨μ΄μ μ΄μ
(memoization)
: μ¬κ· νΈμΆμ λ°λ³΅νλ λμ μ²μ κ³μ°ν λ κ°μ λ©λͺ¨λ¦¬μ μ μ₯ν΄μ 보κ΄νλ μ κ·Ό λ°©λ²
μ¬κ· νΈμΆ + μΊμ - νμ λ¬Έμ μ λ°λ³΅ κ³μ°
- μ΄λ€ νμ λ¬Έμ λ₯Ό μ²μ κ³μ°νμ λ κ·Έ κ²°κ³Όλ₯Ό μΌμ’ μ μΊμμ μ μ₯νλ€.
- κ°μ νμ λ¬Έμ λ₯Ό λ€μ νμ΄μΌ ν λλ μ μ₯ν΄ λ κ²°κ³Όλ₯Ό κ°μ Έμ λ°ννλ€.
- λ©λͺ¨μ΄μ μ΄μ μμ μΊμμ μλ£νμ κ²°μ νλ κ²μ΄ λ§€μ° μ€μνλ€. μΌλ°μ μΌλ‘ λ°°μ΄μ μ¬μ©νλ€.
βΆοΈ λ©λͺ¨μ΄μ μ΄μ λ μ¬κ· μ κ·Ό λ°©λ²μ μνλ€. νμ λ¬Έμ μ λ°λ³΅ κ³μ°μ΄λΌλ λΆμμ©μ νΌνκ³ μ¬κ· μ κ·Ό λ°©μμ μ₯μ μ μ΄λ¦°λ€.