๐ ์๊ณ ๋ฆฌ์ฆ/์ต๋จ ๊ฒฝ๋ก

ํ๋ก์ด๋-์์ฌ(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. ๋ค์ต์คํธ๋ผ(..