Back to : ds-alg-note
Contents

Binary Search Tree

Binary Search Tree๋ž€, ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์„ฑ์งˆ์„ ๋งŒ์กฑํ•˜๋Š” ํŠธ๋ฆฌ๋ฅผ ๋งํ•ฉ๋‹ˆ๋‹ค.

  • ์ด์ง„ ํŠธ๋ฆฌ์ž…๋‹ˆ๋‹ค.

  • ํ•ญ์ƒ ์™ผ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ์˜ ๊ฐ’์€ ์ž๊ธฐ ์ž์‹ ๋ณด๋‹ค ์ž‘๊ณ , ์˜ค๋ฅธ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ์˜ ๊ฐ’์€ ์ž๊ธฐ ์ž์‹ ๋ณด๋‹ค ํฝ๋‹ˆ๋‹ค.

Binary Search Tree๋Š” ์šฐ๋ฆฌ์˜ ๋งฅ๋ฝ์—์„œ ์•ฝ๊ฐ„ ๋ฒ—์–ด๋‚˜ ์žˆ์œผ๋‚˜ ์ž๋ฃŒ๊ตฌ์กฐ์™€ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์‹œ๊ฐ„์— ๋งค์šฐ ์ค‘์š”ํ•˜๊ฒŒ ๋‹ค๋ฃน๋‹ˆ๋‹ค. ์ตํ˜€๋‘๋Š” ๊ฒƒ์„ ์ถ”์ฒœํ•˜์ง€๋งŒ, ์šฐ๋ฆฌ๊ฐ€ ์•ž์œผ๋กœ ์“ธ ์ผ์€ ์•„๋งˆ๋„ ์—†์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค. ๊ฐ„๋‹จํ•˜๊ฒŒ๋งŒ ์งš๊ณ  ๋„˜์–ด๊ฐ€๋„๋ก ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.

(i) ์‚ฝ์ž… : ์‚ฝ์ž…์€ ๊ธฐ๋ณธ์ ์œผ๋กœ, ๋ฃจํŠธ์—์„œ๋ถ€ํ„ฐ ์ถœ๋ฐœํ•ด์„œ, ์‚ฝ์ž…ํ•  ์ž๋ฆฌ๋ฅผ ์ฐพ์•„๊ฐ€๋Š” ์‹์œผ๋กœ ํ•ฉ๋‹ˆ๋‹ค. ๋Œ€์†Œ๊ด€๊ณ„์— ๋”ฐ๋ผ ์™ผ์ชฝ์œผ๋กœ ํƒ€๊ณ  ๋‚ด๋ ค๊ฐˆ์ง€, ์˜ค๋ฅธ์ชฝ์œผ๋กœ ํƒ€๊ณ  ๋‚ด๋ ค๊ฐˆ์ง€๋ฅผ ์ •ํ•œ ๋‹ค์Œ, ๋‚ด๋ ค๊ฐ€์•ผ ํ•  ์ž๋ฆฌ๊ฐ€ ๋น„์—ˆ์œผ๋ฉด ๊ทธ ์ž๋ฆฌ์— ์ง‘์–ด๋„ฃ์Šต๋‹ˆ๋‹ค.

(ii) ์‚ญ์ œ : ์‚ญ์ œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ˆ˜ํ–‰ํ•ฉ๋‹ˆ๋‹ค.

  • ์‚ญ์ œํ•  ๊ฐ’ $x$๋ฅผ ํŠธ๋ฆฌ์—์„œ ์ฐพ์Šต๋‹ˆ๋‹ค. (์‚ฝ์ž…์—์„œ ์ฐพ๋Š” ๋ฐฉ๋ฒ•๊ณผ ๋น„์Šทํ•ฉ๋‹ˆ๋‹ค.)

  • ์ด ๋…ธ๋“œ๋ฅผ, $x$์˜ ์˜ค๋ฅธ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ์—์„œ ๊ฐ€์žฅ ์ž‘์€ ๊ฐ’์ด ์žˆ๋Š” ๋…ธ๋“œ์™€ ๊ตํ™˜ํ•ฉ๋‹ˆ๋‹ค.

  • ์ด์ œ ๊ทธ ์ž๋ฆฌ์— ๊ตํ™˜๋˜์–ด ๋“ค์–ด๊ฐ„ ๋…ธ๋“œ๋ฅผ ์‚ญ์ œํ•ฉ๋‹ˆ๋‹ค.

  • ์™ผ์ชฝ ์ž์‹ ๋…ธ๋“œ๊ฐ€ ์žˆ๋‹ค๋ฉด ๊ทธ ๋…ธ๋“œ๋Š” ๊ฐ€์žฅ ์ž‘์€ ๊ฒ‚์ด ์žˆ๋Š” ๋…ธ๋“œ๊ฐ€ ์•„๋‹ˆ๋ฏ€๋กœ ๋ถˆ๊ฐ€๋Šฅํ•˜๊ณ , ๋”ฐ๋ผ์„œ ๋…ธ๋“œ์˜ ์ž์‹์ด 2๊ฐœ์ผ ์ˆ˜๋Š” ์—†์Šต๋‹ˆ๋‹ค. ์ž์‹์ด 1๊ฐœ๋ผ๋ฉด, ์‚ญ์ œ๋œ ๋…ธ๋“œ ์ž๋ฆฌ๋กœ ๋Œ์–ด์˜ฌ๋ฆฝ๋‹ˆ๋‹ค.

  • ์ž์‹์ด ์—†๋‹ค๋ฉด ๊ทธ๋ƒฅ ๋„˜์–ด๊ฐ€๋„ ๋ฉ๋‹ˆ๋‹ค.

