[์๊ณ ๋ฆฌ์ฆ] ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ (Greedy Algorithm)
ยท
๐งฉ Problem Solving/[์๊ณ ๋ฆฌ์ฆ for PS]
๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ(Greedy Algorithm) ํ์๋ฒ์ผ๋ก๋ ์๋ ค์ง ๋ฌธ์ ํด๊ฒฐ ๋ฐฉ๋ฒ์ด๋ค. ์ด๋ฆ ๊ทธ๋๋ก ์ฃผ์ด์ง ๋ฌธ์ ๋ฅผ ๋จ์ํ๊ฒ ํ์์ ์ผ๋ก ํธ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ํ์์ ์ด๋ผ๋ ๋ง์ 'ํ์ฌ ์ํฉ์์ ๊ฐ์ฅ ์ข์ ๊ฒ๋ง ๊ณ์ ๊ณ ๋ฅด๋ ๋ฐฉ๋ฒ'์ ๋งํ๋ค. ๊ทธ๋ฆฌ๋ ๋ฐฉ๋ฒ์ ์๊ณ ๋ฆฌ์ฆ์ ๊ฐ ๋จ๊ณ์์ ๊ทธ ์๊ฐ์ ์ต์ ์ด๋ผ๊ณ ์๊ฐํ๋ ๊ฒ์ ์ ํํ๋ค. ๋ํ ๊ทธ๋ฆฌ๋๋ก ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ๋๋ ํ์ฌ์ ์ ํ์ด ๋ง์ง๋ง ํด๋ต์ ์ต์ ์ฑ์ ํด์น์ง ์์ ๋ ์ฌ์ฉํ ์ ์๋ค. ์ฐ๋ฆฌ๋ ๊ทธ๋ฆฌ๋ ๋ฌธ์ ๋ฅผ ํ ๋๋ ๋ค์ต์คํธ๋ผ(dijkstra) ๋๋ ์์ ์ ๋ ฌ(topological sort) ์๊ณ ๋ฆฌ์ฆ์ฒ๋ผ ํน์ ์๊ณ ๋ฆฌ์ฆ ์ฝ๋๋ฅผ ๋ฏธ๋ฆฌ ์ ํ์๋ ์๋ค. ๋์ ์ฐ๋ฆฌ๋ ๋ฌธ์ ๋ฅผ ๋ดค์ ๋ '๊ทธ ๋ฌธ์ ๊ฐ ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ํด๊ฒฐํ ์ ์๋์ง'์ ๋ํด ์์์ผ ํ๋ค. ๊ทธ๋ผ ์ด๋ป๊ฒ ์ ์ ์..