Array vs Linked List
Array
-
๋ ผ๋ฆฌ์ ์ ์ฅ ์์์ ๋ฌผ๋ฆฌ์ ์ ์ฅ์์๊ฐ ์ผ์นํจ.
-
์ฅ์
-
Random Access : ์ธ๋ฑ์ค๋ก ์ํ๋ ์์์ ๋ฐ๋ก ์ ๊ทผ์ด ๊ฐ๋ฅํ์ฌ, O(1)์ ํด๋น์์๋ก ์ ๊ทผ๊ฐ๋ฅ
-
์ธ์ด์๋ฐ๋ผ ๋ค๋ฅด์ง๋ง, ํ์ํ ๋งํผ๋ง ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์ฐจ์งํจ
-
-
๋จ์
- ์ค๊ฐ์ ํ ์์๋ฅผ ์ญ์ ํ๊ฑฐ๋, ์๋ก์ด ์์๋ฅผ ๋ฃ์๋, ๋ค๋ฅธ ์์๋ฅผ shift ํด์ค์ผํ์ฌ O(n)์ ์๊ฐ์ด ๊ฑธ๋ฆผ.
Linked List
- ๊ฐ๊ฐ์ ์์๊ฐ ์๊ธฐ ๋ค์ (๊ทธ๋ฆฌ๊ณ ์ด์ ) ์์๊ฐ ๋ฌด์์ธ์ง๋ง ์๊ณ ์์
- ์ฅ์
- ์ญ์ /์ฝ์ ์ ์ํฅ์ ๋ฐ๋ ๋ค์/์ด์ ์์์ ๊ฐ๋ง ๋ณ๊ฒฝํด์ฃผ๋ฉด ๋๊ธฐ์ O(1)์ ์๊ฐ์ด ๊ฑธ๋ฆผ
- ๋จ์
- ๋ ผ๋ฆฌ์ ์ ์ฅ์์์ ๋ฌผ๋ฆฌ์ ์ ์ฅ์์๊ฐ ์ผ์นํ์ง ์์์, ์์๋ฅผ ์ฐพ์๋๋ ์ฒ์ ์์๋ถํฐ ์ฐจ๋ก๋๋ก ์ฐพ์์ผํ๊ธฐ์ O(n)์ ์๊ฐ์ด ๊ฑธ๋ฆฐ๋ค.
- ์ด๋ ์ญ์ /์ฝ์ ์์๋, ์์๋ฅผ ์ฐพ๋ ๊ณผ์ ์ด ํ์ํ๊ธฐ์ ๊ฒฐ๊ตญ ์ญ์ /์ฝ์ ์์๋ O(n)์ด ๊ฑธ๋ฆฌ๊ฒ ๋๋ค.
๊ทธ๋ผ ์ Linked List๋ฅผ ์ฐ๋๊ฐ? โ ๋ค๋ฅธ ๋ก์ง๊ณผ ๊ฒฐํฉํ๋ค๋ฉด ์ญ์ /์ฝ์ /์ฐพ๊ธฐ์ ์๊ฐ๋ณต์ก๋๋ฅผ ์ค์ผ ์ ์๊ณ , Tree์ ๊ทผ๊ฐ์ด ๋๋ ์๋ฃ๊ตฌ์กฐ์ด๊ธฐ์
Tree
๋น์ ํ ์๋ฃ๊ตฌ์กฐ๋ก, ๊ณ์ธต์ ๊ด๊ณ๋ฅผ ํํํ๋ ์๋ฃ๊ตฌ์กฐ์ด๋ค.
ํธ๋ฆฌ๋ ํํ์ ์ง์คํ๋ฉฐ, ๋ฌด์์ธ๊ฐ๋ฅผ ์ ์ฅํ๊ณ ๊บผ๋ธ๋ค๊ธฐ๋ณด๋ค๋ ์ด๋ค ๋ฐ์ดํฐ์ ๊ตฌ์กฐ๋ฅผ ํํํ๋ ๊ฒ์ ์ง์คํ๋ค.
ํธ๋ฆฌ ์ฉ์ด
- Node : ํธ๋ฆฌ๋ฅผ ๊ตฌ์ฑํ๋ ์์๋ค
- Edge : ํธ๋ฆฌ๋ฅผ ๊ตฌ์ฑํ๊ธฐ ์ํด ๋ ธ๋์ ๋ ธ๋๋ฅผ ์ฐ๊ฒฐํ๋ ์
- Rood Node : ์ต์์ ๋ ธ๋
- Terminal Node(leaf node) : ํ์์ ๋ค๋ฅธ ๋ ธ๋๊ฐ ์ฐ๊ฒฐ๋์ง ์์ ๋ ธ๋
- Internal Node (๋ด๋ถ๋ ธ๋) : ๋จ๋ง ๋ ธ๋๋ฅผ ์ ์ธํ ๋ชจ๋ ๋ ธ๋(๋ฃจํธ ํฌํจ)
- Level : 0(๋ฃจํธ๋ ธ๋)๋ถํฐ ์์ํ์ฌ, ํธ๋ฆฌ์ ์ธต๋ณ๋ก ๋ ๋ฒจ์ ํ๋์ฉ ๋ถ์ฌํ ๊ฒ
- height : ํด๋น ํธ๋ฆฌ์ ์ต๊ณ ๋ ๋ฒจ
Binary Tree
ํ ๋ถ๋ชจ๊ฐ ๋๊ฐ์ ์์๋ง ๊ฐ์ง ์ ์๋ ํธ๋ฆฌ๋ฅผ ๋งํ๋ค. ๊ณต์งํฉ๋ ์ด์งํธ๋ฆฌ์ ํฌํจ๋๋ค.
- ํฌํ์ด์งํธ๋ฆฌ : ๋ชจ๋ ๋ ๋ฒจ์ด ๊ฝ ์ฐฌ ์ด์งํธ๋ฆฌ
- ์์ ์ด์งํธ๋ฆฌ : ์์์ ์๋๋ก, ์ผ์ชฝ์์ ์ค๋ฅธ์ชฝ์ผ๋ก ์์๋๋ก ์ฑ์์ง ์ด์งํธ๋ฆฌ
- ์ ์ด์งํธ๋ฆฌ(Full Binary Tree) : ๋ชจ๋ ๋ ธ๋๊ฐ 0๊ฐ ํน์ 2๊ฐ์ ์์๋ง์ ๊ฐ์ง ์ด์งํธ๋ฆฌ
๋ฐฐ์ด๋ก ๊ตฌ์ฑ๋ Binary Tree๋ root๊ฐ 0์ด ์๋ 1์์ ์์ํ ๋, ๋ถ๋ชจ๋ ธ๋์ ์ธ๋ฑ์ค๊ฐ i๋ผ๊ณ ํ๋ค๋ฉด, ์ผ์ชฝ ์์์ 2i, ์ค๋ฅธ์ชฝ ์์์ 2i + 1์ด๋ค.
Binary Search Tree
์ด์งํ์ํธ๋ฆฌ๋ ์ด์งํธ๋ฆฌ์ ์ผ์ข ์ผ๋ก, ๋ฐ์ดํฐ์ ํ์์ ์ฉ์ดํ๊ฒ ํ๊ธฐ ์ํ ๋ฐ์ดํฐ ์ ์ฅ๋ฐฉ๋ฒ์ผ๋ก ๊ณ ์๋์๋ค.
์ด์งํ์ํธ๋ฆฌ์ ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ๋ ๊ท์น
- ์ด์งํ์ํธ๋ฆฌ์ ๋ ธ๋์ ์ ์ฅ๋ ํค๋ ์ ์ผํ๋ค
- ๋ถ๋ชจ์ ํค๊ฐ ์ผ์ชฝ์์ ๋ ธ๋์ ํค๋ณด๋ค ํฌ๋ค
- ๋ถ๋ชจ์ ํค๊ฐ ์ค๋ฅธ์ชฝ์์ ๋ ธ๋์ ํค๋ณด๋ค ์๋ค.
- ์ผ์ชฝ๊ณผ ์ค๋ฅธ์ชฝ ์๋ธํธ๋ฆฌ๋ ์ด์งํ์ํธ๋ฆฌ๋ค.
์ด์งํ์ํธ๋ฆฌ์์ ํ์์ฐ์ฐ์, ๋์ด๋งํผ ํ์ํ๊ธฐ์ O(h)์ด๋ฉฐ, ์์ ์ด์งํธ๋ฆฌ์ผ ๊ฒฝ์ฐ O(log n)์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ค. ํ์ง๋ง worst case๋ก ๋ฐ์ดํฐ๊ฐ ํธํฅ๋์ด ํธ๋ฆฌ์ ๋ค์ด์์ ๊ฒฝ์ฐ ํ์ชฝ์ผ๋ก ์น์ฐ์น๊ฒ ๋์ด O(n)์ ๋ณต์ก๋๋ฅผ ๊ฐ์ง๊ฒ ๋๋ค.
์ด๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด Rebalancing ๊ธฐ๋ฒ์ ์ฌ์ฉํ์ฌ, ํธ๋ฆฌ์ ๊ท ํ์ ๋ค์ ์ก๋ ์์
์ ํ๊ธฐ๋ ํ๋ค. ์ด ๊ธฐ๋ฒ์ ๊ตฌํํ ํธ๋ฆฌ๋ก๋ Red-Black Tree๊ฐ ์๋ค.
Binary Heap
์์ ์ด์งํธ๋ฆฌ์ ๊ธฐ๋ฐํ ํธ๋ฆฌ์ ์ผ์ข
์ด๋ค. ์ต๋ํ, ์ต์ํ ์ด ์๋ค.
- ์ต๋ํ : ๊ฐ ๋ ธ๋์ ๊ฐ์ด ์์์ ๊ฐ๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ์ ์์ ์ด์งํธ๋ฆฌ. ์ต๋๊ฐ์ ์ฐพ๋๋ฐ ์ฌ์ฉ
- ์ต์ํ : ๊ฐ ๋ ธ๋์ ๊ฐ์ด ์์์ ๊ฐ๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ ์ด์งํธ๋ฆฌ. ์ต์๊ฐ์ ์ฐพ๋๋ฐ ์ฌ์ฉ
์ฝ์ /์ญ์ ์ฐ์ฐ์ ์ต๋ ์ธต์๊น์ง๋ง ํ๋, O(log n)์ด๋ค.
๊ตฌํ
- ๋ฃจํธ๋ ธ๋๋ 1๋ถํฐ ์์.
- ์ฝ์
์ฐ์ฐ
- ํธ๋ฆฌ์ ๊ฐ์ฅ ๋ง์ง๋ง์ ์ฝ์
- ๋ถ๋ชจ์ ๊ฐ์ ๋น๊ตํด๊ฐ๋ฉฐ ์ฌ๋ผ๊ฐ
- ์ต์ํ์ผ ๊ฒฝ์ฐ, ๋ถ๋ชจ๋ณด๋ค ํด๊ฒฝ์ฐ ๋ฉ์ถค
- ์ญ์ ์ฐ์ฐ
- ๋ฃจํธ ๋ ธ๋๊ฐ ์ฌ์ฉ์์ ์์ฒญ์ผ๋ก ์ฌ๋ผ์ง
- ๊ฐ์ฅ ๋์ ๋ ธ๋๋ฅผ ๋ฃจํธ๋ ธ๋์ ์ฝ์
- ๋ ์์๋ณด๋ค ๊ฐ์ด ์์ ๋๊น์ง ์๋๋ก ๋ด๋ ค๊ฐ(๋ ์ค ํ๋๋ง ๋ณธ์ธ๋ณด๋ค ์์ ๊ฒฝ์ฐ ๊ทธ์ชฝ๊ณผ ๊ตํ. ๋ ๋ค ์์ ๊ฒฝ์ฐ ์๋ฌด๋ฐ๋ก)
Red Black Tree
์ด์ง ํ์ํธ๋ฆฌ์์, Rebalancing ๊ธฐ๋ฒ์ ์ ์ฉํ์ฌ ํ์/์ญ์ /์ฝ์ ์ O(log n)์ ์๊ฐ์ด ๊ฑธ๋ฆฌ๋๋ก ํ ํธ๋ฆฌ์ด๋ค.
์ฆ, ์ต๋ ๋์ด๋ฅผ log n๋ก ๋ง๋๋ ๊ฒ์ผ๋ก ์์ ์ด์งํธ๋ฆฌ์ ๊ธฐ๋ฐ์ ๋๋ค.
Red Black Tree ์ ์
RBT๋ ์๋ ์ฑ์ง์ ๋ง์กฑํ๋ ์ด์งํ์ํธ๋ฆฌ์ด๋ค.
- ๊ฐ ๋ ธ๋๋ Red or Black์ด๋ผ๋ ์๊น์ ๊ฐ๋๋ค.
- Root Node์ ์์์ Black์ด๋ค.
- ๊ฐ leaf node(NIL)๋ black์ด๋ค.
- ์ด๋ค ๋ ธ๋์ ์๊น์ด red๋ฉด, ๋ ์์์ ๋ชจ๋ black์ด๋ค.(Red๊ฐ ๋๋ฒ ์ฐ์ ๋์ฌ ์ ์์)
- ๊ฐ์ ์ธต์ ์๋ ๊ฐ ๋ ธ๋์ ๋ํ์ฌ ๋ ธ๋๋ก๋ถํฐ descendant leaves ๊น์ง์ ๋จ์ ๊ฒฝ๋ก๋ ๋ชจ๋ ๊ฐ์ ์์ black nodes๋ค์ ํฌํจํ๊ณ ์๋ค. ์ด๋ฅผ ํด๋น ๋ ธ๋์ black-height๋ผ๊ณ ํ๋ค.
Red Black tree์ ํน์ง
- BST์ ํน์ง์ ๋ชจ๋ ๊ฐ๋๋ค.
- Root node๋ถํฐ leaf node๊น์ง์ ๋ชจ๋ ๊ฒฝ๋ก ์ค ์ต์ ๊ฒฝ๋ก์ ์ต๋ ๊ฒฝ๋ก์ ํฌ๊ธฐ ๋น์จ์ 2๋ณด๋ค ํฌ์ง ์๋ค. ์ด๋ฌํ ์ํ๋ฅผ balanced๋ผ๊ณ ํ๋ค.
- ๋ ธ๋์ child๊ฐ ์์ ๊ฒฝ์ฐ child๋ฅผ ๊ฐ๋ฆฌํค๋ ํฌ์ธํฐ๋ NIL ๊ฐ์ ์ ์ฅํ๋ค. ์ด NIL๋ค์ leaf node๋ก ๊ฐ์ฃผํ๋ค.

