CS

[์ž๋ฃŒ๊ตฌ์กฐ] ์ž๋ฃŒ๊ตฌ์กฐ (data structure)

moaoh 2024. 10. 29. 20:19

์ž๋ฃŒ๊ตฌ์กฐ๋ž€?

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