๐Ÿ“‚ ์•Œ๊ณ ๋ฆฌ์ฆ˜/์ตœ๋‹จ ๊ฒฝ๋กœ

    ํ”Œ๋กœ์ด๋“œ-์™€์ƒฌ(Floyd-Warshall) ์•Œ๊ณ ๋ฆฌ์ฆ˜

    1. ๊ฐœ๋… ๐Ÿ•‍๐Ÿฆบ  ํ”Œ๋กœ์ด๋“œ-์™€์ƒฌ(Floyd-Warshall) ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ž€ ๋ชจ๋“  ์ •์ ์—์„œ ๋‹ค๋ฅธ ๋ชจ๋“  ์ •์ ๊นŒ์ง€์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ๊ตฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ๋‹ค์ต์ŠคํŠธ๋ผ(Dijkstra) ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ ๋‹ค๋ฅด๊ฒŒ ์Œ์˜ ๊ฐ€์ค‘์น˜๋ฅผ ํ—ˆ์šฉํ•œ๋‹ค๋Š” ๊ฒŒ ํŠน์ง•์ด๋ผ๊ณ  ํ•  ์ˆ˜ ์žˆ๋‹ค.  ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๊ฐ„๋‹จํ•˜๊ฒŒ ์„ค๋ช…ํ•˜์ž๋ฉด ์ถœ๋ฐœ ์ •์ ์œผ๋กœ๋ถ€ํ„ฐ ๋ชจ๋“  ์ •์ ๊นŒ์ง€์˜ ์ตœ๋‹จ๊ฒฝ๋กœ๋ฅผ ๊ตฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ๋‹ค์ต์ŠคํŠธ๋ผ๋ฅผ ์ด์šฉํ•˜์—ฌ ํ”Œ๋กœ์ด๋“œ-์™€์ƒฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๊ตฌํ˜„ํ•œ๋‹ค๊ณ  ํ•˜๋ฉด ์ถœ๋ฐœ ์ •์ ์„ ๋ชจ๋“  ์ •์ ์˜ ๊ฐœ์ˆ˜๋งŒํผ ์„ค์ •ํ•ด ์ฃผ๋ฉด ๋œ๋‹ค.  ์ˆœ์ฐจ ํƒ์ƒ‰ ๋ฐฉ๋ฒ•์œผ๋กœ ๋‹ค์ต์ŠคํŠธ๋ผ๋ฅผ ๊ตฌํ˜„ํ•˜๋ฉด O(V^2)์ด๊ณ , ๋ชจ๋“  ์ •์ ์„ ์ถœ๋ฐœ ์ •์ ์œผ๋กœ ํ•œ๋‹ค๊ณ  ํ•˜๋ฉด O(V * V^2) = O(V^3)์ด ๋˜๊ฒŒ ๋œ๋‹ค. ํ”Œ๋กœ์ด๋“œ-์™€์ƒฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์‹œ๊ฐ„๋ณต์žก๋„ ๋˜ํ•œ O(V^3)์œผ๋กœ ๊ฐ™๋‹ค. ํ•˜์ง€๋งŒ ํ”Œ๋กœ์ด๋“œ-์™€์ƒฌ ์•Œ..

    ๋‹ค์ต์ŠคํŠธ๋ผ(Dijkstra) ์•Œ๊ณ ๋ฆฌ์ฆ˜

    1. ๊ธฐ๋ณธ ๊ฐœ๋… ๐Ÿ„ 1. ์ตœ๋‹จ ๊ฒฝ๋กœ ๊ฐ€์ค‘์น˜ ๊ทธ๋ž˜ํ”„์—์„œ ๋‘ ์ •์  ์‚ฌ์ด์˜ ๊ฒฝ๋กœ๋“ค ์ค‘์—์„œ ๊ฐ€์ค‘์น˜์˜ ํ•ฉ์ด ์ตœ์†Œ๊ฐ€ ๋˜๋Š” ๊ฒฝ๋กœ 2. ๋Œ€ํ‘œ์ ์ธ ์ตœ๋‹จ ๊ฒฝ๋กœ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋‹ค์ต์ŠคํŠธ๋ผ(Dijkstra) ๋ฒจ๋งŒํฌ๋“œ(Bellman-Ford) ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ(Floyd-Warshall) ์ •์˜ ์ถœ๋ฐœ ์ •์ ๋กœ๋ถ€ํ„ฐ ๋ชจ๋“  ์ •์ ๊นŒ์ง€์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ๊ตฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ถœ๋ฐœ ์ •์ ๋กœ๋ถ€ํ„ฐ ๋ชจ๋“  ์ •์ ๊นŒ์ง€์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ๊ตฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ชจ๋“  ์ •์ ์—์„œ ๋‹ค๋ฅธ ๋ชจ๋“  ์ •์ ๊นŒ์ง€์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ๊ตฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ํŠน์ง• ์Œ์˜ ๊ฐ€์ค‘์น˜๋ฅผ ํ—ˆ์šฉ X ์Œ์˜ ๊ฐ€์ค‘์น˜๋ฅผ ํ—ˆ์šฉ O ์Œ์˜ ๊ฐ€์ค‘์น˜๋ฅผ ํ—ˆ์šฉ O ์‚ฌ์šฉํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜ DP ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์‹œ๊ฐ„๋ณต์žก๋„ O(V ^ 2) ๋˜๋Š” O(E log V) O(V ^ 2) ๋˜๋Š” O(E log V) O(V ^ 3) 2. ๋‹ค์ต์ŠคํŠธ๋ผ(..