๊ฒฐ๊ตญ, ๋‘ ์—ฐ์‚ฐ ๋ชจ๋‘ ๊ฒ€์ƒ‰ ์—ฐ์‚ฐ์„ ์ด์šฉํ•˜์—ฌ ์ด๋ฃจ์–ด์ง‘๋‹ˆ๋‹ค.
์ด์ œ, ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ์ƒ๊ฐํ•ด ๋ด…์‹œ๋‹ค. ์‚ฝ์ž… ์—ฐ์‚ฐ์˜ ๊ฒฝ์šฐ ๊ฒ€์ƒ‰ ์—ฐ์‚ฐ๊ณผ ๊ฑฐ์˜ ๋™์ผํ•˜๋ฏ€๋กœ, ํŠธ๋ฆฌ์˜ ๋†’์ด $h$์— ๋Œ€ํ•ด $O(h)$ ์‹œ๊ฐ„์ด ๋“ค๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. ์‚ญ์ œ์˜ ๊ฒฝ์šฐ, ๊ฒ€์ƒ‰ + ์˜ค๋ฅธ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ์˜ ๊ฐ€์žฅ ์ž‘์€ ๊ฐ’ ์ฐพ๊ธฐ์˜ ๋‘ ๋ฒˆ์ธ๋ฐ, ๋‘˜ ๋ชจ๋‘ ์‚ฌ์‹ค์ƒ ๊ฒ€์ƒ‰๊ณผ ๋น„์Šทํ•œ ์—ฐ์‚ฐ์ด๋ฏ€๋กœ $O(h)$ ์‹œ๊ฐ„์ž…๋‹ˆ๋‹ค. ๊ฒฐ๊ตญ ์‚ฝ์ž…๊ณผ ์‚ญ์ œ ๋ชจ๋‘ $O(h)$ ์‹œ๊ฐ„์ด ๋“œ๋Š” ์—ฐ์‚ฐ์ž…๋‹ˆ๋‹ค. ๊ทธ๋Ÿฐ๋ฐ, ์ด์ง„ ํŠธ๋ฆฌ์˜ ๊ฒฝ์šฐ ์ตœ์•…์˜ ์ƒํ™ฉ์—์„œ $h$๊ฐ€ $n$๊นŒ์ง€ ์ปค์งˆ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. (ํ•œ ์ค„๋กœ ์ญ‰ ๋Š˜์–ด์„œ ์žˆ๋Š” ๊ฒฝ์šฐ)
์šฐ๋ฆฌ๋Š” ๋ณ„๋กœ ์ž์„ธํžˆ ๋‹ค๋ฃจ์ง€๋Š” ์•Š๊ฒ ์ง€๋งŒ, ์ด๋Ÿฌํ•œ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•œ ๋ฐฉ๋ฒ•์„ ์ž ๊น๋งŒ ์ƒ๊ฐํ•ด ๋ด…์‹œ๋‹ค. Quick select๋•Œ๋ž‘ ์•ฝ๊ฐ„ ๋น„์Šทํ•œ๋ฐ, โ€œ์•ฝ๊ฐ„์˜ ์‹œ๊ฐ„์„ ์ง€๋ถˆํ•ด์„œโ€, โ€œ๋„ˆ๋ฌด ๋‚˜์œ ์ƒํ™ฉ์ด ๋ฒŒ์–ด์ง€์ง€ ์•Š๊ฒŒโ€ ๋งŒ๋“ค๋ฉด ๋ฉ๋‹ˆ๋‹ค. ์ด๊ฒƒ์„ Balanced Binary Search Tree (BBST) ๋ผ๊ณ  ๋ถ€๋ฅด๊ณ , ์ด๋ฅผ ๊ตฌํ˜„ํ•˜๋Š” ๋‹ค์–‘ํ•œ ๋ฐฉ๋ฒ•์ด ์žˆ์Šต๋‹ˆ๋‹ค. ์ž์„ธํ•œ ๋‚ด์šฉ์€ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ˆ˜์—…์—์„œ ๋‹ค๋ฃน๋‹ˆ๋‹ค. ์ถ”๊ฐ€ ์ž๋ฃŒ๋ฅผ Additional ii์— ์ผ๋ถ€ ์ œ์‹œํ•ด ๋‘์—ˆ์Šต๋‹ˆ๋‹ค.

STL set, map

C++์˜ ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ์—๋Š” ๋งค์šฐ ํŽธํ•œ set ๊ณผ map์ด ์žˆ์Šต๋‹ˆ๋‹ค. ์ด set๊ณผ map์€ Balanced Binary Search Tree์˜ ์ผ์ข…์ธ Red-Black Tree๋กœ ๊ตฌํ˜„๋˜์–ด ์žˆ๊ธฐ ๋•Œ๋ฌธ์—, BBST๋ฅผ ์‹ค์ œ๋กœ ๊ตฌํ˜„ํ•ด์„œ ์“ธ ์ผ์€ ๋ณดํ†ต ์—†์Šต๋‹ˆ๋‹ค. ์ด ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ์˜ ์‚ฌ์šฉ๋ฒ•์„ ๋ฐ˜๋“œ์‹œ ์ตํžˆ๊ธธ ๊ถŒํ•ฉ๋‹ˆ๋‹ค.
์˜ˆ์‹œ ์ฝ”๋“œ ๋ณด๊ธฐ : BOJ 14425 ๋ฌธ์ž์—ด ์ง‘ํ•ฉ
set, map, multiset, multimap์€ ํ™œ์šฉ๋„๊ฐ€ ๋งค์šฐ ๋†’์Šต๋‹ˆ๋‹ค. ์ฐธ๊ณ ๋กœ, priority queue๋กœ ํ•  ์ˆ˜ ์žˆ๋Š” ๋ชจ๋“  ์—ฐ์‚ฐ์€ multiset์œผ๋กœ ๋˜‘๊ฐ™์ด ํ•  ์ˆ˜ ์žˆ๊ณ , ์‹œ๊ฐ„ ๋ณต์žก๋„๋„ $\order{\log n}$์œผ๋กœ ๊ฐ™์Šต๋‹ˆ๋‹ค. ๊ทธ๋ ‡๋‹ค๊ณ  ํ•ด์„œ ๋‘ ์ฝ”๋“œ์˜ ์ˆ˜ํ–‰ ์‹œ๊ฐ„์ด ๊ฐ™๊ฑฐ๋‚˜ ๋น„์Šทํ•  ๊ฒƒ์œผ๋กœ ๊ธฐ๋Œ€ํ•ด์„œ๋Š” ์•ˆ ๋ฉ๋‹ˆ๋‹ค. ํ•ญ์ƒ, ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” ์ค‘์š”ํ•˜์ง€๋งŒ, ๊ทธ๋ ‡๋‹ค๊ณ  ํ•ด์„œ ์ „๋ถ€๋Š” ์•„๋‹™๋‹ˆ๋‹ค.

