๐˜ฟ๐™‹

uuuouuoยท2022๋…„ 7์›” 25์ผ
0
post-thumbnail

๐Ÿ“– ๋™์  ๊ณ„ํš๋ฒ•(Dynamic Programming)


  • ์™„์ „๊ฒ€์ƒ‰์„ ์Šค๋งˆํŠธํ•˜๊ฒŒ ํ•˜๋Š” ๋ฐฉ๋ฒ•
  • ์žฌ๊ท€ + ๋ฉ”๋ชจ์ด์ œ์ด์…˜ ์ด๋ผ๊ณ  ํ•  ์ˆ˜ ์žˆ์Œ
  • ์ ํ™”์‹์œผ๋กœ ํ‘œํ˜„ ๊ฐ€๋Šฅ

๐Ÿ’ฌ ๋ฉ”๋ชจ์ด์ œ์ด์…˜


  • ์ปดํ“จํ„ฐ ํ”„๋กœ๊ทธ๋žจ์„ ์‹คํ–‰ํ•  ๋•Œ ์ด์ „ ๊ณ„์‚ฐ ๊ฐ’์„ ๋ฉ”๋ชจ๋ฆฌ์— ์ €์žฅํ•ด์„œ ๋งค๋ฒˆ ๋‹ค์‹œ ๊ณ„์‚ฐํ•˜์ง€ ์•Š๋„๋ก ํ•˜๋Š” ๊ฒƒ
  • ์ „์ฒด์ ์ธ ์‹คํ–‰ ์†๋„๋ฅผ ๋น ๋ฅด๊ฒŒ ํ•˜๋Š” ๊ธฐ์ˆ 
  • ๋™์  ๊ณ„ํš๋ฒ•์˜ ํ•ต์‹ฌ ๊ธฐ์ˆ 

๋ฌธ์ œ์ 

  • ์ถ”๊ฐ€์ ์ธ ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์ด ํ•„์š”
  • ์žฌ๊ท€ ํ•จ์ˆ˜ ํ˜ธ์ถœ๋กœ ์ธํ•œ ์‹œ์Šคํ…œ ํ˜ธ์ถœ ์Šคํƒ์„ ์‚ฌ์šฉํ•˜๊ฒŒ ๋˜๊ณ  ์‹คํ–‰ ์†๋„ ์ €ํ•˜ ๋˜๋Š” ์˜ค๋ฒ„ํ”Œ๋กœ์šฐ ๋ฐœ์ƒ ๊ฐ€๋Šฅ
    • ๋ฐ˜๋ณต๋ฌธ์œผ๋กœ ๊ฐ€๋Šฅํ•˜๋ฉด ๋ฐ˜๋ณต๋ฌธ์œผ๋กœ ์ˆ˜ํ–‰

๐Ÿ’ฌ ๋™์  ๊ณ„ํš ์•Œ๊ณ ๋ฆฌ์ฆ˜


  • ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ ๊ฐ™์ด ์ตœ์ ํ™” ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜
  • ์ตœ์ ํ™” ๋ฌธ์ œ : ์ตœ์ (์ตœ๋Œ€๊ฐ’์ด๋‚˜ ์ตœ์†Œ๊ฐ’ ๊ฐ™์€)๊ฐ’์„ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ
    • ํ•ด๋‹น ๋ฌธ์ œ์— ์—ฌ๋Ÿฌ ํ•ด๊ฐ€ ์žˆ์„ ์ˆ˜ ์žˆ์Œ
    • The ์ตœ์ ํ•ด๊ฐ€ ์•„๋‹ˆ๋ผ an ์ตœ์ ํ•ด ๊ตฌํ•˜๋Š” ๊ฒƒ
  • ๋จผ์ œ ์ž‘์€ ๋ถ€๋ถ„ ๋ฌธ์ œ๋“ค์˜ ํ•ด๋ฅผ ๊ตฌํ•˜๊ณ  ์ด๋“ค์„ ์ด์šฉํ•ด ๋ณด๋‹ค ํฐ ํฌ๊ธฐ์˜ ๋ถ€๋ถ„ ๋ฌธ์ œ๋“ค์„ ํ•ด๊ฒฐํ•ด, ์ตœ์ข…์ ์œผ๋กœ ์›๋ž˜ ์ฃผ์–ด์ง„ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜

