Back to : ds-alg-note
Contents

์ €๋ฒˆ ์„ธ์…˜์— ์ด์–ด์„œ, ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ๊ณต๋ถ€ํ•˜๊ณ ์ž ํ•ฉ๋‹ˆ๋‹ค.

Graphs

์ถ”์ƒ์ ์œผ๋กœ, ๊ทธ๋ž˜ํ”„๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ •์˜๋œ $G = (V, E)$๋ฅผ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค.

  • $V$๋Š” ์ •์ ์˜ ์ง‘ํ•ฉ์œผ๋กœ, ๊ทธ๋ƒฅ ์›์†Œ๋“ค์„ ๋ชจ์€ ์ง‘ํ•ฉ์œผ๋กœ ์ƒ๊ฐํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค.

  • $E$๋Š” $V \times V$์˜ ์–ด๋–ค ๋ถ€๋ถ„์ง‘ํ•ฉ์œผ๋กœ, ์›์†Œ๋“ค ๊ฐ„์˜ ์—ฐ๊ฒฐ์„ฑ์„ ํ‘œํ˜„ํ•ฉ๋‹ˆ๋‹ค.

์ฆ‰, ์  (์ •์ , ๋…ธ๋“œ) ๋“ค๊ณผ ๊ทธ๋“ค ๊ฐ„์˜ ์—ฐ๊ฒฐ์„  (๊ฐ„์„ , ์—์ง€) ๋“ค์˜ configuration์„ ๊ทธ๋ž˜ํ”„๋ผ๊ณ  ์ •์˜ํ•œ๋‹ค๋Š” ์˜๋ฏธ์ž…๋‹ˆ๋‹ค. ๋ช‡๊ฐ€์ง€ ์šฉ์–ด๋ฅผ ์งš์ž๋ฉด...

  • Directed/Undirected graph : Directed graph๋Š” ๊ฐ„์„  $(u, v)$ ์™€ $(v, u)$ ๋ฅผ ๋‹ค๋ฅธ ๊ฒƒ์œผ๋กœ ๋ณด๊ณ , Undirected graph๋Š” ๊ฐ™์ง€ ์•Š์€ ๊ฒƒ์œผ๋กœ ๋ด…๋‹ˆ๋‹ค.

  • Multigraph : $(u, v)_1$ ๊ณผ $(u, v)_2$๋กœ, ๊ฐ™์€ ๊ฐ„์„ ์ด ์—ฌ๋Ÿฌ ๊ฐœ ์žˆ์„ ์ˆ˜ ์žˆ๋Š” - ์ฆ‰, $E$๊ฐ€ set์ด ์•„๋‹ˆ๋ผ multiset์ธ - ๊ทธ๋ž˜ํ”„๋ฅผ ๋งํ•ฉ๋‹ˆ๋‹ค. ์ผ๋ฐ˜์ ์œผ๋กœ ์šฐ๋ฆฌ๋Š” ๊ณ ๋ คํ•˜์ง€ ์•Š์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค.

  • Simple graph : $E$๊ฐ€ ์ค‘๋ณต์„ ํ—ˆ์šฉํ•˜์ง€ ์•Š์„ ๋ฟ ์•„๋‹ˆ๋ผ, $(u, u)$ ๋„ ํ—ˆ์šฉํ•˜์ง€ ์•Š๋Š” ๊ทธ๋ž˜ํ”„๋ฅผ ๋งํ•ฉ๋‹ˆ๋‹ค.

  • Path : ๊ฐ„์„ ๋“ค์„ ๋”ฐ๋ผ ๋Œ ์ˆ˜ ์žˆ๋Š” โ€˜๊ฒฝ๋กœโ€™ ๋ฅผ ๋งํ•ฉ๋‹ˆ๋‹ค.

  • Circuit / Cycle : Path์˜ ์‹œ์ž‘์ ์ด ๋์ ๊ณผ ๊ฐ™์€ ๊ฒฝ์šฐ๋ฅผ ๋งํ•ฉ๋‹ˆ๋‹ค.

  • Adjacent : ์ •์  $u, v$์— ๋Œ€ํ•ด, $(u, v) \in E$ ์ด๋ฉด adjacent๋ผ๊ณ  ๋งํ•ฉ๋‹ˆ๋‹ค. ๋˜ํ•œ $u, v$๋Š” ์„œ๋กœ์˜ neighbor์ž…๋‹ˆ๋‹ค.

  • Connected Component : ์ •์  $u, v$์— ๋Œ€ํ•ด, $u$์—์„œ ์‹œ์ž‘ํ•ด์„œ $v$์— ๋„์ฐฉํ•˜๋Š” path๊ฐ€ ์กด์žฌํ•˜๋ฉด ๊ฐ™์€ connected component์— ์žˆ๋‹ค๊ณ  ๋งํ•ฉ๋‹ˆ๋‹ค. ํŠนํžˆ ๋ชจ๋“  ์ •์ ์ด ํ•˜๋‚˜์˜ connected component๋ฅผ ์ด๋ฃจ๋ฉด connected graph๋ผ๊ณ  ๋งํ•ฉ๋‹ˆ๋‹ค.

