๊ด€๋ฆฌ ๋ฉ”๋‰ด

๋ชฉ๋ก๊ทธ๋ฆฌ๋””์•Œ๊ณ ๋ฆฌ์ฆ˜ (1)

CS Student’s SAP&Tech Journey๐Ÿ’ซ

[์•Œ๊ณ ๋ฆฌ์ฆ˜] ๊ทธ๋ฆฌ๋””(Greedy) ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ž€

1. ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜(ํƒ์š•๋ฒ•)์ด๋ž€?๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜(ํƒ์š•๋ฒ•)์€ ํ˜„์žฌ ์ƒํ™ฉ์—์„œ ์ง€๊ธˆ ๋‹น์žฅ ์ข‹์€ ๊ฒƒ๋งŒ ๊ณ ๋ฅด๋Š” ๋ฐฉ๋ฒ•์„ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค.์‰ฝ๊ฒŒ ๋งํ•˜๋ฉด ํƒ์š•์Šค๋Ÿฝ๊ฒŒ ์ตœ๊ณ ์˜ ์„ ํƒ๋งŒ ์ทจํ•˜๋Š” ๊ฒƒ์„ ๋งํ•ฉ๋‹ˆ๋‹ค.์ผ๋ฐ˜์ ์ธ ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋ฌธ์ œ๋ฅผ ํ’€๊ธฐ ์œ„ํ•œ ์ตœ์†Œํ•œ์˜ ์•„์ด๋””์–ด๋ฅผ ๋– ์˜ฌ๋ฆด ์ˆ˜ ์žˆ๋Š” ๋Šฅ๋ ฅ์„ ์š”๊ตฌํ•ฉ๋‹ˆ๋‹ค.๊ทธ๋ฆฌ๋”” ํ•ด๋ฒ•์€ ๊ทธ ์ •๋‹น์„ฑ ๋ถ„์„์ด ์ค‘์š”ํ•ฉ๋‹ˆ๋‹ค.๋‹จ์ˆœํžˆ ๊ฐ€์žฅ ์ข‹์•„ ๋ณด์ด๋Š” ๊ฒƒ์„ ๋ฐ˜๋ณต์ ์œผ๋กœ ์„ ํƒํ•ด๋„ ์ตœ์ ์˜ ํ•ด๋ฅผ ๊ตฌํ•  ์ˆ˜ ์žˆ๋Š”์ง€ ๊ฒ€ํ† ํ•ฉ๋‹ˆ๋‹ค.โœ”๏ธ ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ํ•ญ์ƒ ์ตœ์ ์˜ ํ•ด๋ฅผ ๋ณด์žฅํ•˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค.์ผ๋ฐ˜์ ์ธ ์ƒํ™ฉ์—์„œ ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์ตœ์ ์˜ ํ•ด๋ฅผ ๋ณด์žฅํ•  ์ˆ˜ ์—†์„ ๋•Œ๊ฐ€ ๋งŽ์Šต๋‹ˆ๋‹ค.ํ•˜์ง€๋งŒ ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ์—์„œ์˜ ๋Œ€๋ถ€๋ถ„์˜ ๊ทธ๋ฆฌ๋”” ๋ฌธ์ œ๋Š” ํƒ์š•๋ฒ•์œผ๋กœ ์–ป์€ ํ•ด๊ฐ€ ์ตœ์ ์˜ ํ•ด๊ฐ€ ๋˜๋Š” ์ƒํ™ฉ์—์„œ, ์ด๋ฅผ ์ถ”๋ก ํ•  ์ˆ˜ ์žˆ์–ด์•ผ ํ’€๋ฆฌ๋„๋ก ์ถœ์ œ๋ฉ๋‹ˆ๋‹ค. ํŠธ๋ฆฌ์—์„œ ๊ฒฝ๋กœ๋ฅผ ์ด๋™..