Disjoint Set

์ด๋ฒˆ section์—์„œ ์šฐ๋ฆฌ์˜ ๋ชฉํ‘œ๋Š”, ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋‘ ๊ธฐ๋Šฅ์„ ๊ฐ–๋Š” ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ๋งŒ๋“œ๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค.

(i) Union(a, b) : a๊ฐ€ ๋“ค์–ด ์žˆ๋Š” ์ง‘ํ•ฉ๊ณผ b๊ฐ€ ๋“ค์–ด ์žˆ๋Š” ์ง‘ํ•ฉ์„ ํ•ฉ์น˜๋Š” ์—ฐ์‚ฐ.

(ii) Find(x) : x๊ฐ€ ๋“ค์–ด ์žˆ๋Š” ์ง‘ํ•ฉ์˜ ๋ฒˆํ˜ธ๋ฅผ ํ™•์ธํ•œ๋‹ค. ์ฆ‰, Find(x) ์™€ Find(y) ๋ฅผ ํ†ตํ•ด ๋‘ ์›์†Œ๊ฐ€ ๊ฐ™์€ ์ง‘ํ•ฉ์— ์†Œ์†๋˜์–ด ์žˆ๋Š”์ง€ ํ™•์ธํ•˜๋Š” ์ž‘์—…์ด ๋ชฉํ‘œ.

์˜ˆ๋ฅผ ๋“ค์–ด, 1๋ถ€ํ„ฐ 5๊นŒ์ง€์˜ ์ˆซ์ž๊ฐ€ ์žˆ๋‹ค๊ณ  ํ•  ๋•Œ, Union(1, 2), Union(3, 4) ๋ฅผ ํ•˜๊ณ  ๋‚˜๋ฉด $\Set{1, 2}, \Set{3, 4}, \Set{5}$ ๊ฐ€ ๋ฉ๋‹ˆ๋‹ค. ์ด๋•Œ Find(3) ๊ณผ Find(4)๋Š” ๊ฐ™์•„์•ผ ํ•˜๊ณ , Find(1)๊ณผ๋Š” ๋‹ฌ๋ผ์•ผ ํ•ฉ๋‹ˆ๋‹ค. ๋˜ํ•œ, Union(1, 4) ๋‚˜ Union(2, 3) ๋“ฑ์€ ๋ชจ๋‘ $\Set{1, 2, 3, 4}, \Set{5}$ ๋กœ ๋งŒ๋“œ๋Š” ๊ณผ์ •์„ ์ˆ˜ํ–‰ํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.

Naive Approach

์‰ฌ์šด ๋ฐฉ๋ฒ•์œผ๋กœ, Linked List๋ฅผ ์‚ฌ์šฉํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ์˜ˆ๋กœ ๋“ค ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. $n$๊ฐœ์˜ ์ˆซ์ž๊ฐ€ ์žˆ๊ณ , ์ด๋“ค์— ์ ๋‹นํžˆ operation์„ ์ˆ˜ํ–‰ํ•˜๋ ค๊ณ  ํ•œ๋‹ค๊ณ  ํ•ฉ์‹œ๋‹ค. ๊ฐ๊ฐ์˜ ์›์†Œ๊ฐ€ $p$, $q$๊ฐœ์ธ ์ง‘ํ•ฉ์„ ํ•ฉ์น˜๋Š” ๋ฐ ๋“œ๋Š” ์‹œ๊ฐ„์€ ๊ตฌํ˜„์— ๋”ฐ๋ผ ๋‹ค๋ฅด์ง€๋งŒ, ํšจ์œจ์„ฑ์„ ์œ„ํ•ด ์ž‘์€ ๋ฆฌ์ŠคํŠธ๋ฅผ ํฐ ๋ฆฌ์ŠคํŠธ์— ํ•ฉ์น˜๋Š” ์‹์œผ๋กœ ์ž‘์—…ํ•˜๋ฉด $O(\min(p, q))$ ์ด์ง€๋งŒ ์ด๋Š” ์ตœ๋Œ€ $n/2$ ๊นŒ์ง€์ด๊ณ , ๊ฒฐ๊ตญ ํ•œ๋ฒˆ์˜ Union์— $O(n)$์ด ๊ฑธ๋ฆด ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋˜ํ•œ, Find์˜ ๊ฒฝ์šฐ ๋ชจ๋“  element๋ฅผ ๋’ค์ง€๋ฉด์„œ ์ด ๋ฆฌ์ŠคํŠธ์— ์†Œ์†๋˜์–ด ์žˆ๋Š”์ง€ ์ฐพ๋Š” ๋ฐฉ๋ฒ•๋ฐ–์— ์—†์œผ๋ฏ€๋กœ $O(n)$์ด ๊ฑธ๋ฆฌ๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. ๋ฌผ๋ก , ์ถ”๊ฐ€์ ์ธ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์“ฐ๋ฉด, ๋งค๋ฒˆ ๊ฐ ์›์†Œ๊ฐ€ ์ž์‹ ์ด ์†Œ์†๋œ ๋ฆฌ์ŠคํŠธ์˜ ํ—ค๋“œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋Š” ํฌ์ธํ„ฐ๋ฅผ ๊ด€๋ฆฌํ•˜๋Š” ๋“ฑ ๋ฐฉ๋ฒ•์„ ์“ธ ์ˆ˜๋Š” ์žˆ์ง€๋งŒ, ์ด๊ฒƒ๋„ Union์€ ๋นจ๋ฆฌ ํ•  ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.

Using Trees

์ƒ๊ฐ์„ ๋‹ฌ๋ฆฌํ•˜์—ฌ, ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ƒ๊ฐํ•ด ๋ด…์‹œ๋‹ค. ๊ฐ ์ง‘ํ•ฉ์€ ํ•˜๋‚˜์˜ ํŠธ๋ฆฌ๋กœ ๋‚˜ํƒ€๋‚ผ ๊ฒƒ์ด๊ณ , ๊ฐ ์›์†Œ๋งˆ๋‹ค ์ž์‹ ์˜ ๋ถ€๋ชจ ๋…ธ๋“œ์˜ ๋ฒˆํ˜ธ๋งŒ ์ ์–ด ๋†“์Šต๋‹ˆ๋‹ค. ์ฆ‰, ๊ฐ ์›์†Œ์— ๋Œ€ํ•ด par(x)๋ฅผ ํ•ญ์ƒ ๊ด€๋ฆฌํ•œ๋‹ค๊ณ  ์ƒ๊ฐํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. ์ด๋•Œ, Find(x)๋Š” ์•ฝ๊ฐ„ ์ƒ๊ฐ์„ ๋ฐ”๊ฟ”์„œ, ์ž์‹ ์ด ์†Œ์†๋œ ํŠธ๋ฆฌ์˜ ๋ฃจํŠธ ๋…ธ๋“œ๋ฅผ ์ฐพ๋Š” ์—ฐ์‚ฐ์ด๋ผ๊ณ  ์ƒ๊ฐํ•ฉ๋‹ˆ๋‹ค. (๋ถ€๋ชจ๊ฐ€ ์—†๋Š” ๋ฃจํŠธ ๋…ธ๋“œ์˜ ๋ถ€๋ชจ๋Š” ์ž๊ธฐ ์ž์‹ )
๊ทธ๋ ‡๋‹ค๋ฉด, Union์„ ํ•  ๋•Œ ๊ตณ์ด ๋ชจ๋“  ๋…ธ๋“œ์˜ par์„ ๋ฐ”๊ฟ”์•ผ ํ• ๊นŒ์š”? ํŠธ๋ฆฌ A์™€ ํŠธ๋ฆฌ B๋ฅผ ํ•ฉ์น˜๋ ค๊ณ  ํ•œ๋‹ค๋ฉด, A์˜ ๋ฃจํŠธ๋ฅผ B์˜ ๋ฃจํŠธ ๋ฐ‘์— ๋‹ฌ์•„ ์ฃผ๊ธฐ๋งŒ ํ•˜๋ฉด (์ฆ‰, par[root of A] = root of B) ํ•œ ๋ฒˆ์— ํŠธ๋ฆฌ A ์ „์ฒด๋ฅผ ํŠธ๋ฆฌ B์— ๋‹ฌ์•„ ๋†“์€ ํ˜•ํƒœ๊ฐ€ ๋ฉ๋‹ˆ๋‹ค. ๋‘ ํŠธ๋ฆฌ (์ง‘ํ•ฉ)์˜ Union์ด ๋๋‚ฌ์Šต๋‹ˆ๋‹ค!
์ด ๋ฐฉ๋ฒ•์„ ์ƒ๊ฐํ•ด ๋ณด๋ฉด, Union(x, y) ์—ฐ์‚ฐ์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” ๊ฒฐ๊ตญ Find(x)์™€ Find(y)์— ์˜ํ•ด ๊ฒฐ์ •๋ฉ๋‹ˆ๋‹ค. Find(x)ํ•˜์—ฌ, ๊ทธ ์ฐพ์€ ๋ฃจํŠธ๋ฅผ Find(y)์— ๋‹ฌ์•„ ์ฃผ๋Š” ์—ฐ์‚ฐ์ด $\order{1}$์ด๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค. ๊ทธ๋Ÿฐ๋ฐ, Find ์—ฐ์‚ฐ์€ ๊ทธ ํŠธ๋ฆฌ์˜ ๋†’์ด์— ์˜ํ•ด ๊ฒฐ์ •๋˜๊ณ , ์ตœ์•…์˜ ๊ฒฝ์šฐ ํŠธ๋ฆฌ๊ฐ€ ๋ฃจํŠธ ๋ฐ‘์œผ๋กœ ํ•œ ์ค„๋กœ ์ญ‰ ๋‹ฌ๋ฆด ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ $O(h) = O(n)$ ์ž…๋‹ˆ๋‹ค. ๊ทธ๋Ÿฌ๋ฉด ๋ณ„๋กœ ๋นจ๋ผ์ง„ ๊ฒƒ์ด ์—†์Šต๋‹ˆ๋‹ค.