Unless otherwise specified, $V$๋Š” ์ •์ ์˜ ์ง‘ํ•ฉ์ด๋ฉด์„œ ๊ฐ„ํ˜น ์ •์ ์˜ ๊ฐœ์ˆ˜๋ฅผ $V$๊ฐœ๋ผ๊ณ  ๋ถ€๋ฅผ ๊ฒƒ์ž…๋‹ˆ๋‹ค. $E$๋„ ๋งˆ์ฐฌ๊ฐ€์ง€์ž…๋‹ˆ๋‹ค. (Abuse of notation) ๋˜ํ•œ, ์•ž์œผ๋กœ ๊ทธ๋ƒฅ ๊ทธ๋ž˜ํ”„ $G$๋ผ๊ณ  ํ•˜๋ฉด $n$๊ฐœ์˜ ์ •์ ๊ณผ $m$๊ฐœ์˜ ๊ฐ„์„ ์œผ๋กœ ์ด๋ฃจ์–ด์ง„ Undirected Connected Simple Graph๋ฅผ ์ƒ๊ฐํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. ๊ทธ๋ž˜ํ”„์— ๋Œ€ํ•œ ๋งŽ์€ ๋…ผ์ฆ์€ ๊ฐ Connected Component๋ฅผ ๋…๋ฆฝ์ ์œผ๋กœ ์ƒ๊ฐํ•  ์ˆ˜ ์žˆ์œผ๋ฉฐ, Multigraph๋„ ๋Œ€์ถฉ ๋น„์Šทํ•˜๊ฒŒ ๋‹ค๋ฃจ์–ด์งˆ ์ˆ˜ ์žˆ๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค.

Implementation of Graphs

๊ทธ๋ž˜ํ”„์— ๋Œ€ํ•ด์„œ๋Š” ํ›„์— ๋‹ค์‹œ ์ž์„ธํžˆ ๋ณด๊ฒ ์ง€๋งŒ, ์—ฌ๊ธฐ์„œ๋Š” ๊ทธ๋ž˜ํ”„๋ฅผ ์–ด๋–ป๊ฒŒ ๊ตฌํ˜„ํ• ์ง€๋งŒ ์ƒ๊ฐํ•ด ๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค.

ํ”ํžˆ ์‚ฌ์šฉํ•˜๋Š” ๊ทธ๋ž˜ํ”„ ๊ตฌํ˜„์€ ๋‘ ๊ฐ€์ง€๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค.

  • Adjacent matrix : 2์ฐจ์› $n \times n$ ๋ฐฐ์—ด์„ ์žก๊ณ , $A_{ij}$ ๋ฅผ $(i, j)$ ๊ฐ„์„ ์˜ ์กด์žฌ ์—ฌ๋ถ€๋ฅผ ์ธ์ฝ”๋”ฉํ•˜๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค. Directed graph๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์ƒ๊ฐํ•˜๋Š” ๊ฒƒ์ด ์กฐ๊ธˆ ๋” ์ž์—ฐ์Šค๋Ÿฝ๊ณ , Undirected graph์ผ ๋•Œ๋Š” $A$๊ฐ€ ๋Œ€์นญํ–‰๋ ฌ์ด ๋  ๊ฒƒ์ž…๋‹ˆ๋‹ค.

    ์ด๋ก ์ ์œผ๋กœ ์ด ๋ฐฉ๋ฒ•์ด ์กฐ๊ธˆ๋” ์ž์—ฐ์Šค๋Ÿฝ๊ฒŒ ๊ทธ๋ž˜ํ”„๋ฅผ ๋Œ€ํ•  ์ˆ˜ ์žˆ๋Š”๋ฐ, ํŠนํžˆ Adjacency matrix $A$์˜ ์„ ํ˜•๋Œ€์ˆ˜ํ•™์  ์„ฑ์งˆ๋กœ๋ถ€ํ„ฐ (Eigenvalue ๋“ฑ) ๊ทธ๋ž˜ํ”„์˜ ์„ฑ์งˆ์„ ์•Œ ์ˆ˜ ์žˆ๋Š” ๊ฒƒ๋“ค์ด ๋งŽ์ด ์žˆ๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค.

  • Adjacent list : Vector๋‚˜ List๊ฐ™์€ ๋‹ค์ด๋‚˜๋ฏนํ•œ ๋ญ”๊ฐ€๋ฅผ ์ •์ ๋งˆ๋‹ค ํ•˜๋‚˜์”ฉ $n$๊ฐœ ์žก๊ณ , โ€œ์ด ์ •์ ์— ์ธ์ ‘ํ•œ ์ •์ โ€ ๋“ค์˜ ๋ฆฌ์ŠคํŠธ (๋ฐฐ์—ด) ์„ ๊ด€๋ฆฌํ•˜๋Š” ๊ด€์ ์ž…๋‹ˆ๋‹ค.

