[Swift] ํ๋ก๊ทธ๋๋จธ์ค ์ฌ ์ฐ๊ฒฐํ๊ธฐ
Problem ์ฝ๋ฉํ
์คํธ ์ฐ์ต - ์ฌ ์ฐ๊ฒฐํ๊ธฐ 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr Solution ํด๋น ๋ฌธ์ ๋ Greedy ๋ฌธ์ ์
๋๋ค. ๊ทธ ์ค์์๋ ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ํ์ด์ผํ๋ ๋ฌธ์ ์
๋๋ค. ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ์ด๋?๐ค "์ปดํจํฐ ๊ณผํ์์, ํฌ๋ฌ์ค์ปฌ ์๊ณ ๋ฆฌ์ฆ(์์ด: Kruskal’s algorithm)์ ์ต์ ๋น์ฉ ์ ์ฅ ๋ถ๋ถ ํธ๋ฆฌ๋ฅผ ์ฐพ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ๋ณ์ ๊ฐ์๋ฅผ {\displaystyle E}E, ๊ผญ์ง์ ์ ๊ฐ์๋ฅผ {\displaystyle V}V๋ผ๊ณ ํ๋ฉด ์ด ์๊ณ ๋ฆฌ์ฆ์ {\displaystyle {\color {Blue}O}(E\log V)}{\color {Blue}O}(E\log V)์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ค." ์ํค๋ฐฑ๊ณผ์ ์ด๋ ๊ฒ..
2021. 2. 20.
