๐ฎ ์จ-์์ค/๐ ์๊ณ ๋ฆฌ์ฆ
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ๊ธฐ์์ ๋ ฌ(Radix Sort)
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ๊ธฐ์์ ๋ ฌ(Radix Sort)
2021.07.18๊ธฐ์ ์ ๋ ฌ, Radix Sort ๊ธฐ์ ์ ๋ ฌ์ ๊ณ์ ์ ๋ ฌ(Counting Sort) ์ ๋ง์ฐฌ๊ฐ์ง๋ก ๋น๊ต์ฐ์ฐ์ ์ํํ์ง ์์ ์กฐ๊ฑด์ด ๋ง๋ ์ํฉ์์ ๋น ๋ฅธ ์ ๋ ฌ ์๋๋ฅผ ๋ณด์ฅํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ์ ์ฒด์ ์ธ ์ปจ์
์ ๋ฐ์ดํฐ์ ๊ฐ ์๋ฆฟ์๋ฅผ ๋ฎ์ ์๋ฆฌ์์์๋ถํฐ ๊ฐ์ฅ ํฐ ์๋ฆฌ์๊น์ง ์ฌ๋ผ๊ฐ๋ฉด์ ์ ๋ ฌ์ ์ํํ๋ ๊ฒ์ด๋ค. ๊ทธ๋ฆฌ๊ณ ์ด๋ฐ ์ด์ ๋๋ฌธ์ ์๋ฆฟ์๊ฐ ์กด์ฌํ์ง ์๋ ๋ฐ์ดํฐ๋ฅผ ๊ธฐ์์ ๋ ฌ๋ก ์ ๋ ฌํ๋ ๊ฒ์ ๋ถ๊ฐ๋ฅํ๋ค. Algorithm Concept ๊ธฐ์ ์ ๋ ฌ์ ๋ค์๊ณผ ๊ฐ์ ๊ณผ์ ์ ๊ฑฐ์ณ์ ์ ๋ ฌ์ ์ํํ๋ค. ์๋ฅผ ๋ค์ด, ํ์ฌ ๊ฐ์ง๊ณ ์๋ ๋ฐ์ดํฐ ์ค ๊ฐ์ฅ ํฐ ์๋ฆฟ์๊ฐ 100์ ์๋ฆฌ๋ผ๊ณ ํด๋ณด์. ๊ฐ ๋ฐ์ดํฐ๋ค์ 1์ ์๋ฆฌ๋ฅผ ๋น๊ตํด์ ๊ฐ์ ๋ฐ์ดํฐ๋ผ๋ฆฌ ๋ชจ์๋ค. 1์ ์๋ฆฌ๊ฐ ์์ ๋ฐ์ดํฐ๋ค์ด ์์ ์์นํ๊ฒ ๋๊ณ ํฐ ์ซ์๋ค์ด ๋ค์ ์์นํ๊ฒ ๋๋ค.(์ค..
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ํฉ๋ณ์ ๋ ฌ(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..