1. ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ๋ฌด์์ธ๊ฐ์? ๐ก
Greedy Algorithm
์ ๋งค ์ ํ์ ์๊ฐ๋ง๋ค ๋น์์ ๊ณ ๋ฅผ ์ ์๋ ์ต์ ์ ์ ํ์ง๋ฅผ ๊ณจ๋ผ๊ฐ๋ ๊ฒ์ด ์ ์ฒด์์ ๋ดค์ ๋ ์ต์ ์ ์ ํ์ด๋ผ๊ณ ๊ฐ์ ํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
์๋ฅผ ๋ค์ด ๋ค์๊ณผ ๊ฐ์ ๋ฌธ์ ๊ฐ ์๋ค๊ณ ํด๋ณด์.
ํ์ฌ A์ ์์ ์์ ๊ณ ๋ฅผ ์ ์๋ ์ ํ์ง ์ค C๊ฐ ์ต๋จ๊ฑฐ๋ฆฌ์ด๋ค. ๊ทธ๋ฌ๋ฏ๋ก C๋ฅผ ์ ํํ๋ค.
C ์์ ์์ ๊ณ ๋ฅผ ์ ์๋ ์ ํ์ง ์ค ์ต๋จ ๊ฑฐ๋ฆฌ๋ก ๊ฐ ์ ์๋ ๋
ธ๋๋ G์ด๋ค. ๋ฐ๋ผ์ G๋ฅผ ์ ํํ๋ค. ๋๋ฒ์ ์ ํ ํ ๋ฌด์กฐ๊ฑด F๋ฅผ ๋น์ฉ 0์ผ๋ก ๊ฐ ์ ์๋ค๊ณ ํ ๋, ์ ์ฒด ๋
ธ๋๋ ๋ค์๊ณผ ๊ฐ๋ค.
๋งค ์๊ฐ ๊ฐ ์ ์๋ ์ต์ ์ ์ ํ์ง๋ฅผ ๊ณจ๋๋๋ ์ ์ฒด์์ ๋ดค์ ๋๋ ์ต์ ์ ์ ํ์ด์๋ค. ์ด์ ๊ฐ์ด ๋งค ์๊ฐ์ ์ต์
= ์ ์ฒด์ ์ต์
์ด ์ฑ๋ฆฝํ ๋, ์ด๋ฌํ ๋
ผ๋ฆฌ๋ฅผ Greedy ์๊ณ ๋ฆฌ์ฆ
์ด๋ผ ํ๋ค.
2. ์ ์ฌ์ฉํ์ฃ ? ๐คทโ๏ธ
์... ์ ๋ฌํ ๊ฐ์ ์ด ์ฑ๋ฆฝํ๋ ๋ฌธ์ ๋ผ๋ฉด ๊ตณ์ด ๊ตฌํ์ผ๋ก ์์ ํ์์ ํ๋ ๊ฒ์ ์๊ฐ ๋ญ๋น์ด๊ธฐ ๋๋ฌธ์ด๋ค. ํ์ง๋ง ๊ฐ๋
์ค๋ช
์์ ๋ดค๋ค์ํผ, ๋งค ์๊ฐ์ ์ต์
= ์ ์ฒด์ ์ต์
์ด ์ฑ๋ฆฝํ ๋๋ง ์ด์ฉ์ด ๊ฐ๋ฅํ๋ค. ๋ฐ๋ผ์ ํด๋น ๊ฐ์ ์ด ์ฑ๋ฆฝํ๋์ง ๋ฌธ์ ๋ฅผ ํ๋ฉฐ ์ ์ฌํ ๋ด์ผ ํ๋ค.
3. ์ด๋ป๊ฒ ๊ตฌํํ์ฃ ? ๐
๋ค์ 3๊ฐ์ง ๊ฐ์ ์ ๋ฐ๋ฅธ๋ค.
- ์ฌ๊ท์ด๋ Loop์ด๋ ์ ํ์ ์๊ฐ์ด ์ค๋ฉด ํด๋น ์์ ์์ ๊ณ ๋ฅผ ์ ์๋ ์ต์ ์ ์ ํ์ง๋ฅผ ๊ณ ๋ฅธ๋ค.
- ํด๋น ์ ํ์ง๊ฐ ๋ฌธ์ ์ ์กฐ๊ฑด์ ์๋ฐํ์ง ์๋์ง ํ์ธํ๋ค.
- ์ ์ฒด ๋ฌธ์ ์ ๋ต์ด ๋์๋์ง ํ์ธํ๋ค. ๋ต์ด ์์ง ๋์ค์ง ์์๋ค๋ฉด 1๋ฒ์ ๋ฐ๋ณตํ๋ค.