๊ทธ๋ž˜ํ”„์˜ Density์— ๋Œ€ํ•ด ์ƒ๊ฐํ•ด ๋ด…์‹œ๋‹ค. ์ผ์ƒ์—์„œ ๋งŒ๋‚˜๋Š” ๋Œ€๋ถ€๋ถ„์˜ (ํฐ) ๊ทธ๋ž˜ํ”„๋“ค์€, ๊ต‰์žฅํžˆ sparseํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ํŽ˜์ด์Šค๋ถ ์ „์ฒด์˜ ์นœ๊ตฌ ๊ด€๊ณ„๋ฅผ ๊ทธ๋ž˜ํ”„๋กœ ๊ทธ๋ฆฐ๋‹ค๋ฉด, ํŽ˜์ด์Šค๋ถ ์œ ์ € 10์–ต ๋ช… ์ค‘ ์—ฌ๋Ÿฌ๋ถ„์˜ ํŽ˜์นœ์€ ๋งŽ์•„์•ผ ์ฒœ ๋ช… ๋‹จ์œ„์ผ ๊ฒƒ์ด๋ฏ€๋กœ ์ „์ฒด ๊ฐ€๋Šฅํ•œ ๊ฐ„์„ ๋“ค ์ค‘ 100๋งŒ ๋ถ„์˜ 1 ์ •๋„๋ฐ–์— ์‚ฌ์šฉ๋˜์ง€ ์•Š๋Š”๋‹ค๋Š” ์˜๋ฏธ์ž…๋‹ˆ๋‹ค. ๋Œ€์ถฉ ๊ฐ„์„ ์ด $n^2$๊ฐœ ๊ทผ์ฒ˜์ผ ๋•Œ dense, ๊ทธ๋ณด๋‹ค ๋งŽ์ด ์ž‘์œผ๋ฉด sparse๋ผ๊ณ  ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.

Adjacent matrix๊ฐ€ ์ด๋ก ์ ์œผ๋กœ ๋ณด๋‹ค ์•„๋ฆ„๋‹ต๊ฒŒ ๋Š๊ปด์งˆ ์ˆ˜ ์žˆ์ง€๋งŒ, ๊ทธ๋ž˜ํ”„๊ฐ€ sparseํ•  ๋•Œ adjacent matrix๋Š” $O(n^2)$ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์†Œ๋ชจํ•œ๋‹ค๋Š” ์‹ฌ๊ฐํ•œ ๋‹จ์ ์ด ์žˆ์Šต๋‹ˆ๋‹ค. ์šฐ๋ฆฌ๋Š” ๋งŽ์€ ๊ฒฝ์šฐ์— sparseํ•œ ๊ทธ๋ž˜ํ”„๋ฅผ ๋‹ค๋ฃจ๊ณ  ์‹ถ๊ณ , ๊ฐ„์„ ์„ ๋”ฐ๋ผ๊ฐ€๋ฉด์„œ ์ž‘์—…์„ ํ•˜๊ณ  ์‹ถ์Šต๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด...

for (int nxt = 0; nxt < n; nxt++)
    if (A[i][nxt])
        traverse(A[i][nxt]);

for (int j = 0; j < A[i].size(); j++)
    traverse(A[i][j]);

์ด ์ฝ”๋“œ๋Š” ๋‘˜ ๋‹ค $i$์˜ neighbor๋“ค์„ ๋Œ๋ฉด์„œ traverseํ•จ์ˆ˜๋ฅผ ํ˜ธ์ถœํ•˜์ง€๋งŒ, ์ „์ž์˜ ๊ฒฝ์šฐ์—๋Š” if๋ฌธ์ด ์ถ”๊ฐ€๋  ๋ฟ ์•„๋‹ˆ๋ผ $O(n)$ ๊ฐœ๋งŒํผ ํ™•์ธํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ๋งŒ์•ฝ ํŽ˜์ด์Šค๋ถ ์นœ๊ตฌ ๊ทธ๋ž˜ํ”„์— ๋Œ€ํ•ด ์ฝ”๋“œ๋ฅผ ๋Œ๋ฆฌ๋ฉด, ์œ„์ชฝ ๊ฒฝ์šฐ์—๋Š” ๋‚ด ์นœ๊ตฌ๋“ค์„ ์ฐพ๊ธฐ ์œ„ํ•ด 10์–ต๋ช…์˜ ๋ชจ๋“  ์œ ์ €๋ฅผ ํƒ์ƒ‰ํ•˜๋Š” ๋ฐ˜๋ฉด ํ›„์ž๋Š” ๊ทธ๋Ÿฐ ํ•„์š”๊ฐ€ ์—†์Šต๋‹ˆ๋‹ค.