Optimizations

์œ„์™€ ๊ฐ™์€ ์ฒ˜์ฐธํ•œ ์ƒํ™ฉ์„ ๋ง‰๊ธฐ ์œ„ํ•ด, ์šฐ๋ฆฌ๋Š” ํฌ๊ฒŒ ์„ธ ๊ฐ€์ง€๋ฅผ ์ƒ๊ฐํ•ฉ๋‹ˆ๋‹ค.

  • Union by Rank : ๊ฐ ํŠธ๋ฆฌ๋งˆ๋‹ค, ํ•ญ์ƒ ํŠธ๋ฆฌ์˜ ๋†’์ด1๋ฅผ ๋”ฐ๋กœ ๊ด€๋ฆฌํ•ฉ๋‹ˆ๋‹ค. ์ด๋•Œ, Union ์—ฐ์‚ฐ์—์„œ ํŠธ๋ฆฌ๋ฅผ ๋งค๋‹ฌ ๋•Œ, ๋ฐ˜๋“œ์‹œ ๋†’์ด๊ฐ€ ๋‚ฎ์€ ํŠธ๋ฆฌ๋ฅผ ๋†’์ด๊ฐ€ ๋†’์€ ํŠธ๋ฆฌ์— ๋งค๋‹ฌ๋„๋ก ๊ฐ•์ œํ•ฉ๋‹ˆ๋‹ค. ์ด๋ ‡๊ฒŒ ํ•˜๋ฉด, ํŠธ๋ฆฌ์˜ ๋†’์ด๊ฐ€ ์ ˆ๋Œ€ $\log n$ ์ด์ƒ์œผ๋กœ ์ปค์ง€์ง€ ์•Š์Œ์„ ๋ณด์ผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. (Additional 3)

  • Union by Size : ๊ฐ ํŠธ๋ฆฌ๋งˆ๋‹ค, ํŠธ๋ฆฌ์˜ ํฌ๊ธฐ (๋…ธ๋“œ์˜ ๊ฐœ์ˆ˜) ๋ฅผ ๊ด€๋ฆฌํ•˜๊ณ , ์ž‘์€ ํŠธ๋ฆฌ๋ฅผ ํฐ ํŠธ๋ฆฌ์— ๋ถ™์ด๋„๋ก ๊ฐ•์ œํ•ฉ๋‹ˆ๋‹ค. ์—ญ์‹œ Union by Rank์™€ ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ, ํŠธ๋ฆฌ์˜ ๋†’์ด๊ฐ€ ์ ˆ๋Œ€ $\log n$ ์ด์ƒ์œผ๋กœ ์ปค์ง€์ง€ ์•Š์Œ์„ ๋ณด์ผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. (Additional 4)

  • Path Compression : ๋งค๋ฒˆ Find ์—ฐ์‚ฐ์„ ํ•˜๋‹ค ๋ณด๋ฉด, $x$๊ฐ€ ํฌํ•จ๋œ ํŠธ๋ฆฌ์˜ ๋ฃจํŠธ๋ฅผ ์•Œ๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. ์ด๋•Œ, Heuristic์ ์ธ ์ƒ๊ฐ์œผ๋กœ, ๋‚ด๊ฐ€ 3-4-1-5-2-6์˜ ๊ณผ์ •์œผ๋กœ 3์—์„œ๋ถ€ํ„ฐ parent๋ฅผ ํƒ€๊ณ  ์˜ฌ๋ผ๊ฐ€ 6์— ๋„๋‹ฌํ–ˆ๋‹ค๋ฉด, ์ด ํŠธ๋ฆฌ๋ฅผ ๋ชจ๋‘ ๋œฏ์–ด๋ฒ„๋ฆฌ๊ณ  3, 4, 1, 5, 2๋ฅผ ์ „๋ถ€ 6์— ๊ทธ๋Œ€๋กœ ๋งค๋‹ฌ์•„๋„ ๋ฉ๋‹ˆ๋‹ค. ์ด ์—ฐ์‚ฐ์€ ํŠธ๋ฆฌ์˜ ๋†’์ด๋ฅผ ์ค„์—ฌ ์ค„ ๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค.

์‹ค์ œ ๊ตฌํ˜„์—์„œ ์‚ฌ์šฉํ•˜๋Š” ๋ฐฉ๋ฒ•์€ [Union by Rank or Size] + [Path Compression] ์ž…๋‹ˆ๋‹ค. ์ดํ•˜, [Union Rule]๊ณผ [Path Comp] ๋ผ๊ณ  ์ค„์ด๊ฒ ์Šต๋‹ˆ๋‹ค.

Time Complexity

