CHAPTER 02 μž¬κ·€ 호좜의 νŠΉμ§•κ³Ό λ©”λͺ¨ μ „λž΅

2.1 졜적의 ν•˜μœ„ ꡬ쑰

졜적의 ν•˜μœ„ ꡬ쑰 νŠΉμ„±μ„ 가진 문제 : 크기가 n인 문제λ₯Ό ν’€ λ•Œ ν˜•νƒœλŠ” κ°™μ§€λ§Œ n 미만의 μ›μ†Œλ₯Ό κ°€μ§€λŠ” 더 μž‘μ€ 크기의 문제의 풀이법을 μ‚¬μš©ν•˜λŠ” 것이 졜적의 풀이법인 문제

닀이내믹 ν”„λ‘œκ·Έλž˜λ°μ€ μž¬κ·€ μ ‘κ·Ό 방법을 λ©”λͺ¨λ¦¬μ™€ μ‹œκ°„μ˜ μΈ‘λ©΄μ—μ„œ 효율적으둜 μ΅œμ ν™”ν•˜λŠ” 데 μ‚¬μš©λ˜λŠ” μ ‘κ·Ό 방법이닀. DP의 첫 번째 λ‹¨κ³„λŠ” μ–΄λ–€ 문제의 점화식을 μž‘μ„±ν•˜κ±°λ‚˜ 졜적의 ν•˜μœ„ ꡬ쑰λ₯Ό μ •μ˜ν•˜λŠ” 것이닀.

닀이내믹 ν”„λ‘œκ·Έλž˜λ°κ³Ό κ΄€λ ¨λœ λ¬Έμ œκ°€ 주어지면 μš°μ„  점화식 λ˜λŠ” μž¬κ·€ μ ‘κ·Ό 방식을 μ‚¬μš©ν•΄ 문제λ₯Ό ν‘Ό λ‹€μŒ 같은 λ‘œμ§μ„ μ‚¬μš©ν•΄ 상ν–₯μ‹μœΌλ‘œ μ ‘κ·Όν•˜λŠ” 것이 μ’‹λ‹€.

2.2 ν•˜μœ„ 문제의 반볡 계산

ν•˜μœ„ 문제의 반볡 계산 : μ™„μ „νžˆ 같은 인수λ₯Ό μ‚¬μš©ν•œ 반볡된 μž¬κ·€ 호좜이 μ—¬λŸ¬ 번 λ°œμƒν•˜λŠ” 경우

온라인 μ½”λ”©ν…ŒμŠ€νŠΈμ—μ„œλŠ” μ‹œκ°„λ³΅μž‘λ„κ°€ μ€‘μš”ν•˜λ―€λ‘œ 속도가 느린 μ•Œκ³ λ¦¬μ¦˜μ€ 쒋은 점수λ₯Ό 받을 수 μ—†μ§€λ§Œ, ꡬ술 λ©΄μ ‘μ—μ„œ μ΅œμ ν™”λœ μ•Œκ³ λ¦¬μ¦˜μ„ 생각할 수 없을 λ•Œ μš°μ„  μž¬κ·€ μ ‘κ·Ό λ°©μ‹μ˜ 풀이법을 μ œμ‹œν•˜λŠ” 것도 μ’‹λ‹€. 닡을 내리지 λͺ»ν•˜λŠ” κ²ƒλ³΄λ‹€λŠ” 풀이법을 λ©΄μ ‘μžμ™€μ˜ λŒ€ν™”κ³Όμ •μ„ 톡해 μ΅œμ ν™”ν•˜λ©΄ λœλ‹€.

2.3 λ©”λͺ¨ μ „λž΅

λ©”λͺ¨μ΄μ œμ΄μ…˜(memoization) : μž¬κ·€ ν˜ΈμΆœμ„ λ°˜λ³΅ν•˜λŠ” λŒ€μ‹  처음 계산할 λ•Œ 값을 λ©”λͺ¨λ¦¬μ— μ €μž₯ν•΄μ„œ λ³΄κ΄€ν•˜λŠ” μ ‘κ·Ό 방법

  • μž¬κ·€ 호좜 + μΊμ‹œ - ν•˜μœ„ 문제의 반볡 계산
  • μ–΄λ–€ ν•˜μœ„ 문제λ₯Ό 처음 κ³„μ‚°ν–ˆμ„ λ•Œ κ·Έ κ²°κ³Όλ₯Ό μΌμ’…μ˜ μΊμ‹œμ— μ €μž₯ν•œλ‹€.
  • 같은 ν•˜μœ„ 문제λ₯Ό λ‹€μ‹œ ν’€μ–΄μ•Ό ν•  λ•ŒλŠ” μ €μž₯ν•΄ λ‘” κ²°κ³Όλ₯Ό 가져와 λ°˜ν™˜ν•œλ‹€.
  • λ©”λͺ¨μ΄μ œμ΄μ…˜μ—μ„œ μΊμ‹œμ˜ μžλ£Œν˜•μ„ κ²°μ •ν•˜λŠ” 것이 맀우 μ€‘μš”ν•˜λ‹€. 일반적으둜 배열을 μ‚¬μš©ν•œλ‹€.

▢️ λ©”λͺ¨μ΄μ œμ΄μ…˜λ„ μž¬κ·€ μ ‘κ·Ό 방법에 μ†ν•œλ‹€. ν•˜μœ„ 문제의 반볡 κ³„μ‚°μ΄λΌλŠ” λΆ€μž‘μš©μ„ ν”Όν•˜κ³  μž¬κ·€ μ ‘κ·Ό λ°©μ‹μ˜ μž₯점을 μ‚΄λ¦°λ‹€.