[์๋ฃ๊ตฌ์กฐ] ์๋ฃ๊ตฌ์กฐ (data structure)
์๋ฃ๊ตฌ์กฐ๋?
๋ฐ์ดํฐ๋ฅผ ํจ์จ์ ์ผ๋ก ์ ์ฅํ๊ณ ๊ด๋ฆฌํ๊ธฐ ์ํ ๊ตฌ์กฐ
๋ฐ์ดํฐ๋ฅผ ์ด๋ป๊ฒ ์กฐ์งํ๊ณ ์ ์ฅํ๋๋์ ๋ฐ๋ผ ๊ฒ์, ์ฝ์ , ์ญ์ ๋ฑ์ ์์ ์ด ๋ ๋น ๋ฅด๊ณ ๊ฐ๋จํ๊ฒ ์ด๋ฃจ์ด์ง ์ ์๋ค.
์๋ฃ๊ตฌ์กฐ๋ ํน์ ์ํฉ์์ ๋ ํจ์จ์ ์ธ ์ฑ๋ฅ์ ๋ณด์ด๋ฉฐ, ๊ฐ๋ฐ์๋ ๋ฌธ์ ์ ๋ง๋ ์๋ฃ๊ตฌ์กฐ๋ฅผ ์ ํํด ์ฑ๋ฅ์ ์ต์ ํํ ์ ์๋ค.
๊ตฌํ ๋ฐ ์ธ๋ถ๋ด์ฉ
1. Array.
[์๋ฃ๊ตฌ์กฐ] ๋ฐฐ์ด (Array)
๋ฐฐ์ด์ด๋?๊ฐ์ฅ ๊ธฐ๋ณธ์ ์ธ ๋ฐ์ดํฐ๊ตฌ์กฐ๋ฅผ ์ด์ผ๊ธฐํ๋ค.๋์ผํ ํ์ ์ ๋ฐ์ดํฐ๋ฅผ ์ฐ์์ ์ธ ๋ฉ๋ชจ๋ฆฌ ์์น์ ์ ์ฅํ๋ค.์ฅ๋จ์ ์ฅ์ ์ธ๋ฑ์ค๋ฅผ ํตํด ๊ฐ ์์์ O(1) ์๊ฐ์ ์ ๊ทผ ๊ฐ๋ฅํ๋ค.๊ตฌํ์ด ๊ฐ๋จํ๊ณ
jun-13.tistory.com
2. Linked list.
[์๋ฃ๊ตฌ์กฐ] ๋งํฌ๋๋ฆฌ์คํธ (Linked list)
๋งํฌ๋๋ฆฌ์คํธ (Linked list) ๋?์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ ๊ฐ ๋ ธ๋๊ฐ ๋ฐ์ดํฐ์ ๋ค์ ๋ ธ๋์ ์ฃผ์๋ฅผ ํฌํจํ์ฌ ์์ฐจ์ ์ผ๋ก ์ฐ๊ฒฐ๋ ์๋ฃ๊ตฌ์กฐ๋์ ์ผ๋ก ํฌ๊ธฐ๋ฅผ ์กฐ์ ํ ์ ์๋ค.๊ธฐ์กด์ ์ผ๋ก๋ ํ์ฌ์ ๋ ธ๋๊ฐ ๋ค์ ๋ ธ
jun-13.tistory.com
3. Stack.
[์๋ฃ๊ตฌ์กฐ] ์คํ (Stack)
์คํ์ด๋?์คํ์ LIFO(Last In, First Out) ๊ตฌ์กฐ๋ก, ๋ง์ง๋ง์ ๋ค์ด๊ฐ ๋ฐ์ดํฐ๊ฐ ๊ฐ์ฅ ๋จผ์ ๋์ค๋ ์๋ฃ๊ตฌ์กฐ๋ฅผ ์ด์ผ๊ธฐํ๋ค.์์ธ ์ ์๋ ํ๋ ธ์ด ํ์ ์์๋ก ์๊ฐํ๋ฉด ๋๋ค.์ฅ๋จ์ ์ฅ์ ๋ฐ์ดํฐ์ ์ฝ์ ๊ณผ ์ญ
jun-13.tistory.com
4. Queue.
[์๋ฃ๊ตฌ์กฐ] ํ (Queue)
ํ (Queue) ๋?ํ๋ FIFO(First In, First Out) ๊ตฌ์กฐ๋ก, ๋จผ์ ๋ค์ด์จ ๋ฐ์ดํฐ๊ฐ ๋จผ์ ๋๊ฐ๋ ์๋ฃ๊ตฌ์กฐ์คํ๊ณผ๋ ๋ค๋ฅด๊ฒ ๋จผ์ ๋ค์ด์จ๊ฒ์ด ๋จผ์ ๋๊ฐ๋ FIFO ๊ตฌ์กฐ๋ฅผ ๊ฐ์ง๊ณ ์๋ค.์ฅ๋จ์ ์ฅ์ ๋ฐ์ดํฐ์ ์ฝ์ ๊ณผ ์ญ์
jun-13.tistory.com
5. Tree.
[์๋ฃ๊ตฌ์กฐ] ํธ๋ฆฌ (Tree)
ํธ๋ฆฌ (Tree) ๋?ํธ๋ฆฌ๋ ๊ณ์ธต์ ์ธ ๊ตฌ์กฐ๋ฅผ ๊ฐ์ง ์๋ฃ๊ตฌ์กฐ๋ก, ๋ถ๋ชจ์ ์์ ๋ ธ๋ ๊ฐ์ ๊ด๊ณ๋ฅผ ๋ํ๋ธ๋ค. ๋ฐ์ดํฐ ๊ตฌ์กฐํ๊ฐ ์ฉ์ดํด ํ์ผ ์์คํ , ๊ณ์ธต์ ๋ฐ์ดํฐ ์ ์ฅ ๋ฑ์ ์ฌ์ฉ ๊ฐ๋ฅ.์ฅ๋จ์ ์ฅ์ ๋ฐ์ดํฐ
jun-13.tistory.com
6. Graph.
[์๋ฃ๊ตฌ์กฐ] ๊ทธ๋ํ (Graph)
๊ทธ๋ํ (Graph) ๋?๊ทธ๋ํ๋ ์ ์ (vertex)๊ณผ ๊ฐ์ (edge)๋ก ์ด๋ฃจ์ด์ง ์๋ฃ๊ตฌ์กฐํธ๋ฆฌ (Tree) ์ ๋ฌด์จ ์ฐจ์ด๊ฐ ์๋๊ณ ์๊ฐํ ์ ์๋๋ฐ,๊ทธ๋ํ์ ๊ฒฝ์ฐ์๋ ํธ๋ฆฌ์ ๋ค๋ฅด๊ฒ ์ ์ ๋ง๋ค ๊ฐ์ ์ด ์์ ์๋ ์๊ณ ๋ถ
jun-13.tistory.com
7. Trie.
[์๋ฃ๊ตฌ์กฐ] ํธ๋ผ์ด (Trie)
ํธ๋ผ์ด (Trie) ๋?๋ฌธ์์ด์ ์ ์ฅํ๊ณ , ํจ์จ์ ์ผ๋ก ํ์ํ๊ธฐ ์ํ ํธ๋ฆฌ ํํ์ ์๋ฃ๊ตฌ์กฐtree ํํ์ ์๋ฃ๊ตฌ์กฐ์ ๋ณด ๊ฒ์ ๊ฐ์ ๋ถ์ผ์์ ํ์ฉ๋๋ค.์ฅ๋จ์ ์ฅ์ ๋ฌธ์์ด ๊ฒ์์ ํจ์จ์ ์ด๋ฉฐ, ์ ๋์ฌ ๊ฒ
jun-13.tistory.com
8. Hash table.
[์๋ฃ๊ตฌ์กฐ] ํด์ ํ ์ด๋ธ (Hash Table)
ํด์ ํ ์ด๋ธ (Hash Table) ๋?ํค-๊ฐ ์์ ๋น ๋ฅด๊ฒ ์ฝ์ , ์กฐํ, ์ ๊ฑฐํ๋ ๋ฐ ์ฌ์ฉ๋๋ ๋ฐ์ดํฐ ๊ตฌ์กฐ ์ฅ๋จ์ ์ฅ์ ํ๊ท ์ ์ผ๋ก O(1)์ ์๊ฐ์ ๊ฒ์, ์ฝ์ , ์ญ์ ๊ฐ ๊ฐ๋ฅํด ๋น ๋ฆ.ํฐ ๋ฐ์ดํฐ๋ฅผ ๊ด๋ฆฌํ๊ธฐ์ ์ ๋ฆฌ
jun-13.tistory.com
9. Heap.
[์๋ฃ๊ตฌ์กฐ] ํ (Heap)
ํ (Heap) ๋?ํน์ํ ํธ๋ฆฌ ๊ธฐ๋ฐ ๋ฐ์ดํฐ ๊ตฌ์กฐํ์ ์ฐ์ ์์ ํ๋ฅผ ๊ตฌํํ๊ธฐ ์ํ ์์ ์ด์ง ํธ๋ฆฌ ํํ์ ์๋ฃ๊ตฌ์กฐ์ต๋ ํ (Max Heap)๊ณผ ์ต์ ํ(Min Heap) ์ด 2๊ฐ์ง๊ฐ ์กด์ฌํ๋ค.์ต๋ ํ (Max Heap)๋ถ๋ชจ์ ๋ ธ
jun-13.tistory.com