| ์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | ||||
| 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| 18 | 19 | 20 | 21 | 22 | 23 | 24 |
| 25 | 26 | 27 | 28 | 29 | 30 | 31 |
- python
- ๋ฐฑ์ค ์ฝํ๋ฆฐ
- ์๋ฐ ์๊ณ ๋ฆฌ์ฆ
- Swift
- ์๋ฐ
- ์ฝํ๋ฆฐ
- ์๊ณ ๋ฆฌ์ฆ
- ๋ฏธ๊ตญ์ฃผ์
- Vue.js
- GIT
- Kotlin
- ์ฝํ๋ฆฐ ์คํ
- ํ์ด์ฌ
- vue3
- js
- java ์ฝ๋ฉ ํ ์คํธ
- javascript
- kotlin algorithm
- CI/CD
- pnpm
- Java
- ๋ฐฐ๋น์ฃผ
- ๋ฐฑ์ค
- linux
- ํ์ฝํ
- kotlin ์๊ณ ๋ฆฌ์ฆ
- ๋ฏธ๊ตญ๋ฐฐ๋น์ฃผํฌ์
- ํ๋ก๊ทธ๋๋จธ์ค
- ์๋ฐ์คํฌ๋ฆฝํธ
- ์ฝํ๋ฆฐ ์๊ณ ๋ฆฌ์ฆ
- Today
- Total
๋ชฉ๋กFloyd Warshall (1)
๐ ์ ์ด์ ๋จธ๋ฆฟ์์ผ๋ก
[Algorithm] ํ๋ก์ด๋ ์์ฌ(Floyd Warshall) ์๊ณ ๋ฆฌ์ฆ(ft.ํ์ด์ฌ)
๐ฉ ํ๋ก์ด๋ ์์ฌ ์๊ณ ๋ฆฌ์ฆ ํ์ด์ฌ ๊ตฌํ ํ๋ก์ด๋ ์์ฌ์ ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ๊ณผ ๊ฐ์ด ์ต๋จ๊ฑฐ๋ฆฌ ํน์ ์ต์๋น์ฉ์ ๊ตฌํ๋ ์๊ณ ๋ฆฌ์ฆ์ ๋๋ค. ํ๋ก์ด๋ ์์ฌ์ ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ๊ณผ๋ ๋ฌ๋ฆฌ ๋ชจ๋ ๋ ธ๋์์ ๋ค๋ฅธ ๋ชจ๋ ๋ ธ๋๋ค๊น์ง์ ์ต์ ๊ฑฐ๋ฆฌ(ํน์ ์ต์๋น์ฉ)์ ๊ตฌํ๊ธฐ ๋๋ฌธ์ "์ด๋๊ฐ๋ฅผ ๊ฒฝ์ ํ๋ค."๋ผ๋ ์กฐ๊ฑด์ด ์ฃผ์ด์ง ๋, ์ฌ์ฉ์ ๊ณ ๋ คํ๊ธฐ ์ข์ ์๊ณ ๋ฆฌ์ฆ ์ ๋๋ค. ๋ค๋ง, ์ถ๋ฐ์ (s), ๋์ฐฉ์ง์ (e), ๊ฒฝ์ ์ง(p)์ ๋ชจ๋ ๋ ธ๋๋ฅผ ๊ณ ๋ คํด์ผํ๋ฏ๋ก ์๊ฐ ๋ณต์ก๋๋ O(N^3)์ผ๋ก ํฐ ํธ ์ ๋๋ค. ์ฆ, ๋ฌธ์ ์์ ์ฃผ์ด์ง ๋ ธ๋(N)์ ์ต๋๊ฐ์ ๊ณ ๋ คํด ๋ฏธ๋ฆฌ ๊ณ์ฐํด ์ฌ์ฉํ ๊ฐ์น๊ฐ ์๋ ์๊ณ ๋ฆฌ์ฆ์ธ์ง ๊ณ ๋ คํด๋ด์ผํฉ๋๋ค. โ๏ธ ํ๋ก์ด๋ ์์ฌ ์๊ณ ๋ฆฌ์ฆ ์ ๊ทธ๋ฆผ์ ๊ฒฝ์ฐ๋ ์ถ๋ฐ์ง์ ์ด 1๋ฒ ๋ ธ๋, ๋์ฐฉ์ง์ ์ด 4๋ฒ ๋ ธ๋์ธ ๊ฒฝ์ฐ ์ ๋๋ค. 1 -> 4๋ก ๊ฐ๋๊ฒ ๊ฒฝ์ ..