๐ฎ ์จ-์์ค
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ํฉ๋ณ์ ๋ ฌ(Merge Sort)
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ํฉ๋ณ์ ๋ ฌ(Merge Sort)
2021.07.18ํฉ๋ณ์ ๋ ฌ, ๋จธ์ง์ํธ, ๋ณํฉ์ ๋ ฌ ํฉ๋ณ์ ๋ ฌ์ ํต์ ๋ ฌ๊ณผ ๋ง์ฐฌ๊ฐ์ง๋ก ๋ถํ ์ ๋ณต์ ์ด์ฉํด์ ์ ๋ ฌ์ ์ํํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ํต์ ๋ ฌ๊ณผ๋ ๋ค๋ฅด๊ฒ ํญ์ ๐ฉ(nlgn) ์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๋ณด์ฅํ๋ค๋ ์ฅ์ ์ด ์์ง๋ง, ์ ๋ ฌ์ ์ํด ์ถ๊ฐ์ ์ธ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํฌ๊ฒ ์ฌ์ฉํ๋ค๋ ๋จ์ ์ด ์๋ค. Algorithm Concept ํฉ๋ณ์ ๋ ฌ์ ๋ค์๊ณผ ๊ฐ์ ๊ณผ์ ์ ํตํด ๋ฐฐ์ด์ ์์๋ค์ ์ ๋ ฌํ๊ฒ ๋๋ค. (์ค๋ฆ์ฐจ์) ๋๋์ด์ง ๋ฐฐ์ด์ ๊ธธ์ด๊ฐ 1์ด ๋ ๋๊น์ง ๋ฐฐ์ด์ ๋ฐ์ผ๋ก ๊ณ์ ๋๋๋ค. ๋๋์ด์ง ๋ฐฐ์ด์ ํฉ์น๋ฉด์ ์ ๋ ฌ์ ์ํํ๋ฉด์ ํฉ์น๋ค. ํฉ์น ๋๋ ํฉ์น ๋ ๋ฐฐ์ด์ ๊ธธ์ด์ ์ดํฉ๋งํผ์ ๋ณ๋ ๋ฐฐ์ด์ ์ค๋นํด์ ๋ ๋ฐฐ์ด์์ ์์ ์์๋๋ก ๊ฐ์ ธ์์ ๋ฐฐ์ด์ ๋ฃ์ด์ค๋ค. Example ๋ง๋ก๋ง ํ๋ฉด ํท๊ฐ๋ฆฌ๋๊น ์๋ ๋ฐฐ์ด์ ๋จธ์ง์ํธ๋ก ์ ๋ ฌํ๋ ๊ณผ์ ์ ๋ฐ๋ผ๊ฐ๋ณด์. Phase 1 ๋จผ์ ..
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ๊ณ์์ ๋ ฌ(Counting Sort)
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ๊ณ์์ ๋ ฌ(Counting Sort)
2021.07.18Comparison Sort ๋ชจ๋ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ ๊ธฐ๋ณธ์ ์ผ๋ก ๋ฐฐ์ด์ ์์๋ค์ ๊ฒ์ฌํ๋ ๊ณผ์ ์ด ํฌํจ๋์ด ์๋ค. ๊ฒฐ๊ตญ ๋ฐฐ์ด์ ๋ฐ์ดํฐ๋ค์ ๋น๊ตํ๊ธฐ ์ํด์๋ Decision Tree ๋ฅผ ๋ง๋ค์ด ๊ฒฝ์ฐ์ ์๋ฅผ ๋ฐ์ ธ๋ณผ ์ ์๋๋ฐ, ์ด๋ก๋ถํฐ ์ฐ๋ฆฌ๋ decision tree ์ ๋์ด์ธ logn ๋งํผ ๋น๊ต์ฐ์ฐ์ด ์ผ์ด๋๋ค๋ ๊ฒ์ ์์๋ผ ์ ์๋ค. ๋น๊ต์ฐ์ฐ์ ์๊ฐ ๋ณต์ก๋๋ ี(n) ์ด๋ฏ๋ก ๋น๊ต์ฐ์ฐ์ ์ฌ์ฉํ๋ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ ์๋ฌด๋ฆฌ ๋นจ๋ผ๋ ี(nlogn)๋ณด๋ค ๋น ๋ฅผ ์๊ฐ ์๋ค. ์ฐ๋ฆฌ๊ฐ ์์ฃผ ์ธ๊ธํ๋ ๋น ๋ฅธ ์ ๋ ฌ์๊ณ ๋ฆฌ์ฆ์ธ ํต์ํธ, ๋จธ์ง์ํธ ์ญ์ ี(nlogn)์ ๋ณต์ก๋๋ก ๊ฐ์ง๋ค. Counting Sort ๊ทธ๋ ๋ค๋ฉด ๋ง์ฝ ๋น๊ต์ฐ์ฐ์ ์ฌ์ฉํ์ง ์๋๋ค๋ฉด ์ด๋จ๊น? ๋น๊ต์ฐ์ฐ์ ์ฌ์ฉํ์ง ์๋๋ค๋ฉด Decision Tree ์ ์ ์ฝ์ฌํญ ์์ด ๋ ๋น ..
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ํต์ ๋ ฌ(Quick Sort)
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ํต์ ๋ ฌ(Quick Sort)
2021.07.18ํต์ํธ ํต ์ ๋ ฌ์ ์ด๋ฆ ๊ทธ๋๋ก ๋งค์ฐ ๋น ๋ฅด๊ฒ ์ ๋ ฌ์ ์ํํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ๊ธฐ๋ณธ์ ์ผ๋ก ๋ถํ ์ ๋ณต์ ์ฑ๊ฒฉ์ ๊ฐ์ง๊ณ ์๊ณ ์ค์ ๋ก๋ ๋ง์ด ์ฌ์ฉ๋๋ ๋ํ์ ์ธ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ๋์์ ์๋ฃ๊ตฌ์กฐ ์๊ฐ์๋ค์ ๊ดด๋กญ๊ฒ ํ๋ ์น๊ตฌ ์ค ํ๋ช
์ด๊ธด ํ์ง๋ง.. Algorithm Concept ํต ์ ๋ ฌ์ ๋ค์๊ณผ ๊ฐ์ ๊ณผ์ ์ผ๋ก ์ ๋ ฌ์ ์งํํ๋ค. ์ ๋ ฌ์ ์ค๋ฆ์ฐจ์์ผ๋ก ์งํํ๋ค๊ณ ๊ฐ์ ํ์. ์ฃผ์ด์ง ๋ฐฐ์ด์์ ํ๋์ ์์๋ฅผ ์ ํํ๊ณ ์ด๋ฅผ pivot(ํผ๋ฒ) ์ผ๋ก ์ผ๋๋ค. ๋ฐฐ์ด ๋ด๋ถ์ ๋ชจ๋ ๊ฐ์ ๊ฒ์ฌํ๋ฉด์ ํผ๋ฒ ๊ฐ๋ณด๋ค ์์ ๊ฐ๋ค์ ์ผ์ชฝ์, ํฐ ๊ฐ๋ค์ ์ค๋ฅธ์ชฝ์ ๋ฐฐ์นํ๋ค. ์ด๋ ๊ฒ ํ๋ฉด ๋ฐฐ์ด์ด ๋ ๋ถ๋ถ์ผ๋ก ๋๋๋ค. ๋๋ ์ด ๋ ๊ฐ์ ๋ฐฐ์ด์์ ๊ฐ๊ฐ ์๋ก์ด ํผ๋ฒ์ ๋ง๋ค์ด์ ๋๊ฐ์ ๋ฐฐ์ด๋ก ๋ค์ ์ชผ๊ฐ์ด ์ค๋ค. ๋ ์ด์ ๋ฐฐ์ด์ ์ชผ๊ฐค ์ ์์ ๋๊น์ง ์งํํ๋ค. ..
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ํ๋ก์ด๋-์์
์๊ณ ๋ฆฌ์ฆ(Floyd-Warshall Algorithm)
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ํ๋ก์ด๋-์์ ์๊ณ ๋ฆฌ์ฆ(Floyd-Warshall Algorithm)
2021.07.18All Pairs Shortest Path ์ง๊ธ๊น์ง ๋ค๋ค๋ ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ด๋ ๋ฒจ๋งํฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ๋ชจ๋ ํ๋์ ์ ์ ์ผ๋ก๋ถํฐ ๋ค๋ฅธ ๋ชจ๋ ์ ์ ๊น์ง์ ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋ Single source Shortest Path(SSP) ๋ฌธ์ ๋ฅผ ํ๊ธฐ์ํ ์๊ณ ๋ฆฌ์ฆ์ด์๋ค. ์ค๋ ์๊ฐํ ํ๋ก์ด๋-์์
์๊ณ ๋ฆฌ์ฆ์ ๊ทธ๋ํ์ ์๋ ๋ชจ๋ ๋ชจ๋ ์ ์ ์ ๋ํด ๊ฐ ์ ์ ๋ค์ด ๋ค๋ฅธ ์ ์ ๋ค๊น์ง ๋๋ฌํ๊ธฐ ์ํด ํ์ํ ๋ชจ๋ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ์ด๋ค. Concept ์๊ณ ๋ฆฌ์ฆ์ ์๋ฆฌ๋ ๋จ์ํ๋ค. ์ด๋ค ์ ์ X๋ก๋ถํฐ Y๊น์ง์ ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๊ธฐ ์ํด์ ์ค๊ฐ์ ๊ฑฐ์ณ๊ฐ ์ ์๋ ๋ชจ๋ ์ ์ ๋ค์ ํ์ธํด๋ณด๊ณ ๊ทธ ์ค ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๋ง๋๋ ๊ฒฝ๋ก๋ฅผ ์ฐพ๋ ๊ฒ์ด๋ค. ๋ค์ ์์์ ๋ณด์. ์ฌ๊ธฐ์ dij(k) ์ 1๋ถํฐ k ๊น์ง์ ์ ์ ๋ค์ ๊ฑฐ์ณ๊ฐ๋ ๊ฒฝ๋ก ์ค ์ต๋จ ๊ฒฝ๋ก์ ..
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ์์์ ๋ ฌ(Topological Sort)
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ์์์ ๋ ฌ(Topological Sort)
2021.07.18Topological Sort (์์ ์ ๋ ฌ) Topological sort๋ Direct Acyclic Graph ์ ๊ฒฝ์ฐ์์ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ๋ฐฉ๋ฒ์ด๋ค. ๋ฐฉํฅ์ด ์กด์ฌํ๋ ๊ทธ๋ํ์์ ๊ฐ vertex์ ์ ํ ์์ ์ ๋ณด๋ฅผ ์ ์งํ๋ฉด์ ๋ชจ๋ vertex๋ฅผ ํ์ํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. Type of Edges ์๊ณ ๋ฆฌ์ฆ์ ์์๋ณด๊ธฐ ์ ์, Direct Acyclic Graph๋ฅผ ์๊ธฐ ์ํด ๋ฐฉํฅ์ด ์๋ ๊ทธ๋ํ์์ DFS๋ฅผ ์คํํ ๋ ๋ํ๋๋ edge์ ์ข
๋ฅ๋ฅผ ๋จผ์ ์ ๋ฆฌํด๋ณด์. Tree Edge: ์๋ก์ด ์ ์ ์ ๋ง๋ฌ์ ๋ ์๊ธฐ๋ edge. Edge๋ ํ ์ ์ ์์ ๋ค๋ฅธ ์ ์ ์ ์ด์ ๋ ๋ฐ์ํ๊ฒ ๋๋ค. Tree Edge๋ ์ด๋ค ์ ์ ์ด ์๋ก์ด ์ ์ ๊ณผ ์ฐ๊ฒฐ ๋ ๋ ์๊ธฐ๋ edge๋ฅผ ๋งํ๋ค. Back Edge: Back Edge๋ ํธ๋ฆฌ..
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] DAG์์ ์ต๋จ๊ฒฝ๋ก๋ฅผ ์ฐพ๋ ๋ฒ
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] DAG์์ ์ต๋จ๊ฒฝ๋ก๋ฅผ ์ฐพ๋ ๋ฒ
2021.07.18DAG๋ Directed Acyclic Graph ์ด๋ค. ํ์ด์ ์จ๋ณด๋ฉด, ๋ฐฉํฅ์ด ์กด์ฌํ๊ณ ์ฌ์ดํด์ด ์๋ ๊ทธ๋ํ ๋ผ๊ณ ํ ์ ์๋ค. ๋ฒจ๋ง-ํฌํธ ์๊ณ ๋ฆฌ์ฆ์ ๊ฐ์ฅ ํฐ ๋ฌธ์ ๋ ์์ ์ฌ์ดํด์ด ์๋์ง ํ์ธํ๊ธฐ ์ํด ๊ฑธ๋ฆฌ๋ ์๊ฐ์ด์๋ค. ๊ทธ๋ฌ๋ DAG์์๋ ์ฌ์ดํด์ด ์กด์ฌํ์ง ์๊ณ , ๋ฐฉํฅ์ด ์๊ธฐ ๋๋ฌธ์ ์ถ๊ฐ์ ์ธ ์ฐ์ฐ์์ด ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ์ฐพ๋ ๊ฒ์ด ๊ฐ๋ฅํ ๊ฒ์ด๋ค. Algorithm Strategy ๋ฐฉํฅ์ด ์๊ณ ์ฌ์ดํด์ด ์๋ ๊ทธ๋ํ๋ผ๋ ๊ฒ์ ๊ณง ๋ชจ๋ ์ ์ ์ด ํ์๋๋ ์์๋ฅผ ๊ฐ์ง๋ค๋ ๊ฒ์ด๋ค. ์ด ์ฑ์ง์ ์ด์ฉํด์ ํ ์ ์ ์ผ๋ก๋ถํฐ ๋ค๋ฅธ ์ ์ ์ผ๋ก ์ด๋ํ ๋์ ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ์ถ์ ํด๊ฐ๋ค๋ณด๋ฉด, ๊ฐ์ฅ ๋ง์ง๋ง ์ ์ ์ ๋์ฐฉํ๊ธฐ๊น์ง ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ ์ ์์ ๊ฒ์ด๋ค. ์ด๋ฅผ ๊ตฌํํ๊ธฐ ์ํด์ ๋ค์๊ณผ ๊ฐ์ ๊ณผ์ ์ ๊ฑฐ์น๋ค. Topological Sort ๋ฅผ ํต..
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ(Dijkstra Algorithm)
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ(Dijkstra Algorithm)
2021.07.18๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ SSP ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํ ์๊ณ ๋ฆฌ์ฆ ์ค ๋ฒจ๋ง-ํฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ๋นํด์ ์๋๊ฐ ๋ ๋น ๋ฅธ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ํ์ง๋ง ์์ ๊ฐ์ ์ด ์์ ๋๋ ํด๋ต์ ์ฐพ์ง ๋ชปํ๋ค. ๊ทธ๋์ ๋ง์ฝ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ์์ ์์ ๊ฐ์ ์ด ์
๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ค๋ฉด ๋ฒจ๋ง-ํฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํด์ผํ๊ณ , ์์ ๊ฐ์ ์ผ๋ก๋ง ์ด๋ฃจ์ด์ง ๊ทธ๋ํ๊ฐ ์ฃผ์ด์ง๋ค๋ฉด, ๋ฒจ๋ง-ํฌ๋ ์๊ณ ๋ฆฌ์ฆ๊ณผ ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ๋ชจ๋ ์ฌ์ฉ๊ฐ๋ฅํ์ง๋ง, ์๋๊ฐ ๋ ๋น ๋ฅธ ๋ค์ต์คํธ๋ผ๋ฅผ ์ฌ์ฉํ๋๋ก ํ์. Algorithm Concept ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ BFS์ ๊ฐ์ ๊ฑฐ๋ฆฌ๋ฅผ ์ถ๊ฐํ ๊ฒ๊ณผ ๋น์ทํ๋ค. ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ๋ ๊ฐ์ ์ ์ ์งํฉ์ ์ฌ์ฉํ๋ค. S : ํด๋น ์ง์ ๊น์ง์ ์ต๋จ ๊ฒฝ๋ก๊ฐ ์ด๋ฏธ ๊ตฌํด์ง ์ ์ ๋ค Q : S์ ์ํ์ง ์๋ ๋๋จธ์ง ๋ชจ๋ ์ ์ ๋ค ๊ทธ๋ฆฌ๊ณ ์๊ณ ๋ฆฌ์ฆ์ ์๋ ์์๋ก ..
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ๋ฒจ๋ง-ํฌ๋ ์๊ณ ๋ฆฌ์ฆ(Bellman-Ford Algorithm)
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ๋ฒจ๋ง-ํฌ๋ ์๊ณ ๋ฆฌ์ฆ(Bellman-Ford Algorithm)
2021.07.18์ด์ ๋ณธ๊ฒฉ์ ์ผ๋ก SSP๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํ ์๊ณ ๋ฆฌ์ฆ์ ์ดํด๋ณด์. ์ฒ์์ผ๋ก ์๊ฐํ ์๊ณ ๋ฆฌ์ฆ์ Bellman-Ford ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ์ฐ๋ฆฌ ๋ง๋ก๋ ๋ฒจ๋ง-ํฌ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ผ๊ณ ํ๋ค. Bellman-Ford Algorithm ๋ฒจ๋ง-ํฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ํน์ง์ SSP๋ฅผ ํด๊ฒฐํ๋ ์๊ณ ๋ฆฌ์ฆ ์ ๊ทผ ์ค ์ ์ผํ๊ฒ negative weight ์ด ์กด์ฌํ๋ ๊ทธ๋ํ์์๋ ์ต๋จ๊ฒฝ๋ก๋ฅผ ์ฐพ์ ์ ์๋ค๋ ๊ฒ์ด๋ค. ๊ทธ๋ ์ง๋ง negative weight cycle์ด ์กด์ฌํ ๋๋ ํด๋ต์ ์ฐพ์ ์ ์๋ค. ๋ฐ๋ผ์ ๋ฒจ๋งํฌ๋ ์๊ณ ๋ฆฌ์ฆ์ Negative Cycle์ด ์กด์ฌํ๋์ง ์ฌ๋ถ๋ฅผ ํ์ธํด์ ์กด์ฌํ ๋๋ FALSE, Negative Cylcle์ด ์์ ๋๋ TRUE๋ฅผ ๋ฐํํ๋ค. Algorithm Steps ๋ฒจ๋ง-ํฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ๋จ๊ณ๋ณ๋ก ๋๋์ด์ ์งํํด๋ณด์. S..
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ์ต๋จ๊ฒฝ๋ก(Shortest Path)
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ์ต๋จ๊ฒฝ๋ก(Shortest Path)
2021.07.18Shortest Path(์ต๋จ ๊ฒฝ๋ก)๋ ๊ฐ์ค์น๊ฐ ์๋ ๊ทธ๋ํ์์ ์ด๋ค ์ ์ ์์ ๋ค๋ฅธ ์ ์ ์ผ๋ก ์ด๋ํ๊ธฐ๊น์ง ๊ฐ์ฅ ์งง์ ๊ฐ์ค์น์ ํฉ์ผ๋ก ๋ชฉ์ ์ง์ ๋๋ฌํ๋ ๋ฐฉ๋ฒ์ ์ฐพ๊ธฐ ์ํ ์ ๋ต์ด๋ค. ์ต๋จ ๊ฒฝ๋ก๋ฌธ์ ๋ ๋ช๊ฐ์ง ์ ํ์ผ๋ก ๋๋์ด์ง๋ค. Single Source: ํ๋์ ๋
ธ๋๋ก๋ถํฐ ์ถ๋ฐํด์ ๋ค๋ฅธ ๋ชจ๋ ๋
ธ๋์ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ์ฐพ๋ ๋ฌธ์ Single Destination: ๋ชจ๋ ๋
ธ๋๋ก๋ถํฐ ํ๋์ ๋ชฉ์ ์ง ๊น์ง์ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ์ฐพ๋ ๋ฌธ์ Single Pair: ์ฃผ์ด์ง ํ๋์ ๋
ธ๋๋ก๋ถํฐ ํ๋์ ๋ชฉ์ ์ง๊น์ง์ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ์ฐพ๋ ๋ฌธ์ All pair: ๋ชจ๋ ๋
ธ๋ ์์ ๋ํ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ์ฐพ๋ ๋ฌธ์ ์ด๋ฒ ์์
์์ ์ฃผ๋ก ๋ค๋ฃฐ ๋ด์ฉ์ SSP ๋ผ๊ณ ๋ ๋ถ๋ฅด๋ Single-source Shortest Path ์ด๋ค. Lemma ์ผ๋จ Shortest ..
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ(Prim's Algorithm)
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ(Prim's Algorithm)
2021.07.18ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ์ ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ์ฒ๋ผ ๊ฐ์ ์ ๊ฐ์ค์น๊ฐ ๋ฎ์ ๊ฐ์ ๋ถํฐ ์ ํํด์ MST๋ฅผ ๋ง๋ค์ด ๋๊ฐ์ง๋ง, ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ๊ณผ๋ ๋ค๋ฅด๊ฒ ์ฌ๋ฌ ํธ๋ฆฌ๋ค์ ๋ง๋ค๊ณ ์ ์ ํฉ์น๋ ๊ฒ์ด ์๋๋ผ ํ๋์ ํธ๋ฆฌ๋ฅผ ์ ์งํด๊ฐ๋ฉด์ ์๋ก์ด ๊ฐ์ ์ ์ถ๊ฐํด๋๊ฐ๋ ๋ฐฉ์์ผ๋ก ์งํํ๋ค. Algorithm Concept ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ์ ๋ค์๊ณผ ๊ฐ์ ๊ณผ์ ์ผ๋ก ์งํ๋๋ค. ์์์ ๋ฃจํธ๋
ธ๋ r์ ํฌํจํ๋ ํธ๋ฆฌ A๋ฅผ ๋ง๋ ๋ค. ํธ๋ฆฌ A์ ์ํ๋ ์ ์ ๋ค๊ณผ ์ํ์ง ์๋ ๋ค๋ฅธ ๋ชจ๋ ์ ์ ๋ค์ cross ํ๋ ๊ฐ์ ๋ค ์ค ๊ฐ์ค์น๊ฐ ๊ฐ์ฅ ๋ฎ์ light edge ๋ฅผ ์ฐพ๋๋ค. ํด๋น light edge๋ฅผ ํธ๋ฆฌ A๋ก ํธ์
์ํจ๋ค. ๋น ๋ฅธ light edge ํ์์ ์ํด min heap ์ ์ด์ฉํ priority queue ๋ฅผ ์ฌ์ฉํ๋ค. Pseudo Code MST-Prim..
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ(Kruskal Algorithm)
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ(Kruskal Algorithm)
2021.07.18Kruskal MST Algorithm ์ต์ ์ ์ฅ ํธ๋ฆฌ๋ฅผ ๊ตฌํ๋ ์๊ณ ๋ฆฌ์ฆ ์ค ํ๋์ธ ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ์ ์์๋ณด์. Algorithm Concept ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ์ Greedy Algorithm์ ์ ์ฉํด์ ๊ฐ์ค์น๊ฐ ๊ฐ์ฅ ์ ์ ๊ฐ์ ๋ค์ ๊ณ์ ์ ํํ๋ค. ์๊ณ ๋ฆฌ์ฆ์ ๋ค์๊ณผ ๊ฐ์ ๊ณผ์ ์ผ๋ก ์ด๋ฃจ์ด์ง๋ค. ๊ทธ๋ํ์ ๋ชจ๋ ๊ฐ์ ์ ๊ฐ์ค์น๊ฐ ๋ฎ์ ์์๋๋ก ์ ๋ ฌ ์์๋๋ก ๊บผ๋ด๋ฉด์ MST๋ฅผ ๋ง๋ ๋ค. ์ด๋, MST์ ์ถ๊ฐํ๋ฉด ์ฌ์ดํด์ด ๋ง๋ค์ด์ง๋ ๊ฐ์ ์ ์ ์ธํ๋ค. ๋ฌด์ฒ ๊ฐ๋จํด๋ณด์ด์ง๋ง, 3๋ฒ์งธ ์กฐ๊ฑด์ธ ์ฌ์ดํด์ ๊ฒ์ฌํ๋ ๊ฒ์ด ๊ฐ์ฅ ํต์ฌ์ ์ด๊ณ ์ฝ์ง ์์ ๋ด์ฉ์ด๋ค. ์ด๋ฅผ ์ํด์๋ Union Find ๋ฅผ ํตํด ๊ฐ ๊ฐ์ ์ ์ ๋ ์ ์ ๋ค์ด ๊ฐ์ ์งํฉ ๋ด์ ์๋์ง ํ์ธํด์ผํ๋ค. Example ์ด ๊ทธ๋ํ์์ ์ต์ ์ ์ฅ ํธ๋ฆฌ๋ฅผ ์ฐพ์๋ณด์. Pha..
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ์ต์ ์ ์ฅ ํธ๋ฆฌ(MST)
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ์ต์ ์ ์ฅ ํธ๋ฆฌ(MST)
2021.07.18Spanning Tree Minimum Spanning Tree ๋ฅผ ์์ํ๊ธฐ ์ ์, Spanning Tree๊ฐ ๋ฌด์์ธ์ง ์ ๋ฆฌํด๋ณด์. Spanning Tree Condition ์ ์ฅํธ๋ฆฌ ๋ผ๊ณ ๋ ํ๋ ์คํจ๋ ํธ๋ฆฌ๋ ๋ค์๊ณผ ๊ฐ์ ์กฐ๊ฑด์ด ์ฑ๋ฆฝํด์ผํ๋ค. N๊ฐ์ ์ ์ ์ ๊ฐ์ง๋ ๊ทธ๋ํ์์ ์ต์ N-1 ๊ฐ์ ๊ฐ์ ์ผ๋ก ์ฐ๊ฒฐ๋์ด ์๋ค. ๊ทธ๋ํ์ ๋ชจ๋ ์ ์ ์ ํฌํจํ๋ค. ๊ทธ๋ํ์ ๋ชจ๋ ์ ์ ์ ๊ฐ์ง๊ณ ์์ด์ผ ์ ์ฅํธ๋ฆฌ์ ์กฐ๊ฑด์ด ๋ง์กฑ๋๊ธฐ ๋๋ฌธ์, ๊ฐ์ ์ ๊ฐฏ์๋ ํญ์ N-1 ๊ฐ๊ฐ ๋ ์ ๋ฐ์ ์๊ณ , N-1๊ฐ์ ๊ฐ์ ๊ณผ N๊ฐ์ ์ ์ ์ผ๋ก ์ด๋ฃจ์ด์ง ๊ทธ๋ํ๋ ์ ์ฒด ๊ทธ๋ํ์ ๋ํ ์ฌ์ดํด์ด ์กด์ฌํ ์ ์๊ธฐ ๋๋ฌธ์ ํญ์ ํธ๋ฆฌ์ ํํ๊ฐ ๋๋ค. ๋ฐ๋ผ์ ์ฐ๋ฆฌ๊ฐ DFS๋ BFS ๋ก ํ์ํ๋ฉด ๊ฐ ์ ์ ๋ค์ ์ฐ๊ฒฐํ๊ฒ ๋๋ฉด ์์ฐ์ค๋ฝ๊ฒ Spanning Tree ..