Array ๋ฐฐ์ด, Queue ํ, Stack ์คํ, Linked List ๋งํฌ๋ ๋ฆฌ์คํธ, Hash ํด์ฌ, Tree ํธ๋ฆฌ, Heap ํ
- ๋ฐ์ดํฐ๋ฅผ ๋์ดํ๊ณ , ๊ฐ ๋ฐ์ดํฐ๋ฅผ ์ธ๋ฑ์ค์ ๋์ํ๋๋ก ๊ตฌ์ฑํ ๋ฐ์ดํฐ ๊ตฌ์กฐ
- ํ์ด์ฌ์์๋ ๋ฆฌ์คํธ ํ์ ์ด ๋ฐฐ์ด ๊ธฐ๋ฅ์ ์ ๊ณต
- ๊ฐ์ ์ข ๋ฅ์ ๋ฐ์ดํฐ๋ฅผ ํจ์จ์ ์ผ๋ก ๊ด๋ฆฌํ๊ธฐ ์ํด ์ฌ์ฉ
- ๊ฐ์ ์ข ๋ฅ์ ๋ฐ์ดํฐ๋ฅผ ์์ฐจ์ ์ผ๋ก ์ ์ฅ
๐ก Array BAJ TIL
2750 2751 10989 25305 2108 1427 11650 11651 1181 10814 18870
- ๊ฐ์ฅ ๋จผ์ ๋ฃ์ ๋ฐ์ดํฐ๋ฅผ ๋จผ์ ๊บผ๋ผ ์ ์๋ ๊ตฌ์กฐ
- ๋์ด๊ณต์์ ๊ฐ์ฅ ๋จผ์ ์ค์ ์ ์ฌ๋์ด ์ ์ผ ๋จผ์ ์ ์ฅํ๋ ๊ฒ๊ณผ ๋์ผ
- FIFO ๋๋ LILO ๋ฐฉ์์ผ๋ก ์คํ๊ณผ ๊บผ๋ด๋ ์์๊ฐ ๋ฐ๋
- Enqueue : ํ์ ๋ฐ์ดํฐ๋ฅผ ๋ฃ๋ ๊ธฐ๋ฅ (= put)
- Dequeue: ํ์์ ๋ฐ์ดํฐ๋ฅผ ๊บผ๋ด๋ ๊ธฐ๋ฅ (=get)
๐ก Queue BAJ TIL
18258 2164 11866 1966 10866 1021 5430
-
๋ฐ์ดํฐ๋ฅผ ์ ํ์ ์ผ๋ก ์ ๊ทผํ ์ ์๋ ๊ตฌ์กฐ (ํ์ชฝ ๋์์๋ง ์๋ฃ๋ฅผ ๋ฃ๊ฑฐ๋ ๋บผ ์ ์๋ ๊ตฌ์กฐ )
-
๊ฐ์ฅ ๋์ค์ ์์ ๋ฐ์ดํฐ๋ฅผ ๊ฐ์ฅ ๋จผ์ ๋นผ๋ผ ์ ์๋ ๋ฐ์ดํฐ ๊ตฌ์กฐ (ํ FIFO vs ์คํ LIFO)
-
๋ํ์ ํ์ฉ : ์ปดํจํฐ ๋ด๋ถ์ ํ๋ก์ธ์ค ๊ตฌ์กฐ์ ํจ์ ๋์ ๋ฐฉ์
-
push() : ๋ฐ์ดํฐ๋ฅผ ์คํ์ ๋ฃ๊ธฐ pop() : ๋ฐ์ดํฐ๋ฅผ ์คํ์์ ๊บผ๋ด๊ธฐ
๐ก Stack BAJ TIL
10828 10773 9012 4949 1874 17298
- Linked List VS Array
- ๋ฐฐ์ด์ ์์ฐจ์ ์ผ๋ก ์ฐ๊ฒฐ๋ ๊ณต๊ฐ์ ๋ฐ์ดํฐ๋ฅผ ๋์ดํ๋ ๋ฐ์ดํฐ ๊ตฌ์กฐ
- ๋งํฌ๋ ๋ฆฌ์คํธ๋ ๋จ์ด์ง ๊ณณ์ ์กด์ฌํ๋ ๋ฐ์ดํฐ๋ฅผ ํ์ดํ๋ก ์ฐ๊ฒฐํด์ ๊ด๋ฆฌํ๋ ๋ฐ์ดํฐ ๊ตฌ์กฐ
- C์ธ์ด๋ ์ฃผ์ํ ๋ฐ์ดํฐ ๊ตฌ์กฐ์ด์ง๋ง ํ์ด์ฌ์ ๋ฆฌ์คํธ ํ์ ์ด ๋งํฌ๋ ๋ฆฌ์คํธ์ ๊ธฐ๋ฅ์ ๋ชจ๋ ์ง์
- NODE : ๋ฐ์ดํฐ ์ ์ฅ๋จ์ (๋ฐ์ดํฐ ๊ฐ, ํฌ์ธํฐ)๋ก ๊ตฌ์ฑ (๊ตฌํ ์ ํ์ด์ฌ ๊ฐ์ฒด์งํฅ ๋ฌธ๋ฒ ์ดํด ํ์)
- Pointer : ๊ฐ ๋ ธ๋ ์์์, ๋ค์์ด๋ ์ด์ ์ ๋ ธ๋์์ ์ฐ๊ฒฐ ์ ๋ณด๋ฅผ ๊ฐ์ง๊ณ ์๋ ๊ณต๊ฐ
์ฅ์ | ๋จ์ _ ์ผ๋ฐ์ ์ธ ์คํ ๊ตฌํ ์ |
---|---|
๋ฏธ๋ฆฌ ๋ฐ์ดํฐ ๊ณต๊ฐ์ ๋ฏธ๋ฆฌ ํ ๋นํ์ง ์์๋ ๋จ | ์ฐ๊ฒฐ์ ์ํ ๋ณ๋ ๋ฐ์ดํฐ ๊ณต๊ฐ์ด ํ์ํ๋ฏ๋ก, ์ ์ฅ ๊ณต๊ฐ ํจ์จ์ด ๋์ง ์์ |
(๋ฐ๋ฉด, ๋ฐฐ์ด์ ๋ฏธ๋ฆฌ ๋ฐ์ดํฐ ๊ณต๊ฐ์ ํ ๋นํด์ผํ๋ ์ ์ด ์๋ค.) | ์ฐ๊ฒฐ ์ ๋ณด๋ฅผ ์ฐพ๋ ์๊ฐ์ด ํ์ํ๋ฏ๋ก ์ ๊ทผ ์๋๊ฐ ๋๋ฆฌ๋ค. |
- | ์ค๊ฐ ๋ฐ์ดํฐ ์ญ์ ์, ์๋ค ๋ฐ์ดํฐ์ ์ฐ๊ฒฐ์ ์ฌ๊ตฌ์ฑํด์ผ ํ๋ ๋ถ๊ฐ์ ์ธ ์์ ํ์ |
ํด์ฌ Hash | ์์ ๊ฐ์ ๊ณ ์ ๊ธธ์ด๋ก ๋ณํํ๋ ๊ฒ |
---|---|
ํด์ฌ ํ ์ด๋ธ Hash Table | ํค ๊ฐ์ ์ฐ์ฐ์ ์ํด ์ง์ ์ ๊ทผ์ด ๊ฐ๋ฅํ ๋ฐ์ดํฐ ๊ตฌ์กฐ |
ํด์ฑ ํจ์ Hashing Function | Key์ ๋ํด ์ฐ์ ์ฐ์ฐ์ ์ด์ฉํด ๋ฐ์ดํฐ ์์น๋ฅผ ์ฐพ์ ์ ์๋ ํจ์ |
ํด์ฌ ๊ฐ Hash Vale | Key๋ฅผ ํด์ฑ ํจ์๋ก ์ฐ์ฐํด์, ํด์ฌ ๊ฐ์ ์์๋ด๊ณ , ์ด๋ฅผ ๊ธฐ๋ฐ์ผ๋ก ํด์ฌ ํ ์ด๋ธ์์ ํด๋น Key์ ๋ํ ๋ฐ์ดํฐ ์์น๋ฅผ ์ผ๊ด์ฑ์๊ฒ ์ฐพ์ ์ ์์ |
์ฌ๋กฏ Slot | ํ ๊ฐ์ ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ ์ ์๋ ๊ณต๊ฐ |
๐ก Hash BAJ TIL
15829
- Node์ Branch๋ฅผ ์ด์ฉํด์ ์ฌ์ดํด์ ์ด๋ฃจ์ง ์๋๋ก ๊ตฌ์ฑํ ๋ฐ์ดํฐ ๊ตฌ์กฐ
- ์ด๋์ ์ฌ์ฉ?
- ํธ๋ฆฌ ์ค ์ด์งํธ๋ฆฌ์ ํํ์ ๊ตฌ์กฐ๋ก, ํ์(๊ฒ์)์๊ณ ๋ฆฌ์ฆ ๊ตฌํ์ ์ํด ๋ง์ด ์ฌ์ฉ๋๋ค.
-
Node: ํธ๋ฆฌ์์ ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ๋ ๊ธฐ๋ณธ ์์ (๋ฐ์ดํฐ์ ๋ค๋ฅธ ์ฐ๊ฒฐ๋ ๋ ธ๋์ ๋ํ Branch ์ ๋ณด ํฌํจ)
-
Root Node: ํธ๋ฆฌ ๋งจ ์์ ์๋ ๋ ธ๋
-
Level: ์ต์์ ๋ ธ๋๋ฅผ Level 0์ผ๋ก ํ์์ ๋, ํ์ Branch๋ก ์ฐ๊ฒฐ๋ ๋ ธ๋์ ๊น์ด๋ฅผ ๋ํ๋
-
Parent Node: ์ด๋ค ๋ ธ๋์ ๋ค์ ๋ ๋ฒจ์ ์ฐ๊ฒฐ๋ ๋ ธ๋
-
Child Node: ์ด๋ค ๋ ธ๋์ ์์ ๋ ๋ฒจ์ ์ฐ๊ฒฐ๋ ๋ ธ๋
-
Leaf Node (Terminal Node): Child Node๊ฐ ํ๋๋ ์๋ ๋ ธ๋
-
Sibling (Brother Node): ๋์ผํ Parent Node๋ฅผ ๊ฐ์ง ๋ ธ๋
-
Depth: ํธ๋ฆฌ์์ Node๊ฐ ๊ฐ์ง ์ ์๋ ์ต๋ Level
๐ก Tree BAJ TIL
11725 1167
-
๋ฐ์ดํฐ์์ ์ต๋๊ฐ๊ณผ ์ต์๊ฐ์ ๋น ๋ฅด๊ฒ ์ฐพ๊ธฐ ์ํด ๊ณ ์๋ ์์ ์ด์ง ํธ๋ฆฌ (complete binary tree)
-
์์ ์ด์ง ํธ๋ฆฌ: ๋ ธ๋๋ฅผ ์ฝ์ ํ ๋ ์ตํ๋จ ์ผ์ชฝ ๋ ธ๋๋ถํฐ ์ฐจ๋ก๋๋ก ์ฝ์ ํ๋ ํธ๋ฆฌ
-
ํ์ ์ต๋๊ฐ์ ๊ตฌํ๊ธฐ ์ํ ๊ตฌ์กฐ (์ต๋ ํ, Max Heap) ์, ์ต์๊ฐ์ ๊ตฌํ๊ธฐ ์ํ ๊ตฌ์กฐ (์ต์ ํ, Min Heap) ๋ก ๋ถ๋ฅํ ์ ์์
-
ํ์ ๋ค์๊ณผ ๊ฐ์ด ๋ ๊ฐ์ง ์กฐ๊ฑด์ ๊ฐ์ง๊ณ ์๋ ์๋ฃ๊ตฌ์กฐ
- ๊ฐ ๋ ธ๋์ ๊ฐ์ ํด๋น ๋ ธ๋์ ์์ ๋ ธ๋๊ฐ ๊ฐ์ง ๊ฐ๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๋ค. (์ต๋ ํ์ ๊ฒฝ์ฐ)
- ์์ ์ด์ง ํธ๋ฆฌ ํํ๋ฅผ ๊ฐ์ง
-
ํ์ ์์ ์ด์ง ํธ๋ฆฌ์ด๋ฏ๋ก, ์ฝ์ ํ ๋ ธ๋๋ ๊ธฐ๋ณธ์ ์ผ๋ก ์ผ์ชฝ ์ตํ๋จ๋ถ ๋ ธ๋๋ถํฐ ์ฑ์์ง๋ ํํ๋ก ์ฝ์
- ๋ฐฐ์ด์ ๋ฐ์ดํฐ๋ฅผ ๋ฃ๊ณ , ์ต๋๊ฐ๊ณผ ์ต์๊ฐ์ ์ฐพ์ผ๋ ค๋ฉด O(n)์ด ๊ฑธ๋ฆผ
- ์ด์ ๋ฐํด, ํ์ ๋ฐ์ดํฐ๋ฅผ ๋ฃ๊ณ ์ต๋๊ฐ๊ณผ ์ต์๊ฐ์ ์ฐพ์ผ๋ฉด O(log) ๊ฑธ๋ฆผ
- ์ฐ์ ์์ ํ์ ๊ฐ์ด ์ต๋๊ฐ ๋๋ ์ต์๊ฐ์ ๋น ๋ฅด๊ฒ ์ฐพ์์ผ ํ๋ ์๋ฃ ๊ตฌ๋ ธ ๋ฐ ์๊ณ ๋ฆฌ์ฆ ๊ตฌํ๋ฑ์ ํ์ฉ๋จ
๋ง์ฝ ์๋ง์ ๋ณ๋ค์ค 70๋ฒ์งธ์ ์ซ์๊ฐ ์ ํ ๋ณ๋๊ป์ ์ฐพ๊ฒ ๋๋ค๋ฉด?
-
์ ๋ ฌ์ด ๋์ด์๋ค๋ ์กฐ๊ฑดํ์์ 1/2์ฉ ๋์ฐ์ด ์ค๊ฐ์ ์ฒดํฌํ๊ณ ์ด๋์ชฝ์ ์๋์ง ํ๋จํด์ผ ํ๋ค.
-
์ด์งํ์ vs ์์ฐจํ์ => ์ด์งํ์ ์๋๊ฐ ํจ์ฌ ๋น ๋ฅด๋ค.
๋ถํ ์ ๋ณต ์๊ณ ๋ฆฌ์ฆ๊ณผ ์ด์งํ์ (Devide and Conquer)
์ฃผ๋ก ์ฌ๊ท์ฉ๋ฒ์ ๊ฐ์ง๊ณ ๊ตฌํํ๋ค.
Devide : ๋ฌธ์ ๋ฅผ ํ๋ ๋๋ ๋ ์ด์์ผ๋ก ๋๋๋ค.
Conquer : ๋๋ ์ง ๋ฌธ์ ๊ฐ ์ถฉ๋ถํ ์๊ณ , ํด๊ฒฐ์ด ๊ฐ๋ฅํ๋ค๋ฉด ํด๊ฒฐํ๊ณ ๊ทธ๋ ์ง ์๋ค๋ฉด ๋ค์ ๋๋๋ค.
์ด์ง ํ์ Devide , Conquer
๋ฆฌ์คํธ๋ฅผ 2๊ฐ์ ์ค๋ธ ๋ฆฌ์คํธ๋ก ๋๋๋ค.
๊ฒ์ํ ์ซ์(search) > ์ค๊ฐ๊ฐ์ด๋ฉด, ๋ท๋ถ๋ถ์ ์๋ธ๋ฆฌ์คํธ์์ ๊ฒ์ํ ์ซ์ ์ฐพ๊ธฐ
๊ฒ์ํ ์ซ์(search) < ์ค๊ฐ๊ฐ ์ด๋ฉด, ์๋ถ๋ถ์ ์๋ธ ๋ฆฌ์คํธ์์ ๊ฒ์ํ ์ซ์๋ฅผ ์ฐพ๊ธฐ
์์ฐจํ์ Sequential Search
์ฌ๋ฌ ๋ฐ์ดํฐ ์ค์์ ์ํ๋ ๋ฐ์ดํฐ๋ฅผ ์ฐพ์๋ด๋ ๊ฒ์ ์๋ฏธ
๋ฐ์ดํฐ๊ฐ ๋ด๊ฒจ์๋ ๋ฆฌ์คํธ๋ฅผ ์์์ ๋ถํฐ ํ๋์ฉ ๋น๊ตํด์ ์ฐ๋ํ๋ ๋ฐ์ดํฐ๋ฅผ ์ฐพ๋ ๋ฐฉ๋ฒ