2020-1ν•™κΈ°, λŒ€ν•™μ—μ„œ β€˜μ•Œκ³ λ¦¬μ¦˜β€™ μˆ˜μ—…μ„ λ“£κ³  κ³΅λΆ€ν•œ λ°”λ₯Ό μ •λ¦¬ν•œ κΈ€μž…λ‹ˆλ‹€. 지적은 μ–Έμ œλ‚˜ ν™˜μ˜μž…λ‹ˆλ‹€ :) 전체 ν¬μŠ€νŠΈλŠ” Algorithm ν¬μŠ€νŠΈμ—μ„œ ν™•μΈν•˜μ‹€ 수 μžˆμŠ΅λ‹ˆλ‹€.

2 minute read

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μ—μ„œ μ€‘μš”ν•œ 뢀뢄이기 λ•Œλ¬Έμ— λ§Žμ€ μ—°μŠ΅μ΄ ν•„μš”ν•˜λ‹€.


이번 μ±•ν„°μ—μ„œ λ‹€λ£¨λŠ” λ¬Έμ œλ“€μ€ μ•„λž˜μ™€ κ°™λ‹€.

(μƒλ‹Ήνžˆ λ§Žμ€ λ¬Έμ œκ°€ DP의 ν…Œν¬λ‹‰μ„ μ‚¬μš©ν•œλ‹€. 그만큼 DPκ°€ μ€‘μš”ν•˜λ‹€λŠ” 말!)

Categories:

Updated: