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. ๋ฃจํŠธ๋…ธ๋“œ๋Š” 1๋ถ€ํ„ฐ ์‹œ์ž‘.
  2. ์‚ฝ์ž… ์—ฐ์‚ฐ
    • ํŠธ๋ฆฌ์˜ ๊ฐ€์žฅ ๋งˆ์ง€๋ง‰์— ์‚ฝ์ž…
    • ๋ถ€๋ชจ์™€ ๊ฐ’์„ ๋น„๊ตํ•ด๊ฐ€๋ฉฐ ์˜ฌ๋ผ๊ฐ
    • ์ตœ์†Œํž™์ผ ๊ฒฝ์šฐ, ๋ถ€๋ชจ๋ณด๋‹ค ํด๊ฒฝ์šฐ ๋ฉˆ์ถค
  3. ์‚ญ์ œ ์—ฐ์‚ฐ
    • ๋ฃจํŠธ ๋…ธ๋“œ๊ฐ€ ์‚ฌ์šฉ์ž์˜ ์š”์ฒญ์œผ๋กœ ์‚ฌ๋ผ์ง
    • ๊ฐ€์žฅ ๋์˜ ๋…ธ๋“œ๋ฅผ ๋ฃจํŠธ๋…ธ๋“œ์— ์‚ฝ์ž…
    • ๋‘ ์ž์‹๋ณด๋‹ค ๊ฐ’์ด ์ž‘์„ ๋•Œ๊นŒ์ง€ ์•„๋ž˜๋กœ ๋‚ด๋ ค๊ฐ(๋‘˜ ์ค‘ ํ•˜๋‚˜๋งŒ ๋ณธ์ธ๋ณด๋‹ค ์ž‘์„ ๊ฒฝ์šฐ ๊ทธ์ชฝ๊ณผ ๊ตํ™˜. ๋‘˜ ๋‹ค ์ž‘์„ ๊ฒฝ์šฐ ์•„๋ฌด๋ฐ๋กœ)

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๋กœ ๊ฐ„์ฃผํ•œ๋‹ค.

์‚ฝ์ž…

  1. BST(์ด์ง„ํƒ์ƒ‰ํŠธ๋ฆฌ)์˜ ํŠน์„ฑ์„ ์œ ์ง€ํ•˜๋ฉด์„œ ์‚ฝ์ž…ํ•œ๋‹ค.
  2. ์‚ฝ์ž…๋œ ๋…ธ๋“œ์— Red๋ฅผ ๋ถ€์—ฌํ•œ๋‹ค.
  3. RBT์˜ ํŠน์„ฑ์„ ์œ„๋ฐฐํ–ˆ์„ ์‹œ ๋…ธ๋“œ์˜ ์ƒ‰๊น”์„ ์กฐ์ •ํ•˜๊ณ , Black-height๊ฐ€ ์œ„๋ฐฐ๋˜์—ˆ๋‹ค๋ฉด rotation์„ ํ†ตํ•ด height๋ฅผ ์กฐ์ •ํ•œ๋‹ค.
    • ๋‹ค๋ฅธ ์„ค๋ช…
      • Recoloring : ์‚ฝ์ž…๋œ ๋…ธ๋“œ์˜ ๋ถ€๋ชจ์˜ ํ˜•์ œ ์ƒ‰๊น”์ด Red์ผ ๊ฒฝ์šฐ
        • ๋ถ€๋ชจ์™€ ๋ถ€๋ชจ์˜ ํ˜•์ œ ๋…ธ๋“œ๋Š” Black์œผ๋กœ, ๋ถ€๋ชจ์˜ ๋ถ€๋ชจ๋Š” Red๋กœ(๋‹จ, ๋ฃจํŠธ๋…ธ๋“œ์ผ๊ฒฝ์šฐ Black์œผ๋กœ ๋†”๋‘ 
        • ๋‹ค์‹œ double red๊ฐ€ ๋ฐœ์ƒํ–ˆ์„ ๊ฒฝ์šฐ ๋‹ค์‹œ ์ž‘์—…
      • Restructuring : ์‚ฝ์ž…๋œ ๋…ธ๋“œ์˜ ๋ถ€๋ชจ์˜ ํ˜•์ œ ์ƒ‰๊น”์ด Black ๋˜๋Š” NULL์ธ ๊ฒฝ์šฐ
        • ์‚ฝ์ž…๋œ ๋…ธ๋“œ, ๋ถ€๋ชจ, ๋ถ€๋ชจ์˜ ๋ถ€๋ชจ๋ฅผ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌ
        • ์ค‘์•™ ๊ฐ’์„ ๋ถ€๋ชจ๋…ธ๋“œ๋กœ ๋งŒ๋“ค๊ณ , ๋‚˜๋จธ์ง€ ๋…ธ๋“œ๋ฅผ ์ž์‹์œผ๋กœ ๋ณ€ํ™˜ํ•จ.
        • ๋ถ€๋ชจ๋…ธ๋“œ๊ฐ€ ๋œ ๋…ธ๋“œ๋ฅผ Black, ๋‚˜๋จธ์ง€ ๋…ธ๋“œ๋ฅผ Red๋กœ coloring ํ•จ
  4. ์ด๋Ÿฌํ•œ ๊ณผ์ •์„ ํ†ตํ•ด RBT์˜ ๋™์ผํ•œ height์— ์กด์žฌํ•˜๋Š” internal node๋“ค์˜ black-height๊ฐ€ ๊ฐ™์•„์ง€๊ฒŒ ๋˜๊ณ , ์ตœ์†Œ ๊ฒฝ๋กœ์™€ ์ตœ๋Œ€๊ฒฝ๋กœ์˜ ํฌ๊ธฐ ๋น„์œจ์ด 2 ๋ฏธ๋งŒ์œผ๋กœ ์œ ์ง€๋œ๋‹ค.

์‚ญ์ œ

  1. BST์˜ ํŠน์„ฑ์„ ์œ ์ง€ํ•˜๋ฉด์„œ ์‚ฝ์ž…ํ•œ๋‹ค.
  2. ๋งŒ์•ฝ ์ง€์›Œ์ง„ ๋…ธ๋“œ๊ฐ€ black์ด๋ฉด,
    1. black-height๊ฐ€ 1 ๊ฐ์†Œํ•œ ๊ฒฝ๋กœ์— black node๊ฐ€ 1๊ฐœ ์ถ”๊ฐ€๋˜๋„๋ก rotationํ•˜๊ณ  ๋…ธ๋“œ์˜ ์ƒ‰๊น”์„ ์กฐ์ •ํ•œ๋‹ค.
  3. ์ง€์›Œ์ง„ ๋…ธ๋“œ๊ฐ€ Red๋ผ๋ฉด,
    1. ํŠน์„ฑ์ด ์œ„๋ฐฐ๋˜์ง€ ์•Š์œผ๋ฏ€๋กœ 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 ๋ฐฉ์‹ (๋ถ„๋ฆฌ์—ฐ๊ฒฐ๋ฒ•)

  1. ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ๋ฅผ ์‚ฌ์šฉํ•˜๋Š” ๋ฐฉ์‹
    • ๊ฐ๊ฐ์˜ ๋ฒ„ํ‚ท๋“ค์„ ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ๋กœ ๋งŒ๋“ค์–ด, Collision์ด ๋ฐœ์ƒํ•˜๋ฉด ํ•ด๋‹น ๋ฒ„ํ‚ท์˜ ๋ฆฌ์ŠคํŠธ์˜ ๋์— ์‚ฝ์ž…ํ•˜๋Š” ๋ฐฉ์‹
    • ์‚ฝ์ž…/์‚ญ์ œ๊ฐ€ ๊ฐ„๋‹จํ•จ. Open Address ๋ฐฉ์‹์— ๋น„ํ•ด ํ…Œ์ด๋ธ”์˜ ํ™•์žฅ์„ ๋Šฆ์ถœ ์ˆ˜ ์žˆ๋‹ค.
    • ์ž‘์€ ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ• ๋•Œ ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ ์ž์ฒด์˜ ์˜ค๋ฒ„ํ—ค๋“œ๊ฐ€ ๋ถ€๋‹ด์ด ๋œ๋‹ค๋Š” ๋‹จ์ ์ด ์žˆ์Œ.
  2. 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๊ฐ€ ์ถ”๊ฐ€๋˜๋ฉด ์ •์ง€ํ•จ.

์‹œ๊ฐ„ ๋ณต์žก๋„

  1. Edge์˜ weight๋ฅผ ๊ธฐ์ค€์œผ๋กœ sorting - O(ElogE)
  2. cycle ์ƒ์„ฑ์—ฌ๋ถ€๋ฅผ ๊ฒ€์‚ฌํ•˜๊ณ  id๋ฅผ ํ†ต์ผ โ†’ O(E + V log V)

Prim

ํ˜„์žฌ๊นŒ์ง€์˜ ๊ทธ๋ž˜ํ”„์™€ ์•„์ง ์ถ”๊ฐ€๋˜์ง€ ์•Š์€ ๋…ธ๋“œ์™€ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ๊ฐ„์„  ์ค‘์—์„œ ๊ฐ€์žฅ ์ž‘์€ ๊ฐ€์ค‘์น˜๋ฅผ ๊ฐ€์ง€๋Š” ๊ฐ„์„ ๋งŒ ์ถ”๊ฐ€ํ•จ.

์‹œ๊ฐ„๋ณต์žก๋„ : O(E logv)