[Swift] ํ๋ก๊ทธ๋๋จธ์ค 2018 Summer/Winter Coding ๋ฐฐ๋ฌ
Problem ์ฝ๋ฉํ
์คํธ ์ฐ์ต - ๋ฐฐ๋ฌ 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr Solution ํด๋น ๋ฌธ์ ๋ ํ ์ ์ ์์์ ๊ฑฐ๋ฆฌ๋ง ๊ตฌํ๋ฉด ๋๊ธฐ ๋๋ฌธ์ ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ํ์ด์ผ ํ๋ ๋ฌธ์ ๋ค. (ํ๋ก์ด๋๋ก ํ๋ฉด ํจ์จ์ ์ด์ง ์์ง๋ง ํ๋ฆฌ๊ธด ํ๋ฆฐ๋ค...) ๋ค์ต์คํธ๋ผ ํ์ด 1.๋ชจ๋ ๊ฑฐ๋ฆฌ๋ฅผ ์ ์ฅํ ์ด์ฐจ์ ๋ฐฐ์ด์ ๋ง๋ค์ด์ค. (allDistances ๋ณ์๋ฅผ ์ฐธ๊ณ ํด์ฃผ์ธ์!) 2.๋ค์ต์คํธ๋ผ๋ก ์์ํ๋ ์ ์ ์์ ๊ฐ์ฅ ๊ฐ๊น์ด ๊ฑฐ๋ฆฌ๋ฅผ ์ฐพ์์ค. (dijkstra ํจ์๋ฅผ ์ฐธ๊ณ ํด์ฃผ์ธ์!) 4.1๊ณผ ์ฐ๊ฒฐ๋ ์ ์ ์ค ์ฃผ์ด์ง ์๊ฐ ..
2021. 5. 21.
[Swift] ํ๋ก๊ทธ๋๋จธ์ค ๊ฐ์ฅ ๋จผ ๋
ธ๋ (์ฌ์ด ํ์ด ํฌํจ)
Problem ์ฝ๋ฉํ
์คํธ ์ฐ์ต - ๊ฐ์ฅ ๋จผ ๋
ธ๋ 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr Solution ํด๋น ๋ฌธ์ ๋ BFS๋ก ํ์ด์ผ ํ๋ ๋ฌธ์ ์
๋๋ค. 1๋ถํฐ ์์ํด์ 1๊ณผ ์ฐ๊ฒฐ๋ ์ซ์๋ค ๊ทธ๋ฆฌ๊ณ ์ฐ๊ฒฐ๋ ์ซ์๋ค๊ณผ ์ฐ๊ฒฐ๋ ์ซ์๋ค์ ๋์ดํด์ค๋๋ค. ๋์ดํ๋ฉด ์๋ ๊ทธ๋ฆผ์ฒ๋ผ ๋ ๊ฒ์
๋๋ค. ์ฌ๊ธฐ์ ์ฐ๋ฆฌ๋ ํ ๋ผ์ธ์ด ์ฐ๊ฒฐ๋ ๋๋ง๋ค ๋ผ์ธ์ ์ซ์๋ฅผ ๋๋ ค๊ฐ์ค๋๋ค. ์ ๊ทธ๋ฆผ์์ ์ผ์ชฝ ํ๋์ ์ซ์ ๋ชจ์์ ์ฐธ๊ณ ํด์ฃผ์ธ์. ํ์ง๋ง ๋ผ์ธ 2๊น์ง ์์ ๋ ๋ฌธ์ ์ ์ด ์๊ธฐ๋๋ฐ์. 2์ ์ฐ๊ฒฐ๋ 1,3,4,5 ์ค์์ 1๊ณผ 3์ ๊ฐ ํ์๊ฐ ์์ต๋๋ค. ์๋ํ๋ฉด ์ด๋ฏธ ์์์ ์ฐ๊ฒฐ์ ๋ง๋ค์ด์ค ์ซ์๋ค์ด๊ธฐ ๋๋ฌธ์
๋๋ค. ์ด ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด์ ์ด๋ฏธ ..
2021. 3. 7.
[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.