๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
728x90
๋ฐ˜์‘ํ˜•

ํฌ๋ฃจ์Šค์ปฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜1

[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.
728x90
๋ฐ˜์‘ํ˜•

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”