โ—พ ๋™์  ๊ณ„ํš๋ฒ•์˜ ์ ์šฉ ์š”๊ฑด

์ตœ์  ๋ถ€๋ถ„๋ฌธ์ œ ๊ตฌ์กฐ(Optimal substructure)

  • ์–ด๋–ค ๋ฌธ์ œ๊ฐ€ ์ตœ์ ์ผ ๋•Œ ๊ทธ ํ•ด๋ฅผ ๊ตฌ์„ฑํ•˜๋Š” ์ž‘์€ ๋ฌธ์ œ๋“ค์˜ ํ•ด ์—ญ์‹œ ์ตœ์ ์ด์–ด์•ผ ํ•จ
  • ๋™์  ๊ณ„ํš๋ฒ•์˜ ๋ฐฉ๋ฒ• ์ž์ฒด๊ฐ€ ํฐ ๋ฌธ์ œ์˜ ์ตœ์  ํ•ด๋ฅผ ์ž‘์€ ๋ฌธ์ œ์˜ ์ตœ์  ํ•ด๋“ค์„ ์ด์šฉํ•˜์—ฌ ๊ตฌํ•˜๊ธฐ ๋•Œ๋ฌธ์— ๋งŒ์•ฝ ํฐ ๋ฌธ์ œ์˜ ์ตœ์  ํ•ด๋ฅผ ์ž‘์€ ๋ฌธ์ œ๋“ค์˜ ์ตœ์ ํ™”์˜ ํ•ด๋“ค๋กœ ๊ตฌ์„ฑ๋˜์ง€ ์•Š์œผ๋ฉด ์ ์šฉ ๋ถˆ๊ฐ€

์ค‘๋ณต ๋ถ€๋ถ„๋ฌธ์ œ ๊ตฌ์กฐ(Overlapping subproblems)

  • DP๋Š” ํฐ ๋ฌธ์ œ๋ฅผ ์ด๋ฃจ๋Š” ์ž‘์€ ๋ฌธ์ œ๋“ค์„ ๋จผ์ € ํ•ด๊ฒฐ ํ›„ ์ž‘์€ ๋ฌธ์ œ๋“ค์˜ ์ตœ์  ํ•ด๋ฅผ ์ด์šฉํ•ด ์ˆœํ™˜์ ์œผ๋กœ ํฐ ๋ฌธ์ œ ํ•ด๊ฒฐ
    • ์ˆœํ™˜์ ์ธ ๊ด€๊ณ„๋ฅผ ํ‘œํ˜„ํ•˜๊ธฐ ์œ„ํ•ด ๋™์  ๊ณ„ํš๋ฒ•์—์„œ๋Š” ์ผ๋ฐ˜์ ์œผ๋กœ ์ ํ™”์‹ ์‚ฌ์šฉ
  • ์ˆœํ™˜์ ์ธ ์„ฑ์งˆ ๋•Œ๋ฌธ์— ์ด์ „์— ๊ณ„์‚ฐ๋˜์—ˆ๋˜ ์ž‘์€ ๋ฌธ์ œ์˜ ํ•ด๊ฐ€ ํ•„์š”ํ•˜๊ฒŒ ๋˜๋Š”๋ฐ, ์ด๋ฅผ ์œ„ํ•ด DP์—์„œ๋Š” ์ด๋ฏธ ํ•ด๊ฒฐ๋œ ์ž‘์€ ๋ฌธ์ œ์˜ ํ•ด๋ฅผ ์ €์žฅ ๊ณต๊ฐ„์— ์ €์žฅํ•˜๊ฒŒ ๋จ
  • ์ด ์ €์žฅ๋œ ํ•ด๋“ค์„ ์ €์žฅ ๊ณต๊ฐ„(table)์˜ ์ฐธ์กฐ๋ฅผ ํ†ตํ•ด์„œ ์ค‘๋ณต๋œ ๊ณ„์‚ฐ ํ”ผํ•  ์ˆ˜ ์žˆ์Œ

