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

๋‹ค์ต์ŠคํŠธ๋ผ2

[Algorithm] ๋‹ค์ต์ŠคํŠธ๋ผ(Dijkstra) ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ž€? (feat.Swift) ์•ˆ๋…•ํ•˜์„ธ์š” Foma ๐Ÿ‘Ÿ ์ž…๋‹ˆ๋‹ค! ์˜ค๋Š˜์€ ๊ทธ๋ž˜ํ”„ ๋ฌธ์ œ์—์„œ ์•„์ฃผ ๋นˆ๋ฒˆํ•˜๊ฒŒ ์‚ฌ์šฉ๋˜๋Š” ๋‹ค์ต์ŠคํŠธ๋ผ๋ผ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ๋Œ€ํ•ด์„œ ์•Œ์•„๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค. ๋ฐ”๋กœ ์‹œ์ž‘ํ• ๊ฒŒ์š”! ๋‹ค์ต์ŠคํŠธ๋ผ๋ž€? ๐Ÿค” ๋‚˜๋ฌด ์œ„ํ‚ค์—๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ •์˜๋˜์–ด์žˆ์Šต๋‹ˆ๋‹ค. "์Œ์˜ ๊ฐ€์ค‘์น˜๊ฐ€ ์—†๋Š” ๊ทธ๋ž˜ํ”„์˜ ํ•œ ์ •์ ์—์„œ ๋ชจ๋“  ์ •์ ๊นŒ์ง€์˜ ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐ๊ฐ ๊ตฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค." ์‰ฝ๊ฒŒ ๋งํ•˜๋ฉด ํ•œ ์ •์ ์—์„œ ๋‹ค๋ฅธ ์ •์ ์œผ๋กœ ์ด๋™ํ•  ๋•Œ ๊ฐ€์žฅ ๋น ๋ฅธ ๊ธธ์„ ์ฐพ์•„์ฃผ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด์—์š”. ๊ทธ๋ž˜ํ”„ ์„ค๋ช… ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ทธ๋ž˜ํ”„๊ฐ€ ์žˆ๋‹ค๊ณ  ๊ฐ€์ •ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. ์‹œ์ž‘ ์ •์ ์€ 1๋กœ ๋ชฉํ‘œ ์ •์ ์„ 4๋กœ ๋‘์—ˆ์„ ๋•Œ ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ๊ฑฐ๋ฆฌ๋Š” ๋ช‡์ผ๊นŒ์š”? 1 - 5 - 4 ๋กœ ๊ฐ€๋Š” ๊ฒฝ์šฐ๊ฐ€ 3 + 1 = 4๋กœ ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ๊ธธ์ด๊ฒ ์ฃ ? ์ด๋ ‡๊ฒŒ ๊ฐ„๋‹จํžˆ ๋ณด์ด๋Š” ๊ฒฝ๋กœ๋Š” ๋ˆˆ์œผ๋กœ ์‰ฝ๊ฒŒ ์ฐพ์„ ์ˆ˜ ์žˆ์ง€๋งŒ ๋ณต์žกํ•œ ๊ฒฝ๋กœ์ผ์ˆ˜๋ก ์ฐพ๊ธฐ๊ฐ€ ์–ด๋ ค์›Œ์งˆ ๊ฒƒ์ž…๋‹ˆ๋‹ค. ์ด.. 2021. 5. 22.
[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.
728x90
๋ฐ˜์‘ํ˜•