๋‹ค๋งŒ ์ธ์ ‘ํ–‰๋ ฌ์ด ๊ตฌํ˜„์ด ์ข€๋” ๊ฐ„๋‹จํ•˜๊ณ , ํ–‰๋ ฌ ๊ณฑ์…ˆ์„ ํ†ตํ•ด ์—ฐ๊ฒฐ์„ฑ์„ ๋ณธ๋‹ค๋˜๊ฐ€ ํ•˜๋Š” ์—ฐ์‚ฐ๋“ค์ด ๊ฐ€๋Šฅํ•˜๊ธฐ ๋•Œ๋ฌธ์—, ํ•„์š”ํ•œ ๊ฒฝ์šฐ์—๋Š” ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ๊ทธ๋Ÿฌ๋‚˜ ์œ„ ์ด์œ ๋“ค ๋•Œ๋ฌธ์—, ์šฐ๋ฆฌ๋Š” ๊ธฐ๋ณธ์ ์œผ๋กœ ์ธ์ ‘๋ฆฌ์ŠคํŠธ๋ฅผ ๊ทธ๋ž˜ํ”„์˜ ๊ธฐ๋ณธ ํ‘œํ˜„์œผ๋กœ ๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค.

Trees / Binary Trees

์ •์  $n$๊ฐœ ์ค‘ ์–ด๋–ค ๋ฃจํŠธ๊ฐ€ ์žˆ๊ณ , ๋ฃจํŠธ๋กœ๋ถ€ํ„ฐ ๋ชจ๋“  ์ •์ ๊นŒ์ง€์˜ ๊ฒฝ๋กœ๊ฐ€ ์œ ์ผํ•˜๊ฒŒ ์กด์žฌํ•˜๋Š” ๊ทธ๋ž˜ํ”„๋ฅผ Tree๋ผ๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ์ด๋•Œ ๋ฃจํŠธ๋กœ๋ถ€ํ„ฐ ๊ฒฝ๋กœ๋ฅผ ๋‚ด๋ ธ์„ ๋•Œ ๋‚ด ๋ฐ”๋กœ ์ด์ „ ๋…ธ๋“œ๋ฅผ parent, ๊ทธ ์ด์ „ ๋…ธ๋“œ๋“ค์„ ancestor๋ผ๊ณ  ํ•ฉ๋‹ˆ๋‹ค (๋ฐ˜๋Œ€๋Š” child, descendant) ํŠธ๋ฆฌ์˜ ๊ฒฝ์šฐ, ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ ํ‘œํ˜„ ์™ธ์—๋„ ๊ทธ๋ƒฅ $n$์นธ ๋ฐฐ์—ด์— ๊ฐ tree์˜ parent node๋ฅผ ์ €์žฅํ•˜๋Š” ๋ฐฉ๋ฒ•์œผ๋กœ๋„ ์ €์žฅํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

Binary Tree๋ž€, ๋ชจ๋“  ๋…ธ๋“œ์˜ Child node๊ฐ€ ์ตœ๋Œ€ 2๊ฐœ์ธ ํŠธ๋ฆฌ๋ฅผ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค. ๊ตฌํ˜„์˜ ํŽธ์˜์™€, ๋‹ค์–‘ํ•œ ํ™œ์šฉ์ฒ˜ ๋•Œ๋ฌธ์— ๋งค์šฐ ์ž์ฃผ ํ™œ์šฉ๋˜๋Š” ์ž๋ฃŒ ๊ตฌ์กฐ์ž…๋‹ˆ๋‹ค. ์šฐ๋ฆฌ๋Š” ์•ž์œผ๋กœ Binary tree ๋…ธ๋“œ๋ฅผ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ƒ๊ฐํ•  ๊ฒƒ์ž…๋‹ˆ๋‹ค.

struct node {
    int val, id;
    node * left;
    node * right;
} root;

์ฆ‰, ๊ฐ ๋…ธ๋“œ๊ฐ€ id์™€ ์–ด๋–ค ๊ฐ’์„ ํ•˜๋‚˜ ๊ฐ€์ง€๊ณ  ์žˆ๊ณ , ์ž์‹ ์˜ left / right child๋กœ ๊ฐ€๋Š” ํฌ์ธํ„ฐ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ์Œ์„ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค.

์ด์ง„ ํŠธ๋ฆฌ์˜ Special case๋กœ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ฒฝ์šฐ๋“ค์ด ์žˆ์Šต๋‹ˆ๋‹ค.

  • Full Binary Tree : ๋ชจ๋“  ๋…ธ๋“œ๊ฐ€ 0๊ฐœ ๋˜๋Š” 2๊ฐœ์˜ ์ž์‹ ๋…ธ๋“œ๋ฅผ ๊ฐ–์Šต๋‹ˆ๋‹ค.

  • Complete Binary Tree : ๊ฐ€์žฅ ์•„๋ž˜ ์ธต์„ ์ œ์™ธํ•œ ๋ชจ๋“  ์ธต์ด ์ตœ๋Œ€ํ•œ ๋…ธ๋“œ๊ฐ€ ์ฐจ ์žˆ๊ณ , ๊ฐ€์žฅ ์•„๋ž˜ ์ธต์—์„œ๋„ ์ตœ๋Œ€ํ•œ ์™ผ์ชฝ์œผ๋กœ ๋…ธ๋“œ๊ฐ€ ๋ชฐ๋ ค์žˆ๋Š” ํŠธ๋ฆฌ์ž…๋‹ˆ๋‹ค.

  • Perfect Binary Tree : Complete ์ด๋ฉด์„œ Full ์ธ binary tree์ž…๋‹ˆ๋‹ค. ๋†’์ด๊ฐ€ $h$์ธ Perfect Binary Tree์˜ ๋…ธ๋“œ๋Š” ํ•ญ์ƒ $2^h$์ž„์„ ๊ธฐ์–ตํ•˜์„ธ์š”.