Additional 3๊ณผ 4์—์„œ ๋‹ค๋ฃฌ ๋ฐ”์™€ ๊ฐ™์ด, [Union Rule] ์€ ํ•œ๋ฒˆ ์—ฐ์‚ฐ์— ๋Œ€๋žต $\order{\log n}$ ์ •๋„๊ฐ€ ๊ฑธ๋ฆผ์„ ๋ณด์žฅํ•ฉ๋‹ˆ๋‹ค. Union Rule ์—†์ด Path Comp ๋งŒ์œผ๋กœ๋Š”, ์ฒซ ๋ช‡๋ฒˆ์˜ Path comp๋Š” ๋ณ„๋กœ ํšจ์œจ์ ์ด์ง€ ๋ชปํ•˜์ง€๋งŒ ๋‚˜์ค‘์˜ case๋“ค์ด ํšจ์œจ์ ์ด๊ธฐ ๋•Œ๋ฌธ์—, ์ƒ๋‹นํžˆ ์ข‹์€ Bound๋ฅผ ์ฐพ์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.2 ๋‘ ๊ฐ€์ง€๋ฅผ ๋ชจ๋‘ ์‚ฌ์šฉํ•˜๋Š”, ํšจ์œจ์ ์ธ ๊ตฌํ˜„์˜ ๊ฒฝ์šฐ, Find ์—ฐ์‚ฐ์ด ํ‰๊ท ์ ์œผ๋กœ ๋Œ€๋‹จํžˆ ๋น ๋ฅด๊ฒŒ ์ˆ˜ํ–‰๋ฉ๋‹ˆ๋‹ค. ์ด๋•Œ, ์ด ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ $\alpha(n)$ ์ด๋ผ๋Š” ํ•จ์ˆ˜๋กœ ์”๋‹ˆ๋‹ค. ์ด ํ•จ์ˆ˜๋Š” Inverse Ackermann ํ•จ์ˆ˜๋ผ๋Š” ๊ฒƒ์ธ๋ฐ, ์šฐ๋ฆฌ๊ฐ€ ์ƒ์ƒํ•  ์ˆ˜ ์žˆ๋Š” ๋Œ€๋ถ€๋ถ„์˜ ํ•จ์ˆ˜๋ณด๋‹ค ์ž‘์€ ๊ฐ’์„ ๊ฐ–์Šต๋‹ˆ๋‹ค. ์ธ๊ฐ„์ด ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ๋ชจ๋‘ ํ•ฉ์ณ๋„, ๊ทธ ์•ˆ์— ๋“ค์–ด๊ฐ€๋Š” $n$์˜ ๊ฐ’์— ๋Œ€ํ•ด $\alpha(n) < 5$์ด๊ธฐ ๋•Œ๋ฌธ์— ์šฐ๋ฆฌ๋Š” ์ด ํ•จ์ˆ˜๋ฅผ ์‚ฌ์‹ค์ƒ ์ƒ์ˆ˜๋ผ๊ณ  ์ƒ๊ฐํ•ด๋„ ํฐ ๋ฌธ์ œ๋Š” ์—†์Šต๋‹ˆ๋‹ค.

