user-img
๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜ 3
thumbnail
[๋ฐฑ์ค€] 1931 ํšŒ์˜์‹ค ๋ฐฐ์ • ์‰ฌ์šด ํ’€์ด ^^
1. ๋ฌธ์ œ ์„ค๋ช… ๐Ÿ“Œ๋ฌธ์ œ ๋งํฌํšŒ์˜์‹œ๊ฐ„์˜ ์‹œ์ž‘๊ณผ ๋์ด ์ฃผ์–ด์งˆ ๋•Œ, ์ตœ๋Œ€ํ•œ ๋งŽ์€ ๊ฐ•์˜๋ฅผ ํšŒ์˜์‹ค์— ๋ฐฐ์ •ํ•ด๋ผ (A ๊ฐ•์˜์˜ ๋์‹œ๊ฐ„๊ณผ B ๊ฐ•์˜์˜ ์‹œ์ž‘ ์‹œ๊ฐ„์ด ๊ฐ™์œผ๋ฉด ์—ฐ๋‹ฌ์•„ ๋ฐฐ์ •ํ•  ์ˆ˜ ์žˆ๋Š” ๊ฒƒ์œผ๋กœ ๊ฐ„์ฃผํ•œ๋‹ค.) 2. ์ ‘๊ทผ ๋ฐฉ์‹ ๐Ÿ—ƒ๏ธKEY WORDS: GREEDY ALGORITHMGreedy Algorithm์€ ์„ ํƒ์˜ ์ˆœ๊ฐ„์— ์ตœ์ ์˜ ์„ ํƒ์ง€๋ฅผ ๊ณ ๋ฅด๋Š” ๊ฒƒ์ด ์ „์ฒด ๋ฌธ์ œ์—์„œ ์ตœ์ ์˜ ์„ ํƒ์„ ํ•˜๋Š” ๊ฒƒ์ด๋ผ ๊ฐ€์ •ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.๋นจ๋ฆฌ ๋๋‚˜๋Š” ์ˆœ์œผ๋กœ ํšŒ์˜๋ฅผ ์ •๋ ฌ์ œ์ผ ๋นจ๋ฆฌ ๋๋‚˜๋Š” ํšŒ์˜๊ฐ€ A๋ผ๋ฉด A ํšŒ์˜ ์ดํ›„์— ์‹œ์ž‘ํ•  ์ˆ˜ ์žˆ์œผ๋ฉด์„œ๋„, ์ตœ๋Œ€ํ•œ ๋นจ๋ฆฌ ๋๋‚˜๋Š” ํšŒ์˜๋ฅผ ์„ ํƒํ•˜๋Š” ๊ฒƒ์ด ์ „์ฒด ๋ฌธ์ œ์—์„œ ๋ดค์„ ๋•Œ ์ตœ๋Œ€ํ•œ ๋งŽ์€ ๊ฐ•์˜๋ฅผ ๊ณ ๋ฅผ ์ˆ˜ ์žˆ๋Š” ๋ฐฉ๋ฒ•์ž„.2๋ฒˆ์„ ๋ชจ๋“  ํšŒ์˜๋ฅผ ๋Œ์•„๋ณด๋ฉฐ ๋” ์ด์ƒ ๊ณ ๋ฅผ ์ˆ˜ ์žˆ๋Š” ํšŒ์˜๊ฐ€ ์—†์„ ๋•Œ๊นŒ์ง€ ๋ฐ˜๋ณต 3. ์ฝ”๋“œ ์†Œ๊ฐœ ๐Ÿ”Ž..
2024.11.09
์•Œ๊ณ ๋ฆฌ์ฆ˜/๋ฌธ์ œ ํ’€์ด
thumbnail
๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ฐœ๋…
1. ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋ฌด์—‡์ธ๊ฐ€์š”? ๐Ÿ’กGreedy Algorithm์€ ๋งค ์„ ํƒ์˜ ์ˆœ๊ฐ„๋งˆ๋‹ค ๋‹น์‹œ์— ๊ณ ๋ฅผ ์ˆ˜ ์žˆ๋Š” ์ตœ์„ ์˜ ์„ ํƒ์ง€๋ฅผ ๊ณจ๋ผ๊ฐ€๋Š” ๊ฒƒ์ด ์ „์ฒด์—์„œ ๋ดค์„ ๋•Œ ์ตœ์„ ์˜ ์„ ํƒ์ด๋ผ๊ณ  ๊ฐ€์ •ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.์˜ˆ๋ฅผ ๋“ค์–ด ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋ฌธ์ œ๊ฐ€ ์žˆ๋‹ค๊ณ  ํ•ด๋ณด์ž.ํ˜„์žฌ A์˜ ์‹œ์ ์—์„œ ๊ณ ๋ฅผ ์ˆ˜ ์žˆ๋Š” ์„ ํƒ์ง€ ์ค‘ C๊ฐ€ ์ตœ๋‹จ๊ฑฐ๋ฆฌ์ด๋‹ค. ๊ทธ๋Ÿฌ๋ฏ€๋กœ C๋ฅผ ์„ ํƒํ•œ๋‹ค.C ์‹œ์ ์—์„œ ๊ณ ๋ฅผ ์ˆ˜ ์žˆ๋Š” ์„ ํƒ์ง€ ์ค‘ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋กœ ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๋…ธ๋“œ๋Š” G์ด๋‹ค. ๋”ฐ๋ผ์„œ G๋ฅผ ์„ ํƒํ•œ๋‹ค. ๋‘๋ฒˆ์˜ ์„ ํƒ ํ›„ ๋ฌด์กฐ๊ฑด F๋ฅผ ๋น„์šฉ 0์œผ๋กœ ๊ฐˆ ์ˆ˜ ์žˆ๋‹ค๊ณ  ํ•  ๋•Œ, ์ „์ฒด ๋…ธ๋“œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.๋งค ์ˆœ๊ฐ„ ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ์ตœ์„ ์˜ ์„ ํƒ์ง€๋ฅผ ๊ณจ๋ž๋”๋‹ˆ ์ „์ฒด์—์„œ ๋ดค์„ ๋•Œ๋„ ์ตœ์„ ์˜ ์„ ํƒ์ด์—ˆ๋‹ค. ์ด์™€ ๊ฐ™์ด ๋งค ์ˆœ๊ฐ„์˜ ์ตœ์„  = ์ „์ฒด์˜ ์ตœ์„  ์ด ์„ฑ๋ฆฝํ•  ๋•Œ, ์ด๋Ÿฌํ•œ ๋…ผ๋ฆฌ๋ฅผ Greedy ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ผ ํ•œ๋‹ค..
2024.11.07
์•Œ๊ณ ๋ฆฌ์ฆ˜/์•Œ๊ณ ๋ฆฌ์ฆ˜-์ด๋ก 
thumbnail
[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ๊ด‘๋ฌผ ์บ๊ธฐ ํ’€์ด java
1. ๋ฌธ์ œ ์„ค๋ช…๋ฌธ์ œ ๋งํฌ2. ์ ‘๊ทผ ๋ฐฉ์‹KEY WORD: GREEDY Algorithm๊ด‘๋ฌผ์„ ์บ๋Š” ๋น„์šฉ์„ ์ตœ์†Œํ™” ํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š”, ๋Œ ๊ณก๊ดญ์ด๋กœ ์บค์„ ๋•Œ, ๋น„์šฉ์ด ์ œ์ผ ๋งŽ์ด ๋“œ๋Š” ๊ตฌ๊ฐ„์ด ์•ž์— ์˜ค๋„๋ก, ๊ด‘๋ฌผ ๋ฆฌ์ŠคํŠธ๋ฅผ ์ •๋ ฌํ•˜๊ณ , ๊ตฌ๊ฐ„๋“ค์„ ์ˆœํšŒํ•˜๋ฉฐ, ๊ทธ๋•Œ ๊ทธ๋•Œ ์ตœ์„ ์˜ ๊ณก๊ดญ์ด๋กœ ์ผ์ฒ˜๋ฆฌ๋ฅผ ํ•ด์•ผํ•œ๋‹ค.๊ทธ ์˜๋ฏธ์—์„œ Greedy Algorithm์„ ์จ์•ผ ํ•˜๋Š” ๊ฒƒ์ด๋‹ค.๊ด‘๋ฌผ์˜ ํฌ๊ธฐ๊ฐ€ 50๋ฐ–์— ์•ˆ๋จ์œผ๋กœ ์‹œ๊ฐ„๋ณต์žก๋„ ๊ด€๋ จํ•ด์„œ ๊ฑฑ์ •ํ•  ๊ฒƒ์€ ์—†์„ ๊ฒƒ ๊ฐ™๋‹ค. ๊ทธ๋ ‡๋‹ค๋ฉด ํ•ด์•ผํ•  ์ผ์€,๊ด‘๋ฌผ List๋ฅผ 5๊ฐœ์”ฉ ์ž๋ฅธ๋‹ค. ๊ทธ๊ฒƒ์ด ์ผ์˜ ๋‹จ์œ„์ด๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.(๊ทผ๋ฐ ๊ด‘๋ฌผ์ด 5์˜ ๋ฐฐ์ˆ˜๋กœ ์•ˆ ๋งž์•„ ๋–จ์–ด์งˆ ์ˆ˜ ์žˆ๋‹ค. ๊ทธ๋Ÿฌ๋ฉด ๋งจ ๋งˆ์ง€๋ง‰์€ 3๊ฐœ๋‚˜ 4๊ฐœ๊ฐ€ ํ•˜๋‚˜์˜ ๋ฌถ์Œ์ด ๋  ์ˆ˜๋„ ์žˆ์Œ์œผ๋กœ ์ด๋ฅผ ์ฃผ์˜ํ•ด์„œ Loop๋ฅผ ์ง ๋‹ค.)๋‚˜๋ˆ ์ง„ ๊ด‘๋ฌผ ๋ฌถ์Œ์„ ๋Œ ๊ณก๊ดญ์ด๋กœ ์ž‘์—…ํ–ˆ์„ ๋•Œ ํ”ผ๋กœ..
2024.07.23
์•Œ๊ณ ๋ฆฌ์ฆ˜/๋ฌธ์ œ ํ’€์ด