๐Ÿ’ฌ DP ์ ์šฉ ์ ‘๊ทผ ๋ฐฉ๋ฒ•


  • ์ตœ์ ํ•ด ๊ตฌ์กฐ์˜ ํŠน์„ฑ ํŒŒ์•…
    • ๋ฌธ์ œ๋ฅผ ๋ถ€๋ถ„ ๋ฌธ์ œ๋กœ ๋‚˜๋ˆ”
  • ์ตœ์ ํ•ด์˜ ๊ฐ’์„ ์žฌ๊ท€์ ์œผ๋กœ ์ •์˜
    • ๋ถ€๋ถ„ ๋ฌธ์ œ์˜ ์ตœ์ ํ•ด ๊ฐ’์— ๊ธฐ๋ฐ˜ํ•ด ๋ฌธ์ œ์˜ ์ตœ์ ํ•ด ๊ฐ’ ์ •์˜
  • ์ƒํ–ฅ์‹ ๋ฐฉ๋ฒ•์œผ๋กœ ์ตœ์ ํ•ด์˜ ๊ฐ’ ๊ณ„์‚ฐ
    • ๊ฐ€์žฅ ์ž‘์€ ๋ถ€๋ถ„ ๋ฌธ์ œ๋ถ€ํ„ฐ ํ•ด๋ฅผ ๊ตฌํ•˜๊ณ  ํ…Œ์ด๋ธ” ์ €์žฅ
    • ํ…Œ์ด๋ธ”์— ์ €์žฅ๋˜์žˆ๋Š” ๋ถ€๋ถ„ ๋ฌธ์ œ์˜ ํ•ด๋ฅผ ์ด์šฉํ•ด์„œ ์ ์ฐจ์ ์œผ๋กœ ์ƒ์œ„ ๋ถ€๋ถ„ ๋ฌธ์ œ์˜ ์ตœ์ ํ•ด ๊ตฌํ•จ (์ƒํ–ฅ์‹ ๋ฐฉ๋ฒ•)

๐Ÿ’ฌ ๋ถ„ํ•  ์ •๋ณต๊ณผ ๋™์  ๊ณ„ํš๋ฒ• ๋น„๊ต


๋ถ„ํ•  ์ •๋ณต

  • ์—ฐ๊ด€ ์—†๋Š” ๋ถ€๋ถ„ ๋ฌธ์ œ๋กœ ๋ถ„ํ• 
  • ๋ถ€๋ถ„ ๋ฌธ์ œ๋ฅผ ๋…๋ฆฝ, ์žฌ๊ท€์ ์œผ๋กœ ํ•ด๊ฒฐ
  • ๋ถ€๋ถ„ ๋ฌธ์ œ์˜ ํ•ด๋ฅผ ๊ฒฐํ•ฉ
    • ๋ณ‘ํ•ฉ์ •๋ ฌ, ํ€ต์ •๋ ฌ
  • ํ•˜ํ–ฅ์‹ ๋ฐฉ๋ฒ•์œผ๋กœ ์ ‘๊ทผ

DP

  • ๋ถ€๋ถ„ ๋ฌธ์ œ๋“ค์ด ์—ฐ๊ด€์ด ์—†์œผ๋ฉด ์ ์šฉ ๋ถˆ๊ฐ€๋Šฅ
    • ์ฆ‰, ๋ถ€๋ถ„ ๋ฌธ์ œ๋“ค์€ ๋” ์ž‘์€ ๋ถ€๋ถ„ ๋ฌธ์ œ๋“ค์„ ๊ณต์œ 
  • ๋ชจ๋“  ๋ถ€๋ถ„ ๋ฌธ์ œ๋ฅผ ํ•œ๋ฒˆ๋งŒ ๊ณ„์‚ฐํ•˜๊ณ  ๊ฒฐ๊ณผ๋ฅผ ์ €์žฅ ํ›„ ์žฌ์‚ฌ์šฉ
    • ๋ถ„ํ•  ์ •๋ณต์€ ๊ฐ™์€ ๋ถ€๋ถ„ ๋ฌธ์ œ๊ฐ€ ๋‚˜ํƒ€๋‚  ๊ฒฝ์šฐ ๋‹ค์‹œ ๊ณ„์‚ฐ
  • ์ƒํ–ฅ์‹ ๋ฐฉ๋ฒ•์œผ๋กœ ์ ‘๊ทผ

0๊ฐœ์˜ ๋Œ“๊ธ€