Additional Topics / Problems

  1. Balanced Binary Search Tree์˜ ์˜ˆ์‹œ๋กœ, AVL-Tree, Red-Black-Tree, B-Tree์™€ ๊ทธ ํŠน์ˆ˜ํ•œ ํ˜•ํƒœ์ธ 2-3-4 Tree๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด ์ž๋ฃŒ๊ตฌ์กฐ๋“ค์€ ํฌ๊ฒŒ ๊ฒ€์ƒ‰๊ณผ ๊ฒ€์ƒ‰ ๊ธฐ๋ฐ˜ ์—ฐ์‚ฐ (์‚ฝ์ž…, ์‚ญ์ œ, ๊ฒ€์ƒ‰)์„ $\order{\log n}$ ์— ์ˆ˜ํ–‰ํ•ฉ๋‹ˆ๋‹ค. ๊ทธ ๋ฐ–์—๋„, ์ผ๋ฐ˜์ ์ธ ์ด๋Ÿฐ ํŠธ๋ฆฌ๋กœ๋Š” ์ ˆ๋Œ€ ์ˆ˜ํ–‰ํ•  ์ˆ˜ ์—†์–ด ๋ณด์ด๋Š” ๊ธฐ๊ดดํ•œ ์—ฐ์‚ฐ์„ ์ œ๊ณตํ•˜๋Š” ์ž๋ฃŒ๊ตฌ์กฐ๋“ค์ด ์กด์žฌํ•ฉ๋‹ˆ๋‹ค.3 ์šฐ๋ฆฌ๋Š” ๋‹ค๋ฃจ์ง€ ์•Š์„ ์˜ˆ์ •์ด๊ณ  ์‚ฌ์‹ค ์ €๋„ ์ฝ”๋”ฉํ•  ์ค„ ๋ชจ๋ฅด์ง€๋งŒ โ€˜๋ฃจํŠธ๋ฅผ ๋ฐ”๊พธ๋Š” ์—ฐ์‚ฐโ€™์„ Amortized $\order{\log n}$์— ํ•ด ์ค€๋‹ค๊ฑฐ๋‚˜ ํ•˜๋Š”... ๋ญ ๊ทธ๋Ÿฐ ๊ฒƒ๋„ ์žˆ๋‹ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค (?)

  2. Union by rank๋งŒ ์‚ฌ์šฉํ•˜์˜€์„ ๋•Œ, ํŠธ๋ฆฌ์˜ ๋†’์ด๊ฐ€ $O(\log n)$ ์ด์ƒ์œผ๋กœ ์ฆ๊ฐ€ํ•˜์ง€ ์•Š๋Š”๋‹ค๋Š” ์‚ฌ์‹ค์„ ๋‚ฉ๋“ํ•˜์„ธ์š”. ํŠธ๋ฆฌ์˜ ๋†’์ด๊ฐ€ ํ•ฉ์น˜๋ ค๋Š” ํŠธ๋ฆฌ์˜ ๋†’์ด $h_1, h_2$๋ณด๋‹ค 1๋งŒํผ ์ฆ๊ฐ€ํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š”, ์–‘์ชฝ์˜ ๋†’์ด๊ฐ€ ๊ฐ™์•„์•ผ ํ•˜๋ฉฐ, ๊ทธ๋Ÿฌ๊ธฐ ์œ„ํ•ด์„œ๋Š” ๊ทธ ํŠธ๋ฆฌ์˜ ๋…ธ๋“œ ์ˆ˜๋Š” ์ ์–ด๋„ $2h_1$๊ฐœ๊ฐ€ ๋˜์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ๊ท€๋‚ฉ๋ฒ•์„ ํ†ตํ•ด, ๋†’์ด๊ฐ€ $h$์ธ ํŠธ๋ฆฌ๊ฐ€ ๋˜๋ ค๋ฉด $2^h$๊ฐœ ์ •๋„์˜ ๋…ธ๋“œ๊ฐ€ ํ•„์š”ํ•จ์„ ๋ณด์ด์„ธ์š”.

  3. Union by size์— ๋Œ€ํ•ด์„œ, ์œ„ ๋ฌธ์ œ์™€ ๊ฐ™์€ ๋‚ด์šฉ์„ ๋ณด์ด์„ธ์š”.

  4. 2, 3์—์„œ ์ œ์‹œ๋œ ์•„์ด๋””์–ด์˜ ํ•ต์‹ฌ์„ ์š”์•ฝํ•˜๋ฉด, โ€˜๋งค๋ฒˆ ํฐ ์ชฝ์— ์ž‘์€ ์ชฝ์„ ๋ถ™์ด๋„๋ก ๊ฐ•์ œํ•˜๋ฉด, ํ•œ๋ฒˆ ํ•ฉ์น˜๋Š” ์—ฐ์‚ฐ์„ ํ•  ๋•Œ ๊ฒฐ๊ณผ๋ฌผ์˜ ํฌ๊ธฐ๋Š” ์ ์–ด๋„ ์ž‘์€ ์ชฝ์˜ 2๋ฐฐ๊ฐ€ ๋œ๋‹คโ€™ ๋ผ๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค. ์ด ์›์น™์€ ๋‹น์—ฐํ•ด ๋ณด์ด์ง€๋งŒ, Tree DP ๋“ฑ์—์„œ ๋ณต์žก๋„๋ฅผ ์ค„์ด๋Š” ํ•ต์‹ฌ์ ์ธ ํŠธ๋ฆญ ์ค‘ ํ•˜๋‚˜์ž…๋‹ˆ๋‹ค. ๊ฐ„๋‹จํ•œ ์ œ์•ฝ์„ ํ†ตํ•ด $O(n^2)$ ์‹œ๊ฐ„ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ $O(n \log n)$ ๋˜๋Š” $O(n \log^2 n)$ ์œผ๋กœ ์ค„์ผ ์ˆ˜ ์žˆ๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค.

  5. Wikipedia์—๋Š” Union Rule + Path Comp๋ฅผ ์ˆ˜ํ–‰ํ•  ๋•Œ, ์‹œ๊ฐ„ ๋ณต์žก๋„๊ฐ€ $O(\log^* n)$ ์ž„์„ ๋ณด์ด๋Š” ์ฆ๋ช…์ด ์žˆ์Šต๋‹ˆ๋‹ค. $\log^* n$ ์ด๋ผ๋Š” ํ•จ์ˆ˜๋Š”, ๋Œ€๋žต $\log \log \log \dots \log n$์˜ ๊ฐ’์ด 1๋ณด๋‹ค ์ž‘์•„์ง€๊ธฐ ์œ„ํ•ด ํ•„์š”ํ•œ $\log$์˜ ๊ฐœ์ˆ˜์ž…๋‹ˆ๋‹ค. ์ด ํ•จ์ˆ˜๋„ ๋‹น์—ฐํžˆ ๋งค์šฐ ๋Š๋ฆฌ๊ฒŒ ์ฆ๊ฐ€ํ•˜๊ธฐ ๋•Œ๋ฌธ์—, ์‹ค์šฉ์ ์œผ๋กœ๋Š” 5 ์ดํ•˜์˜ ๊ฐ’์„ ๊ฐ€์ง„๋‹ค๊ณ  ๊ฐ€์ •ํ•ด๋„ ๋ฉ๋‹ˆ๋‹ค. CLRS ์ฑ…์˜ chapter 21์—๋Š” Inverse ackermann ํ•จ์ˆ˜์— ๊ด€ํ•œ ์ฆ๋ช…์ด ์ˆ˜๋ก๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค. ๊ด€์‹ฌ์ด ์žˆ๋‹ค๋ฉด ์ฐธ๊ณ ํ•˜์„ธ์š”. ์šฐ๋ฆฌ๊ฐ€ ๋‹ค๋ฃจ๊ธฐ์—๋Š” ํ•„์š” ์ด์ƒ์œผ๋กœ ๋ณต์žกํ•˜๊ณ , ๋ณ„๋กœ ์ค‘์š”ํ•˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค. ๋‹ค๋งŒ ๋‘ ์ฆ๋ช… ๋ชจ๋‘ ์ƒ๋‹นํžˆ Elegantํ•ฉ๋‹ˆ๋‹ค.

  6. ($\star$) Union Find์„ ๊ทธ๋ž˜ํ”„์˜ ์šฉ์–ด๋กœ ์“ฐ๋ฉด, ๋…ธ๋“œ๋“ค์„ ์ž‡๋Š” ์—ฐ์‚ฐ๊ณผ ๋‘ ๋…ธ๋“œ๊ฐ€ ์„œ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š”์ง€ ๋ฌป๋Š” ์—ฐ์‚ฐ์ด๋ผ๊ณ  ์ƒ๊ฐํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด๋ฅผ Incremental connectivity๋ผ๊ณ  ๋ถ€๋ฆ…๋‹ˆ๋‹ค. ๋ฐ˜๋Œ€๋กœ, ๊ฐ„์„ ์ด ์ฒ˜์Œ์—๋Š” ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๊ณ , ์‚ญ์ œ๋˜๋Š” ๊ฒฝ์šฐ์˜ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์„๊นŒ์š”? ์ฆ‰, union-find์˜ union ๋Œ€์‹  disconnect(u, v) ์—ฐ์‚ฐ์„ ๋น ๋ฅด๊ฒŒ ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ์„๊นŒ์š”? ์ด ๋ฌธ์ œ๋Š” incremental๋ณด๋‹ค ํ›จ์”ฌ ์–ด๋ ต์Šต๋‹ˆ๋‹ค. ์ฒ˜์Œ์— ์—ฐ๊ฒฐ๋œ ์ƒํƒœ๊ฐ€ Tree์ธ ๊ฒฝ์šฐ, 1981๋…„์— Evan๊ณผ Shiloach๊ฐ€ $O(n \log n)$ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„, 1997๋…„์— Alstrup ๋“ฑ์ด $O(n + m)$ ์— ๊ฐ€๋Šฅํ•จ์„ ๋ณด์˜€์Šต๋‹ˆ๋‹ค. Planar graph์— ๋Œ€ํ•ด์„œ ์„ ํ˜• ์‹œ๊ฐ„ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์ œ์‹œ๋œ ๊ฒƒ์€ 2015๋…„์˜ ์ผ์ž…๋‹ˆ๋‹ค.

  7. ($\star\star$) ์ด์ œ, ๋‘ ๋ฌธ์ œ๋ฅผ ํ•ฉ์ณ ๋ด…์‹œ๋‹ค. connect์™€ disconnect์—ฐ์‚ฐ์„ ๋ชจ๋‘ ์ง€์›ํ•  ์ˆ˜ ์žˆ์„๊นŒ์š”? ์ด ๋ฌธ์ œ๋Š” ๊ทธ๋ž˜ํ”„๊ฐ€ ๋ชจ๋“  ์ƒํ™ฉ์—์„œ Forest (์„œ๋กœ ์—ฐ๊ฒฐ๋˜์ง€ ์•Š์€ ํŠธ๋ฆฌ๋“ค) ์ž„์ด ๋ณด์žฅ๋˜๋Š” ๊ฒฝ์šฐ $O(n \log n)$ ์—, ์ผ๋ฐ˜ ๊ทธ๋ž˜ํ”„์—์„œ๋„ ์ฟผ๋ฆฌ๋‹น poly-logarithmic ์‹œ๊ฐ„์— ํ’€ ์ˆ˜ ์žˆ์Œ์ด ์•Œ๋ ค์ ธ ์žˆ์Šต๋‹ˆ๋‹ค.