์ผ๋ฐ˜์ ์œผ๋กœ, Balance๊ฐ€ ์ž˜ ์žกํ˜€ ์žˆ๋Š” binary tree๋Š” ๋†’์ด๊ฐ€ $\log n$ ์ •๋„์ด๊ณ , ํ•œ ์ค„์— ๊ฐ€๊นŒ์šด binary tree๋Š” ๋†’์ด๊ฐ€ $n$ ์ •๋„์ž„์„ ๊ธฐ์–ตํ•˜๋ฉด ์ข‹์Šต๋‹ˆ๋‹ค.

Heaps

Heap์ด๋ผ๋Š” ์ž๋ฃŒ ๊ตฌ์กฐ๋Š”, ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์„ฑ์งˆ์„ ๋งŒ์กฑํ•˜๋Š” ํŠธ๋ฆฌ๋ฅผ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค.

  • Complete Binary Tree. ์ฆ‰, ์ตœ๋Œ€ํ•œ ๊ท ํ˜•์ด ์žกํ˜€ ์žˆ๊ณ , ๋…ธ๋“œ๊ฐ€ ๋‚จ๋Š”๋‹ค๋ฉด ์™ผ์ชฝ์œผ๋กœ ๋ชฐ์•„๋„ฃ์€ ์ƒํƒœ์˜ ํŠธ๋ฆฌ์—ฌ์•ผ ํ•ฉ๋‹ˆ๋‹ค.

  • ํž™ ์„ฑ์งˆ. ๋ถ€๋ชจ ๋…ธ๋“œ์— ์“ฐ์—ฌ ์žˆ๋Š” ๊ฐ’์€, ์ž์‹ ๋…ธ๋“œ์— ์“ฐ์—ฌ ์žˆ๋Š” ๊ฐ’๋ณด๋‹ค ํ•ญ์ƒ ์ž‘๊ฑฐ๋‚˜ ๊ฐ™๋‹ค.

์ด์ œ, Complete Binary Tree์˜ ๊ตฌ์กฐ๋ฅผ ์ƒ๊ฐํ•ด ๋ณด๋ฉด, ํ•œ ์ธต์”ฉ ๋ฐ‘์œผ๋กœ ๋‚ด๋ ค์˜ฌ ๋•Œ๋งˆ๋‹ค ๋…ธ๋“œ์˜ ๊ฐœ์ˆ˜๊ฐ€ 2๋ฐฐ์”ฉ ๋Š˜์–ด๋‚˜๋ฏ€๋กœ, ์ „์ฒด ๋…ธ๋“œ์˜ ๊ฐœ์ˆ˜๊ฐ€ $n$๊ฐœ ์ •๋„์ผ ๋•Œ, ๋†’์ด $h$ ๋Š” $h \in \Theta(\log n)$ ์ž…๋‹ˆ๋‹ค. ๋˜ํ•œ, Heap์˜ ์„ฑ์งˆ ์ƒ, Heap์˜ ์ž„์˜์˜ ๋…ธ๋“œ๋ฅผ ํ•˜๋‚˜ ์žก์œผ๋ฉด, ๊ทธ ๋…ธ๋“œ๋ฅผ root๋กœ ํ•˜๋Š” subtree๋„ ๋‹ค์‹œ heap์ž„์„ ์•Œ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

Heap Operation

Heap์˜ ๊ธฐ๋ณธ operation์œผ๋กœ, ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋‘๊ฐ€์ง€ ์—ฐ์‚ฐ์„ ์ƒ๊ฐํ•ฉ๋‹ˆ๋‹ค.

  • Heap์— ์–ด๋–ค ์ˆ˜ $x$๋ฅผ ์‚ฝ์ž…ํ•˜๋Š” Push ์—ฐ์‚ฐ

  • Heap์˜ ๋…ธ๋“œ๋ฅผ ์‚ญ์ œํ•˜๋Š” ์—ฐ์‚ฐ

Pop ์—ฐ์‚ฐ์—์„œ ๋ฃจํŠธ๋งŒ ์ƒ๊ฐํ•ด๋„ ๋˜๋Š” ์ด์œ ๋Š” ์•ž์„œ ๋งํ•œ ๋ฐ”์™€ ๊ฐ™์ด, ๋ชจ๋“  ๋…ธ๋“œ๊ฐ€ ์ž์‹ ์„ subtree๋กœ ํ•˜๋Š” heap์˜ ๋ฃจํŠธ์ด๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ, ์œ„ ๋‘ ์—ฐ์‚ฐ๋งŒ ์žˆ์œผ๋ฉด Heap์— ์ž„์˜์˜ ์›์†Œ๋ฅผ ์‚ฝ์ž…ํ•˜๊ณ  ์‚ญ์ œํ•  ์ˆ˜ ์žˆ๋‹ค๋Š” ์˜๋ฏธ์ž…๋‹ˆ๋‹ค.
์ด ์—ฐ์‚ฐ์„ ์–ด๋–ป๊ฒŒ ๊ตฌํ˜„ํ• ์ง€ ์ƒ๊ฐํ•ด ๋ด…์‹œ๋‹ค. Push์˜ ๊ฒฝ์šฐ, ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ณผ์ •์œผ๋กœ ์ˆ˜ํ–‰ํ•ฉ๋‹ˆ๋‹ค.

  • ๋ฌด์กฐ๊ฑด ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ ์„ฑ์งˆ์„ ๋งŒ์กฑํ•˜๋Š” ๊ฒƒ์„ ์šฐ์„ ํ•˜์—ฌ, ๋ ์ž๋ฆฌ์— ์‚ฝ์ž…ํ•ฉ๋‹ˆ๋‹ค.

  • ๋์ž๋ฆฌ์˜ ์‚ฝ์ž…์œผ๋กœ ์ธํ•ด ํž™ ์„ฑ์งˆ์ด ๊นจ์กŒ์„ ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ, ๊ทธ ์ž๋ฆฌ๋ถ€ํ„ฐ ์˜ฌ๋ผ์˜ค๋ฉด์„œ ํž™์„ ์ˆ˜์„ ํ•ฉ๋‹ˆ๋‹ค.

ํž™์„ ์ˆ˜์„ ํ•œ๋‹ค๊ณ  ํ•˜๋Š” ๋ง์€, ์‹ค์ œ๋กœ๋Š” ์‚ฝ์ž…ํ•œ ์ž๋ฆฌ๋ถ€ํ„ฐ ์˜ฌ๋ผ์˜ค๊ฑฐ๋‚˜ ๋‚ด๋ ค๊ฐ€๋ฉด์„œ, ์ž์‹ ๋…ธ๋“œ๊ฐ€ ๋ถ€๋ชจ ๋…ธ๋“œ๋ณด๋‹ค ํฐ ๊ฐ’์„ ๊ฐ€์กŒ์œผ๋ฉด ๋‘ ๋…ธ๋“œ๋ฅผ ๊ตํ™˜ํ•œ๋‹ค๋Š” ์˜๋ฏธ์ž…๋‹ˆ๋‹ค. ์•ž์œผ๋กœ ์ด์™€ ๊ฐ™์€ โ€œํž™ ์ˆ˜์„ โ€ ์ด๋ผ๋Š” ๋ง์„ ๊ณ„์† ์“ธ ํ…๋ฐ, ๊ธฐ๋ณธ์ ์œผ๋กœ ํŠน์ • ๋…ธ๋“œ์—์„œ ํž™์„ ์ˆ˜์„ ํ•œ๋‹ค๋ฉด, ๋ฃจํŠธ๋ถ€ํ„ฐ ๋ฆฌํ”„๊นŒ์ง€ ๋‚ด๋ ค๊ฐ€๋ฉด์„œ ๋งค ๋‹จ๊ณ„ ์ตœ๋Œ€ 2๊ฐœ์”ฉ, ๋งŽ์•„์•ผ $2h \in O(\log n)$ ๊ฐœ์˜ ๋…ธ๋“œ๋งŒ ๋ณด๋ฉด ๋ฉ๋‹ˆ๋‹ค.

ํž™์—์„œ ๋…ธ๋“œ๋ฅผ ์‚ญ์ œํ•˜๋Š” ์—ฐ์‚ฐ์€ ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.

  • ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ ์„ฑ์งˆ์„ ๋งŒ์กฑํ•˜๋Š” ๊ฒƒ์„ ์šฐ์„ ํ•˜์—ฌ, ๋ ์ž๋ฆฌ ๋…ธ๋“œ์™€ ์‚ญ์ œํ•  ๋…ธ๋“œ์˜ ์ž๋ฆฌ๋ฅผ ๋ฐ”๊ฟ‰๋‹ˆ๋‹ค.

  • ๋ ์ž๋ฆฌ์˜ ๋…ธ๋“œ๋ฅผ ์ง€์›Œ๋„ ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ ์„ฑ์งˆ์ด ๊นจ์ง€์ง€ ์•Š์Šต๋‹ˆ๋‹ค.

  • ์ด์ œ, ๋ฐฉ๊ธˆ ๊ตํ™˜์— ์˜ํ•ด ํž™ ์„ฑ์งˆ์ด ๊นจ์กŒ์„ ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ, ์œ„์•„๋ž˜๋กœ ์˜ค๊ฐ€๋ฉด์„œ ํž™์„ ์ˆ˜์„ ํ•ฉ๋‹ˆ๋‹ค.

๊ณผ์ •์„ ๋ณด๋ฉด, ์ˆ˜์„  ์™ธ์˜ ๋ชจ๋“  Operation์€ ๊ตฌํ˜„์„ ์ž˜ ํ•˜๋ฉด $O(1)$์— ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์„ ๊ฒƒ ๊ฐ™์•„ ๋ณด์ž…๋‹ˆ๋‹ค. ์ˆ˜์„ ์—์„œ๋Š” ๊ฐ’ ๊ฐ„์˜ ๋น„๊ต๊ฐ€ ์ตœ๋Œ€ $O(\log n)$ ๋ฒˆ ์ผ์–ด๋‚˜๊ธฐ ๋•Œ๋ฌธ์—, ์ „์ฒด ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์ˆ˜ํ–‰ ์‹œ๊ฐ„์€ $O(\log n)$ ์ž…๋‹ˆ๋‹ค.

