๋ฐฐ์ด์ ๋ ๊ตฌ์ญ์ผ๋ก ๋ถ๋ฆฌํ๋ partition๊ณผ ๋ ๊ตฌ์ญ์ ์ ๋ ฌํ๋ฉฐ ํ๋๋ก ํฉ์น๋ merge๋ก ์ ๋ ฌ์ ์ํํ๋ stableํ ์ ๋ ฌ ๊ธฐ๋ฒ
pivot์ ๊ธฐ์ค์ผ๋ก ๋ ๊ตฌ์ญ์ ๋ถ๋ฆฌํ๋ฉด์ (์ผ์ชฝ์ pivot๋ณด๋ค ์์ ๊ฐ, ์ค๋ฅธ์ชฝ์ pivot๋ณด๋ค ํฐ ๊ฐ) ์ ๋ ฌํ๋ unstableํ ์ ๋ ฌ ๊ธฐ๋ฒ
๋ ํ์์ ๋ชจ๋ ์ ์ ์ ํ๋ฒ๋ง ๋ฐฉ๋ฌธํ๋ค๋ ๊ฐ์ ๋ชฉํ๋ฅผ ๊ฐ์ง๊ณ ์์ง๋ง, ๊ทธ ๊ณผ์ ์์ ํ์ํ๋ ๋ฐฉ์์ ์ฐจ์ด๊ฐ ์๋ค.
์์ ๊ฐ์ค์น๊ฐ ์กด์ฌํ์ง ์๋ ๊ทธ๋ํ์์ ์ถ๋ฐ์ ์์๋ถํฐ ๋ค๋ฅธ ๋์ฐฉ์ ๊ฐ์ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ์์๋ผ ๋ ์ฌ์ฉ๋๋ ์๊ณ ๋ฆฌ์ฆ
๋ชจ๋ ์ ์ ์์๋ถํฐ ์๋ก ๋ค๋ฅธ ๋ชจ๋ ์ ์ ๋ค๊ฐ์ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋ ์๊ณ ๋ฆฌ์ฆ
ํ ์ ์ ์์ ๋ค๋ฅธ ๋ชจ๋ ์ ์ ๋ค๋ก ๊ฐ๋ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋ ์๊ณ ๋ฆฌ์ฆ
DFS๋ฅผ ์ด์ฉํ์ฌ ํ ๋ฆฌ์ ๊ฐ ์ ์ ์ ์กฐ์-์์ ๊ด๊ณ๋ฅผ ์ฝ๊ฒ ์ฐพ๋๋ก ํด์ฃผ๋ ๊ธฐ๋ฒ
Disjoint-set(์๋ก์ ์งํฉ) ์๋ฃ๊ตฌ์กฐ๋ฅผ ๋ง๋ค๊ธฐ ์ํ ์๊ณ ๋ฆฌ์ฆ
์ด๋ค ๊ทธ๋ํ๋ก๋ถํฐ ์ต์ ์ ์ฅ ํธ๋ฆฌ(Minimum Spanning Tree)๋ฅผ ๋์ถํด๋ผ ๋ ์ฌ์ฉํ๋ ์๊ณ ๋ฆฌ์ฆ
Kruskal๊ณผ ๊ฐ์ด ์ด๋ค ๊ทธ๋ํ๋ก๋ถํฐ ์ต์ ์ ์ฅ ํธ๋ฆฌ(Minimum Spanning Tree)๋ฅผ ๋์ถํด๋ผ ๋ ์ฌ์ฉํ๋ ์๊ณ ๋ฆฌ์ฆ
๋ ์ ์๊ฐ์ ์ต๋๊ณต์ฝ์๋ฅผ ๊ตฌํ๋ ์๊ณ ๋ฆฌ์ฆ
์ต์ ํ๋ ์์ ๊ตฌํ๊ธฐ ์๊ณ ๋ฆฌ์ฆ
์์ด๊ณผ ์กฐํฉ ์๊ณ ๋ฆฌ์ฆ
ํฌํ ์ด์ง ํธ๋ฆฌ ๋ชจ์์ ์๋ฃ๊ตฌ์กฐ๋ก ๊ตฌ๊ฐ์ ํน์ง์ด ๋๋ ๊ฐ(ํฉ, ๊ณฑ, ์ต๋, ์ต์, gcd ๋ฑ)์ ์ฒ๋ฆฌํ ๋ ์ด์ฉ
์ ๋ ฌ๋ ๋ฆฌ์คํธ์์ ๋ ํฌ์ธํฐ๋ฅผ ์ด์ฉํด ์์ฐจ์ ์ผ๋ก ์ ๊ทผํ๋ฉด์ ์ํ๋ ๋ฌธ์ ์ ํด๋ฅผ ๊ฒ์ํ ๋ ์ฌ์ฉํ๋ ๊ธฐ๋ฒ