Programming Practice

  1. C++์˜ STL multiset ๋“ฑ์„ ์‚ฌ์šฉํ•˜์—ฌ, BOJ 7662๋ฒˆ์„ ํ•ด๊ฒฐํ•ด ๋ณด์„ธ์š”.

  2. ์ฒ˜์Œ์œผ๋กœ STL์—์„œ ์•„์˜ˆ ์ง€์›ํ•˜์ง€ ์•Š๋Š” ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ๊ตฌํ˜„ํ•ด ๋ณด๊ฒŒ ๋˜์—ˆ์Šต๋‹ˆ๋‹ค. Disjoint set ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ๊ตฌํ˜„ํ•ด ๋ณด๊ณ , ๊ตฌํ˜„์ฒด๋ฅผ BOJ 1717๋ฒˆ์— ์ œ์ถœํ•ด์„œ ํ™•์ธํ•ด ๋ณด์„ธ์š”. C++๋กœ ๊ตฌํ˜„ํ•œ ์˜ฌ๋ฐ”๋ฅธ ๊ตฌํ˜„์ฒด๋Š” 100ms ๋ฏธ๋งŒ์œผ๋กœ ๋™์ž‘ํ•ฉ๋‹ˆ๋‹ค. ๋งŒ์•ฝ ์ƒ๊ฐ๋ณด๋‹ค ์‹œ๊ฐ„์ด ์˜ค๋ž˜ ๊ฑธ๋ฆฐ๋‹ค๋ฉด, ๋‹ค๋ฅธ ์‚ฌ๋žŒ์˜ ๋น ๋ฅธ ๊ตฌํ˜„์„ ์ฐธ๊ณ ํ•ด์„œ ์–ด๋–ค ๋ถ€๋ถ„์„ ๊ฐœ์„ ํ•  ์ˆ˜ ์žˆ์„์ง€ ์•Œ์•„๋ณด์„ธ์š”.

  1. ์—„๋ฐ€ํ•˜๊ฒŒ๋Š” ๋†’์ด์™€๋Š” ์•ฝ๊ฐ„ ๋‹ค๋ฅธ๋ฐ, ๋Œ€์ถฉ ๋†’์ด๋ผ๊ณ  ์ƒ๊ฐํ•ด๋„ ๋…ผ๋ฆฌ์ง„ํ–‰์—๋Š” ๋ฌธ์ œ๊ฐ€ ์—†์Šต๋‹ˆ๋‹คย โ†ฉ

  2. ์ƒ๋‹นํžˆ ๋ณต์žกํ•˜๊ณ  ๋ณ„๋กœ ์ค‘์š”ํ•˜์ง€ ์•Š์œผ๋ฏ€๋กœ ์ƒ๋žตํ•ฉ๋‹ˆ๋‹คย โ†ฉ

  3. ์ž๋ฃŒ๊ตฌ์กฐ์˜ ์„ธ๊ณ„๋„ ๋์ด ์—†์Šต๋‹ˆ๋‹ค :)ย โ†ฉ