Heap Sort

๋นˆ Heap๊ณผ $n$ ํฌ๊ธฐ์˜ ๋ฐฐ์—ด์—์„œ ์‹œ์ž‘ํ•ด์„œ, ๋ชจ๋“  element๋ฅผ Heap์— ๋„ฃ์Šต๋‹ˆ๋‹ค. ๊ทธ๋‹ค์Œ, ๋ฃจํŠธ๊ฐ€ ์ „์ฒด heap์˜ ์ตœ์†Ÿ๊ฐ’์ด๋ฏ€๋กœ, ๋ฃจํŠธ๋ฅผ ํ™•์ธํ•˜๊ณ  ์‚ญ์ œํ•˜๋Š” ์—ฐ์‚ฐ์„ $n$๋ฒˆ ๋ฐ˜๋ณตํ•˜๋ฉด, ์ž‘์€ ์›์†Œ๋ถ€ํ„ฐ ์ˆœ์„œ๋Œ€๋กœ ๋‚˜์˜ค๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. ๋„ฃ๊ณ  ๋นผ๋Š”๋ฐ ๋งค๋ฒˆ $O(\log n)$์”ฉ์ด๋ฏ€๋กœ ํ•ญ์ƒ $O(n \log n)$ ์ •๋ ฌ์ž„์ด ๋ณด์žฅ๋ฉ๋‹ˆ๋‹ค!

Heap Implementation

ํž™์ด ํŠธ๋ฆฌ ๊ตฌ์กฐ๋ผ๊ณ  ํ•ด์„œ, ์‹ค์ œ๋กœ ํฌ์ธํ„ฐ ์„ธ๊ฐœ์งœ๋ฆฌ ๋…ธ๋“œ๋กœ (Parent, Left-Child, Right-Child) ๊ตฌํ˜„ํ•ด์•ผ ํ•  ํ•„์š”๋Š” ์—†์Šต๋‹ˆ๋‹ค. ์‹ค์ œ๋กœ๋Š”, ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์›๋ฆฌ๋กœ ๋ฐฐ์—ด์— ํŠธ๋ฆฌ๋ฅผ ์–น๋Š” ๋Š๋‚Œ์œผ๋กœ ๊ตฌํ˜„ํ•˜๋ฉด ์œ ์šฉํ•ฉ๋‹ˆ๋‹ค.

  • 1๋ฒˆ ๋…ธ๋“œ๋ฅผ ๋ฃจํŠธ๋กœ ํ•œ๋‹ค.

  • $n$๋ฒˆ ๋…ธ๋“œ์˜ ๋‘ ์ž์‹ ๋…ธ๋“œ๋Š” $2n$, $2n+1$๋ฒˆ์œผ๋กœ ํ•œ๋‹ค.

  • ๊ทธ๋Ÿฌ๋ฉด, ์ž๋™์œผ๋กœ $n$๋ฒˆ ๋…ธ๋“œ์˜ ๋ถ€๋ชจ ๋…ธ๋“œ๋Š” $n/2$๋ฒˆ ๋…ธ๋“œ (์ •์ˆ˜ ๋‚˜๋ˆ—์…ˆ๋งŒ ํ•˜๋ฉด ๋ฐ”๋กœ ๋‚˜์˜ต๋‹ˆ๋‹ค!).

์ด โ€˜๋ฐฐ์—ด์— ์ด์ง„ํŠธ๋ฆฌ๋ฅผ ์–น๋Š”โ€™ ๊ตฌํ˜„์€ ๋‚˜์ค‘์— ์ด์ง„ํŠธ๋ฆฌ ๊ธฐ๋ฐ˜์˜ ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ๊ตฌํ˜„ํ•  ๋•Œ ์ •๋ง ๋งŽ์ด ์“ฐ๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.