์ฝ์
- BST(์ด์งํ์ํธ๋ฆฌ)์ ํน์ฑ์ ์ ์งํ๋ฉด์ ์ฝ์ ํ๋ค.
- ์ฝ์ ๋ ๋ ธ๋์ Red๋ฅผ ๋ถ์ฌํ๋ค.
- RBT์ ํน์ฑ์ ์๋ฐฐํ์ ์ ๋
ธ๋์ ์๊น์ ์กฐ์ ํ๊ณ , Black-height๊ฐ ์๋ฐฐ๋์๋ค๋ฉด rotation์ ํตํด height๋ฅผ ์กฐ์ ํ๋ค.
- ๋ค๋ฅธ ์ค๋ช
- Recoloring : ์ฝ์
๋ ๋
ธ๋์ ๋ถ๋ชจ์ ํ์ ์๊น์ด Red์ผ ๊ฒฝ์ฐ
- ๋ถ๋ชจ์ ๋ถ๋ชจ์ ํ์ ๋ ธ๋๋ Black์ผ๋ก, ๋ถ๋ชจ์ ๋ถ๋ชจ๋ Red๋ก(๋จ, ๋ฃจํธ๋ ธ๋์ผ๊ฒฝ์ฐ Black์ผ๋ก ๋๋
- ๋ค์ double red๊ฐ ๋ฐ์ํ์ ๊ฒฝ์ฐ ๋ค์ ์์
- Restructuring : ์ฝ์
๋ ๋
ธ๋์ ๋ถ๋ชจ์ ํ์ ์๊น์ด Black ๋๋ NULL์ธ ๊ฒฝ์ฐ
- ์ฝ์ ๋ ๋ ธ๋, ๋ถ๋ชจ, ๋ถ๋ชจ์ ๋ถ๋ชจ๋ฅผ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ
- ์ค์ ๊ฐ์ ๋ถ๋ชจ๋ ธ๋๋ก ๋ง๋ค๊ณ , ๋๋จธ์ง ๋ ธ๋๋ฅผ ์์์ผ๋ก ๋ณํํจ.
- ๋ถ๋ชจ๋ ธ๋๊ฐ ๋ ๋ ธ๋๋ฅผ Black, ๋๋จธ์ง ๋ ธ๋๋ฅผ Red๋ก coloring ํจ
- Recoloring : ์ฝ์
๋ ๋
ธ๋์ ๋ถ๋ชจ์ ํ์ ์๊น์ด Red์ผ ๊ฒฝ์ฐ
- ๋ค๋ฅธ ์ค๋ช
- ์ด๋ฌํ ๊ณผ์ ์ ํตํด RBT์ ๋์ผํ height์ ์กด์ฌํ๋ internal node๋ค์ black-height๊ฐ ๊ฐ์์ง๊ฒ ๋๊ณ , ์ต์ ๊ฒฝ๋ก์ ์ต๋๊ฒฝ๋ก์ ํฌ๊ธฐ ๋น์จ์ด 2 ๋ฏธ๋ง์ผ๋ก ์ ์ง๋๋ค.
์ญ์
- BST์ ํน์ฑ์ ์ ์งํ๋ฉด์ ์ฝ์ ํ๋ค.
- ๋ง์ฝ ์ง์์ง ๋
ธ๋๊ฐ black์ด๋ฉด,
- black-height๊ฐ 1 ๊ฐ์ํ ๊ฒฝ๋ก์ black node๊ฐ 1๊ฐ ์ถ๊ฐ๋๋๋ก rotationํ๊ณ ๋ ธ๋์ ์๊น์ ์กฐ์ ํ๋ค.
- ์ง์์ง ๋
ธ๋๊ฐ Red๋ผ๋ฉด,
- ํน์ฑ์ด ์๋ฐฐ๋์ง ์์ผ๋ฏ๋ก RBT๊ฐ ๊ทธ๋๋ก ์ ์ง๋๋ค.
Hash Table
ํด์๋ ๋ด๋ถ์ ์ผ๋ก ๋ฐฐ์ด์ ์ฌ์ฉํ์ฌ ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ๊ธฐ ๋๋ฌธ์ ๋น ๋ฅธ ๊ฒ์์๋๋ฅผ ๊ฐ์ง๋ค. ํน์ ํ ๊ฐ์ Searchํ ๋ ๋ฐ์ดํฐ ๊ณ ์ ์ ์ธ๋ฑ์ค(ํด์๊ฐ)์ผ๋ก ์ ๊ทผํ๋ฏ๋ก, ํ์์ฐ์ฐ์ ์๊ฐ๋ณต์ก๋๋ ํ๊ท O(1)์ด๋ค.(์ถฉ๋ ๋๋ฌธ์ ํญ์ O(1)์ ์๋)
์ด ์ธ๋ฑ์ค๋ก ์ฌ์ฉ๋ ํด์๊ฐ์ ํน๋ณํ ์๊ณ ๋ฆฌ์ฆ์ ํตํด ์ ์ฅํ ๋ฐ์ดํฐ์ ์ฐ๊ด๋ ๊ณ ์ ํ ์ซ์๋ฅผ ๋ง๋ค์ด ๋ธ ๋ค ์ด๋ฅผ ์ธ๋ฑ์ค๋ก ์ฌ์ฉํ๋ค. ์ด ์ธ๋ฑ์ค๋ ๊ทธ ๋ฐ์ดํฐ๋ง์ ๊ณ ์ ํ ์์น์ด๊ธฐ์ ์ฝ์ /์ญ์ ์ ๋ค๋ฅธ ๋ฐ์ดํฐ๋ก ์ฑ์ธ ํ์๊ฐ ์์ผ๋ฏ๋ก ์ฐ์ฐ์์ ์ถ๊ฐ์ ์ธ ๋น์ฉ์ด ์๋๋ก ๋ง๋ค์ด์ง ๊ตฌ์กฐ์ด๋ค.
Hash Function
ํด์๊ฐ์ ๋ง๋ค์ด๋ด๊ธฐ ์ํ ํจ์. ์ด ํจ์์ ์ํด ๋ฐํ๋ ๋ฐ์ดํฐ์ ๊ณ ์ ์ซ์๊ฐ์ hashcode๋ผ๊ณ ํ๋ฉฐ, ์ ์ฅ๋๋ ๊ฐ๋ค์ key๊ฐ์ hash function์ ํตํด์ ์์ ๋ฒ์์ ๊ฐ๋ค๋ก ๋ฐ๊ฟ์ค๋ค.
์ด๋ ์๋ก ๋ค๋ฅธ ๋ฐ์ดํฐ์ ๋์ผํ key ๊ฐ์ ๋์ถํด๋ผ ์ ์๊ณ , ์ด๋ฌํ ์ํฉ์ Collision์ด๋ผ๊ณ ํ๋ค.
Collision : ์๋ก ๋ค๋ฅธ ๋๊ฐ์ ํค๊ฐ ๊ฐ์ ์ธ๋ฑ์ค๋ก hasing ๋๋ฉด ๊ฐ์ ๊ณณ์ ์ ์ฅํ ์ ์๊ฒ ๋๋ค. collision์ด ๋ง์์ง์๋ก ํ์์ ํ์ํ ์๊ฐ๋ณต์ก๋๋ O(n)์ ๊ฐ๊น์์ง๋ค.
Resolve Conflict
Open Address(๊ฐ๋ฐฉ ์ฃผ์๋ฒ)
๋ค๋ฅธ ํด์ ๋ฒํท์ ์ถฉ๋์ด ๋ฐ์ํ ์๋ฃ๋ฅผ ์ฝ์ ํ๋ ๋ฐฉ์.
๋ค๋ฅธ ํด์๋ฒํท์ ์ฐพ๋๋ฐฉ๋ฒ : ์ต์
์ ๊ฒฝ์ฐ ์๋ ์๋ฆฌ๋ก ๋์์ด
1. Linear Probing : ์์ฐจ์ ์ผ๋ก ํ์ํ์ฌ ์ฒซ๋ฒ์งธ๋ก ๋ฐ๊ฒฌํ ๋น ๊ณณ์ ๋ฃ์
1. Quadratic probing : 2์ฐจํจ์๋ฅผ ์ด์ฉํด ์ฐพ์
1. Double hashing probing : 2์ฐจ ํด์ ํจ์๋ฅผ ์ฌ์ฉํด ์๋ก์ด ์ฃผ์๋ฅผ ํ ๋นํจ. ๋ง์ ์ฐ์ฐ๋์ด ํ์ํ๋ค.
Separate Chaining ๋ฐฉ์ (๋ถ๋ฆฌ์ฐ๊ฒฐ๋ฒ)
- ์ฐ๊ฒฐ๋ฆฌ์คํธ๋ฅผ ์ฌ์ฉํ๋ ๋ฐฉ์
- ๊ฐ๊ฐ์ ๋ฒํท๋ค์ ์ฐ๊ฒฐ๋ฆฌ์คํธ๋ก ๋ง๋ค์ด, Collision์ด ๋ฐ์ํ๋ฉด ํด๋น ๋ฒํท์ ๋ฆฌ์คํธ์ ๋์ ์ฝ์ ํ๋ ๋ฐฉ์
- ์ฝ์ /์ญ์ ๊ฐ ๊ฐ๋จํจ. Open Address ๋ฐฉ์์ ๋นํด ํ ์ด๋ธ์ ํ์ฅ์ ๋ฆ์ถ ์ ์๋ค.
- ์์ ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ ๋ ์ฐ๊ฒฐ๋ฆฌ์คํธ ์์ฒด์ ์ค๋ฒํค๋๊ฐ ๋ถ๋ด์ด ๋๋ค๋ ๋จ์ ์ด ์์.
- Tree๋ฅผ ์ฌ์ฉํ๋ ๋ฐฉ์(RBT)
- ์ ๋ฐฉ์๊ณผ ๋์ผํ๋ฐ ํธ๋ฆฌ๋ฅผ ์ฌ์ฉํ๋ ๊ฒ
์ฐ๊ฒฐ๋ฆฌ์คํธ vs Tree
- ํด์ ๋ฒํท์ ํ ๋น๋ key-value ์์ ๊ฐ์๋ก ์ด๋ ๊ฒ์ ์ฌ์ฉํ ์ง ๊ฒฐ์ ํจ
- ๋ฐ์ดํฐ์ ๊ฐ์๊ฐ ์ ๋ค๋ฉด ์ฐ๊ฒฐ๋ฆฌ์คํธ๋ฅผ ์ฌ์ฉํ๋ค. ํธ๋ฆฌ๋ ๋ฉ๋ชจ๋ฆฌ ์ฌ์ฉ๋์ด ๋ง๊ธฐ ๋๋ฌธ์ด๋ค.
- ์ด๋์ ๊ธฐ์ค์ 6๊ฐ, 8๊ฐ์ด๋ค. (6๊ฐ, 7๊ฐ์ผ๊ฒฝ์ฐ ๋ฐ์ดํฐ๊ฐ ํ๋์ฝ์ /ํ๋ ์ญ์ ๋ ๋๋ง๋ค ์๋ฃ๊ตฌ์กฐ๋ฅผ ๋ฐ๊ฟ์ผํจ. ๋ฐ๋ผ์ 2์นธ์ ์ฌ์ ๋ฅผ ๋ )
- ์์
- ํด์๋ฒํท์ 6๊ฐ์ key-value ์์ด ์๋๋ฐ ํ๋์ ๊ฐ์ด ์ถ๊ฐ๋จ. โ ์ฐ๊ฒฐ๋ฆฌ์คํธ ์ ์ง
- ๋ค์ ํ๋์ ๊ฐ์ด ์ญ์ ๋จ โ ์ฐ๊ฒฐ๋ฆฌ์คํธ ์ ์ง
- ๊ฐ์ด ๋ค์ 2๊ฐ๊ฐ ์ถ๊ฐ๋จ โ ํธ๋ฆฌ๋ก ๋ณ๊ฒฝ
- ํ๋๊ฐ ์ญ์ ๋จ โ ํธ๋ฆฌ ์ ์ง
- ํ๋๊ฐ ์ญ์ ๋จ โ ์ฐ๊ฒฐ๋ฆฌ์คํธ๋ก ๋ณ๊ฒฝ
๋ณด์กฐํด์ํจ์
key์ ํด์๊ฐ์ ๋ณํํ์ฌ ํด์ ์ถฉ๋ ๊ฐ๋ฅ์ฑ์ ์ค์ด๋ ๊ฒ. Separate chaining๋ฐฉ์์ ์ฌ์ฉํ ๋ ํจ๊ป ์ฌ์ฉ๋๋ฉฐ, ๋ณด์กฐํด์ํจ์๋ก worst case์ ๊ฐ๊น์ ์ง๋ ๊ฒฝ์ฐ๋ฅผ ์ค์ผ ์ ์๋ค.
Open address vs Separate Chaining
๋๋ค worst case์์๋ O(M)์. ํ์ง๋ง Open Address ๋ฐฉ์์ ์ฐ์๋ ๊ณต๊ฐ์ ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ๊ธฐ ๋๋ฌธ์ Separate Chaining์ ๋นํด ์บ์ ํจ์จ์ด ๋๋ค. ๋ฐ๋ผ์ ๋ฐ์ดํฐ๊ฐ ์ถฉ๋ถํ ์ ์ผ๋ฉด Open Adderess๊ฐ ์ข๋ค.
ํ์ง๋ง Open Address๋ ๋ฒํท์ ๊ณ์ ์ฌ์ฉํ๊ธฐ์ ํ ์ด๋ธ์ ํ์ฅ์ด ์์ฃผ ์ผ์ด๋๋ค.
ํด์ ๋ฒํท ๋์ ํ์ฅ(resize)
ํด์๋ฒํท์ ๊ฐ์๊ฐ ์ ์ผ๋ฉด ํด์ ์ถฉ๋๋ก ์ฑ๋ฅ์ ์์ค์ด ๋ฐ์ํจ. ๋ฐ๋ผ์ key-value ์ ๋ฐ์ดํฐ ๊ฐ์๊ฐ ์ผ์ ๊ฐ์ ์ด์์ด ๋๋ฉด ํด์ ๋ฒํท์ ๊ฐ์๋ฅผ ๋๋ฐฐ๋ก ๋๋ฆฐ๋ค. ์ด๋ ๊ฒ ํ๋ฉด ํด์ ์ถฉ๋๋ก ์ธํ ์ฑ๋ฅ์ ํ๋ฅผ ์ด๋์ ๋ ํด๊ฒฐํ ์ ์๋ค.
์ด๋ ๋๋ฐฐ๋ก ํ์ฅํ๋ ์๊ณ์ ์ ๊ธฐ์กด ํด์๋ฒํท ๊ฐ์์ 75%์ด๋ค.
Graph
Undirected Graph ์ Directed Graph (Digraph)
- Directed Graph : ๋ฐฉํฅ์ฑ์ด ํฌํจ๋ ๊ทธ๋ํ
- Undirected Graph : ๋ฐฉํฅ์ฑ์ด ์๋ ๊ทธ๋ํ
Degree
๊ฐ ์ ์ ์ ์ฐ๊ฒฐ๋ Edge์ ๊ฐ์. ๋ฐฉํฅ๊ทธ๋ํ์ผ๊ฒฝ์ฐ Degree๊ฐ ๋๋ก ๋๋๋ค.
๊ฐ์ค์น ๊ทธ๋ํ
๊ฐ์ ์ด ๊ฐ์ค์น๋ฅผ ๋์ด์ ๊ตฌ์ฑํ ๊ทธ๋ํ
๋ถ๋ถ๊ทธ๋ํ
๋ณธ๋ ๊ทธ๋ํ์ ์ผ๋ถ ์ ์ ๋ฐ ๊ฐ์ ์ผ๋ก ์ด๋ฃจ์ด์ง ๊ทธ๋ํ
๊ทธ๋ํ ๊ตฌํ๋ฒ
์ธ์ ํ๋ ฌ
- ํด๋นํ๋ ์์น์ value๋ฅผ ํตํด ์ ์ ๊ฐ์ ์ฐ๊ฒฐ์ ๋ณด๋ฅผ O(1)๋ก ํ์ ํ ์ ์์.
- Edge์ ๊ฐ์์ ๋ฌด๊ดํ๊ฒ V^2์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์ฐจ์งํจ
- Dense Graph๋ฅผ ํํํ ๋ ์ ํฉํจ
์ธ์ ๋ฆฌ์คํธ : ์ฐ๊ฒฐ๋ฆฌ์คํธ
- vertex์ ๋ฆฌ์คํธ๋ฅผ ํ์ธํด์ผํ๊ธฐ ๋๋ฌธ์, ์ ์ ๊ฐ ์ฐ๊ฒฐ ํ์ธ์ ์ค๋ ๊ฒฐ๋ฆฐ๋ค.
- ๋ฉ๋ชจ๋ฆฌ๋ O(E + V)๋ฅผ ์ฐจ์งํจ
- Sparse Graph๋ฅผ ํํํ ๋ ์ ํฉํจ.
๊ทธ๋ํ ํ์
DFS
- ์ฐ๊ฒฐ๋์ด์๋ ์ ์ ์ผ๋ก ๊ณ์ ๊ฐ๋ค๊ฐ ๋์ด์ ์ฐ๊ฒฐ๋ ์ ์ ์ด ์์ผ๋ฉด ๋๋์์์ ๋ค์ ํ์ํจ
- O(V +E)
BFS
- ํ ์ ์ ์ ์ฐ๊ฒฐ๋์ด์๋ ๋ชจ๋ ์ ์ ์ผ๋ก ๋์๊ฐ
- O(V + E). BFS๋ก ๊ตฌํ ๊ฒฝ๋ก๋ ๋ฃจํธ๋ก๋ถํฐ ํด๋น ๋ ธ๋๋ก์ ์ต๋จ ๊ฒฝ๋ก์
์ต์์ ์ฅํธ๋ฆฌ(MST)
ํฌ๋ฃจ์ค์นผ
๊ฐ์ค์น๊ฐ ๊ฐ์ฅ ๋ฎ์ edge๋ฅผ ํ๋์ฉ ์ถ๊ฐํ๋, ์ฌ์ดํด์ ํ์ฑํ์ง ์๋ edge๋ฅผ ์ถ๊ฐํ๋ ๊ฒ. V - 1๊ฐ์ Edge๊ฐ ์ถ๊ฐ๋๋ฉด ์ ์งํจ.
์๊ฐ ๋ณต์ก๋
- Edge์ weight๋ฅผ ๊ธฐ์ค์ผ๋ก sorting - O(ElogE)
- cycle ์์ฑ์ฌ๋ถ๋ฅผ ๊ฒ์ฌํ๊ณ id๋ฅผ ํต์ผ โ O(E + V log V)
Prim
ํ์ฌ๊น์ง์ ๊ทธ๋ํ์ ์์ง ์ถ๊ฐ๋์ง ์์ ๋ ธ๋์ ์ฐ๊ฒฐ๋์ด ์๋ ๊ฐ์ ์ค์์ ๊ฐ์ฅ ์์ ๊ฐ์ค์น๋ฅผ ๊ฐ์ง๋ ๊ฐ์ ๋ง ์ถ๊ฐํจ.
์๊ฐ๋ณต์ก๋ : O(E logv)