๋ชฉ๋ก๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (115)

let's get IT with DAVINA ๐Ÿ’ป

[์•Œ๊ณ ๋ฆฌ์ฆ˜ ์œ ํ˜•] Greedy Algorithm

Greedy Algorithm (ํƒ์š• ์•Œ๊ณ ๋ฆฌ์ฆ˜) ์„ ํƒ์˜ ์ˆœ๊ฐ„๋งˆ๋‹ค ๋‹น์žฅ ๋ˆˆ์•ž์— ๋ณด์ด๋Š” ์ตœ์ ์˜ ์ƒํ™ฉ๋งŒ์„ ์ซ“์•„ ์ตœ์ข…์ ์ธ ํ•ด๋‹ต์— ๋„๋‹ฌํ•˜๋Š” ๋ฐฉ๋ฒ• Greedy Algorithm ๋ฌธ์ œ ํ•ด๊ฒฐ ๋‹จ๊ณ„ ๐Ÿ”ฝ ์„ ํƒ ์ ˆ์ฐจ(Selection Procedure): ํ˜„์žฌ ์ƒํƒœ์—์„œ์˜ ์ตœ์ ์˜ ํ•ด๋‹ต์„ ์„ ํƒํ•ฉ๋‹ˆ๋‹ค. ์ ์ ˆ์„ฑ ๊ฒ€์‚ฌ(Feasibility Check): ์„ ํƒ๋œ ํ•ด๊ฐ€ ๋ฌธ์ œ์˜ ์กฐ๊ฑด์„ ๋งŒ์กฑํ•˜๋Š”์ง€ ๊ฒ€์‚ฌํ•ฉ๋‹ˆ๋‹ค. ํ•ด๋‹ต ๊ฒ€์‚ฌ(Solution Check): ์›๋ž˜์˜ ๋ฌธ์ œ๊ฐ€ ํ•ด๊ฒฐ๋˜์—ˆ๋Š”์ง€ ๊ฒ€์‚ฌํ•˜๊ณ , ํ•ด๊ฒฐ๋˜์ง€ ์•Š์•˜๋‹ค๋ฉด ์„ ํƒ ์ ˆ์ฐจ๋กœ ๋Œ์•„๊ฐ€ ์œ„์˜ ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•ฉ๋‹ˆ๋‹ค. - ํƒ์š•์  ์„ ํƒ ์†์„ฑ(Greedy Choice Property) : ์•ž์˜ ์„ ํƒ์ด ์ดํ›„์˜ ์„ ํƒ์— ์˜ํ–ฅ์„ ์ฃผ์ง€ ์•Š์Šต๋‹ˆ๋‹ค. - ์ตœ์  ๋ถ€๋ถ„ ๊ตฌ์กฐ(Optimal Substructure) : ๋ฌธ์ œ์— ๋Œ€ํ•œ ..

DEV_IN/Algorithm 2023. 3. 7. 01:25