Additional topics and Problems

  1. Heap sort์—์„œ๋Š” ์–ด์ฐจํ”ผ ๋ณต์žก๋„๊ฐ€ ๋‹ฌ๋ผ์ง€์ง€ ์•Š์•„์„œ ๋นˆ ํž™์— $n$๊ฐœ์˜ ์›์†Œ๋ฅผ ์ˆœ์„œ๋Œ€๋กœ ์‚ฝ์ž…ํ•˜๋Š” ์‹์œผ๋กœ ํž™์„ ๊ตฌ์„ฑํ–ˆ์ง€๋งŒ, ์‹ค์ œ๋กœ๋Š” ์ด๋ฏธ ์žˆ๋Š” ๋ฐฐ์—ด์„ ๊ทธ๋Œ€๋กœ Heap์œผ๋กœ ๋งŒ๋“œ๋Š” Heapify() ์—ฐ์‚ฐ์€ ์ด๋ณด๋‹ค ๋นจ๋ฆฌ ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ณผ์ •์„ ์ด์šฉํ•ฉ๋‹ˆ๋‹ค.

    • ๊ฐ€์žฅ ์•„๋ž˜ ๋…ธ๋“œ ($N$๋ฒˆ) ๋ถ€ํ„ฐ ์‹œ์ž‘ํ•ฉ๋‹ˆ๋‹ค.

    • ์ž์‹ ์˜ ๊ฐ’์ด ๋ถ€๋ชจ๋…ธ๋“œ๋ณด๋‹ค ๋†’๋‹ค๋ฉด, ๋ถ€๋ชจ๋…ธ๋“œ์™€ ๊ฐ’์„ ๊ตํ™˜ํ•ฉ๋‹ˆ๋‹ค.

    • ์ด๋•Œ์˜ ๊ฐ’์ด ์ž์‹ ์ •์ ๋ณด๋‹ค ์ž‘๋‹ค๋ฉด, ์ž์‹๋…ธ๋“œ ์ค‘ ์ž‘์€ ์ชฝ๊ณผ ๊ฐ’์„ ๊ตํ™˜ํ•ฉ๋‹ˆ๋‹ค. (๋ฆฌํ”„๊นŒ์ง€ ๋‚ด๋ ค๊ฐ€๋ฉด์„œ)

    • ์žฌ๊ท€์ ์œผ๋กœ ๋ฐ˜๋ณตํ•ฉ๋‹ˆ๋‹ค.

    Heap ์ˆ˜์„  ๊ณผ์ •๊ณผ ๋˜‘๊ฐ™์•„ ๋ณด์ด์ง€๋งŒ, ์•ฝ๊ฐ„์˜ ์ฐจ์ด๋Š” ์œ„์ชฝ์œผ๋กœ๋Š” ๋๊นŒ์ง€ ํ™•์ธํ•˜์ง€ ์•Š๋Š”๋‹ค๋Š” ์ ์ž…๋‹ˆ๋‹ค. ์•„๋ž˜์ชฝ์œผ๋กœ๋Š” ์žฌ๊ท€์ ์œผ๋กœ ๋ฐ˜๋ณตํ•ด์•ผ ํ•˜์ง€๋งŒ, ๋ถ€๋ชจ๋…ธ๋“œ์™€ ๊ฐ’์„ ๊ตํ™˜ํ–ˆ๋‹ค๊ณ  ํ•ด์„œ ํ•œ๋ฒˆ์— ์œ„์ชฝ๊นŒ์ง€ ํž™์„ ์ˆ˜์„ ํ•˜์ง€ ๋ง๊ณ , ๋ถ€๋ชจ๋…ธ๋“œ์˜ ๊ฐ’์€ ๋‚˜์ค‘์— ๊ทธ ๋…ธ๋“œ ์ฐจ๋ก€๊ฐ€ ๋  ๋•Œ ํ™•์ธํ•ด๋„ ๋ฉ๋‹ˆ๋‹ค.
    ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ์ƒ๊ฐํ•ด ๋ณด๋ฉด, ์ž์‹ ์˜ ๋†’์ด์— ๋น„๋ก€ํ•˜๋Š” ์ •๋„์˜ ์—ฐ์‚ฐ์ด ํ•„์š”ํ•จ์„ ์•Œ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋Œ€๋žต ๊ฐ ๋…ธ๋“œ๋งˆ๋‹ค ๋†’์ด๊ฐ€ $h$๋ผ๋ฉด ๋Œ€๋žต $O(h)$๋ฒˆ ์—ฐ์‚ฐ์ด ํ•„์š”ํ•ฉ๋‹ˆ๋‹ค. ๋†’์ด๊ฐ€ $k$์ธ ๋…ธ๋“œ๊ฐ€ $2^k$๊ฐœ์ž„์„ ์ด์šฉํ•˜์—ฌ, ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์ฃผ์–ด์ง„ Array๋ฅผ Heap์œผ๋กœ ๊ณ ์น˜๋Š” ๋ฐ $O(n)$ ์‹œ๊ฐ„๋ฐ–์— ๊ฑธ๋ฆฌ์ง€ ์•Š์Œ์„ ๋ณด์ด์„ธ์š”.

    ํžŒํŠธ) ๊ฐ ๋…ธ๋“œ๋Š” โ€˜์ตœ๋Œ€ ์–ผ๋งˆ๋‚˜โ€™ ๋‚ด๋ ค๊ฐˆ ์ˆ˜ ์žˆ๋‚˜์š”?

Programming Practice

  1. BOJ 19535๋ฒˆ์„ ํ•ด๊ฒฐํ•ด ๋ณด์„ธ์š”.

  2. BOJ 11279๋ฒˆ์„ (STL์˜ priority queue๋ฅผ ์“ฐ์ง€ ๋ง๊ณ ) ํ•ด๊ฒฐํ•ด ๋ณด์„ธ์š”.

  3. BOJ 1655๋ฒˆ์„ ํ•ด๊ฒฐํ•ด ๋ณด์„ธ์š”.