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$๋ฒ ๋ธ๋ (์ ์ ๋๋์๋ง ํ๋ฉด ๋ฐ๋ก ๋์ต๋๋ค!).

์ด โ๋ฐฐ์ด์ ์ด์งํธ๋ฆฌ๋ฅผ ์น๋โ ๊ตฌํ์ ๋์ค์ ์ด์งํธ๋ฆฌ ๊ธฐ๋ฐ์ ์๋ฃ๊ตฌ์กฐ๋ฅผ ๊ตฌํํ  ๋ ์ ๋ง ๋ง์ด ์ฐ๊ฒ ๋ฉ๋๋ค.

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๋ฒ์ ํด๊ฒฐํด ๋ณด์ธ์.