Back to : ds-alg-note

์˜ค๋Š˜์€ ์—ฐ์Šต๋ฌธ์ œ๋งŒ ์žˆ์Šต๋‹ˆ๋‹ค.

  1. Segment Tree : ์ˆ˜์—ด์„ ๋‹ค๋ฃจ๋Š” ์ž๋ฃŒ๊ตฌ์กฐ์ค‘ ํ•˜๋‚˜์ž…๋‹ˆ๋‹ค. ์–ด๋–ค ์ˆ˜์—ด $a_1, a_2, \dots a_n$ ์ด ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค.

    • ๊ตฌ๊ฐ„ $[i, j]$๊ฐ€ ์ฃผ์–ด์ง€๋ฉด, $a_i + a_{i+1} + \dots + a_j$ ์˜ ๊ฐ’์„ ๊ตฌํ•ฉ๋‹ˆ๋‹ค.

    • $i, v$ ๊ฐ€ ์ฃผ์–ด์ง€๋ฉด, $a_i$ ์— $v$๋ฅผ ๋”ํ•ฉ๋‹ˆ๋‹ค.

    1. ์ฒซ๋ฒˆ์งธ ์ฟผ๋ฆฌ๋งŒ ์ฃผ์–ด์ง€๊ณ , ๋‘๋ฒˆ์งธ ์ฟผ๋ฆฌ๊ฐ€ ์ฃผ์–ด์ง€์ง€ ์•Š๋Š”๋‹ค๋ฉด, ์ด ๋ฌธ์ œ๋ฅผ ์ฟผ๋ฆฌ๋‹น $O(1)$ ์— ์ฒ˜๋ฆฌํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋ถ€๋ถ„ํ•ฉ ๋ฐฐ์—ด์ด๋ผ๊ณ  ๋ถ€๋ฆ…๋‹ˆ๋‹ค. ์ด ๋ฐฉ๋ฒ•์„ ์„ค๋ช…ํ•˜์„ธ์š”.

    2. ์šฐ๋ฆฌ๋Š” Complete Binary Tree๋ฅผ ๋งŒ๋“ค์–ด์„œ ์ด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ณ ์ž ํ•ฉ๋‹ˆ๋‹ค. ๊ฐ ๋…ธ๋“œ๋Š” ์–ด๋–ค ๊ตฌ๊ฐ„์„ ๋‹ด๋‹นํ•  ๊ฒƒ์ž…๋‹ˆ๋‹ค. ๊ฐ ๋…ธ๋“œ๋“ค์€ ๋‹ค์Œ ์›์น™์„ ์ง€ํ‚ต๋‹ˆ๋‹ค. โ€œ๋…ธ๋“œ์˜ ๊ฐ’์€, ๋‘ ์ž์‹ ๋…ธ๋“œ์˜ ๊ฐ’์„ ํ•ฉํ•œ ๊ฐ’์„ ๊ฐ–๋Š”๋‹ค. ๊ฐ ๋…ธ๋“œ๋Š” ๋‘ ์ž์‹ ๋…ธ๋“œ๊ฐ€ ๋‹ด๋‹นํ•˜๋Š” ๊ตฌ๊ฐ„์„ ํ•ฉํ•œ ๊ตฌ๊ฐ„์„ ๋‹ด๋‹นํ•œ๋‹ค"

    3. ์ „์ฒด ๋…ธ๋“œ์˜ ๊ฐœ์ˆ˜๊ฐ€ ๋ช‡ ๊ฐœ์ธ์ง€ ์ƒ๊ฐํ•ด ๋ณด์„ธ์š”. ์ฒซ ๋ฒˆ์งธ ์ฟผ๋ฆฌ๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ด๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด ์ด ํ™•์ธํ•ด์•ผ ํ•˜๋Š” ๋…ธ๋“œ๊ฐ€ ๋ช‡ ๊ฐœ์ธ์ง€ ์ƒ๊ฐํ•ด ๋ณด์„ธ์š”. ๋‘ ๋ฒˆ์งธ ์ฟผ๋ฆฌ์— ๋Œ€ํ•ด์„œ๋„ ๊ฐ™์€ ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•ด ๋ณด์„ธ์š”.

    4. ์ด ๋ฐฉ๋ฒ•์ด ๋‘ ์ฟผ๋ฆฌ๋ฅผ ๋น ๋ฅด๊ฒŒ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์Œ์„ ์ดํ•ดํ•˜๊ณ , ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๊ณ„์‚ฐํ•ด ๋ณด์„ธ์š”.

  2. Segment Tree with Lazy Propagation : ์œ„ ๋ฌธ์ œ์™€ ๊ฑฐ์˜ ๊ฐ™์Šต๋‹ˆ๋‹ค.

    • ๊ตฌ๊ฐ„ $[i, j]$๊ฐ€ ์ฃผ์–ด์ง€๋ฉด, $a_i + a_{i+1} + \dots + a_j$ ์˜ ๊ฐ’์„ ๊ตฌํ•ฉ๋‹ˆ๋‹ค.

    • ๊ตฌ๊ฐ„ $[i, j]$์™€ ๊ฐ’ $v$ ๊ฐ€ ์ฃผ์–ด์ง€๋ฉด, $a_i, a_{i+1}, \dots a_j$ ์— ๋ชจ๋‘ $v$๋ฅผ ๋”ํ•ฉ๋‹ˆ๋‹ค.

    1. ์ผ๋ฐ˜์ ์ธ ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ๊ฐ€ ์ด ๋ฌธ์ œ๋ฅผ ์ž˜ ํ•ด๊ฒฐํ•˜์ง€ ๋ชปํ•จ์„ ๊ด€์ฐฐํ•˜์„ธ์š”.

    2. ์ถ”๊ฐ€์ ์ธ ๊ธฐ๋ฒ•์œผ๋กœ, ๊ฐฑ์‹ ์„ โ€œ๋ฏธ๋ฃจ๋Š”โ€ ๋ฐฉ๋ฒ•์„ ์‚ฌ์šฉํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. ๊ฐ ๋…ธ๋“œ๋งˆ๋‹ค, ์ด ๋…ธ๋“œ๊ฐ€ ์ง€๊ธˆ๊นŒ์ง€ ์–ผ๋งˆ๋‚˜ ๊ฐฑ์‹ ์„ ๋ฏธ๋ฃจ๊ณ  ์žˆ์—ˆ๋Š”์ง€๋ฅผ ์ถ”๊ฐ€๋กœ ์ €์žฅํ•ฉ๋‹ˆ๋‹ค.

    3. 1๋ฒˆ, 2๋ฒˆ ์ฟผ๋ฆฌ๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ ๊ฐ๊ฐ ์–ด๋–ป๊ฒŒ ์ด ์ •๋ณด๋ฅผ ์ด์šฉํ•˜์—ฌ ๊ฐ’์„ ๊ณ„์‚ฐํ• ์ง€ ์ œ์‹œํ•˜๊ณ , ๊ทธ ๋ฐฉ๋ฒ•๋“ค์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๊ณ„์‚ฐํ•˜์„ธ์š”.

  3. Merge Sort Tree : ์ด๋ฒˆ์—๋Š” ์œ„์™€ ๊ฐ™์ด ์ˆ˜์—ด์ด ์ฃผ์–ด์ง€๋Š” ์ƒํ™ฉ์—์„œ, ์ด๋Ÿฐ ๋ฌธ์ œ๋ฅผ ์ƒ๊ฐํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.

    • ๊ตฌ๊ฐ„ $[i, j]$์™€ ์–ด๋–ค ์ˆ˜ $k$๊ฐ€ ์ฃผ์–ด์ง€๋ฉด, $a_i, a_{i+1}, \dots a_j$ ์—์„œ $k$๋ณด๋‹ค ํฐ ๊ฐ’์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•ฉ๋‹ˆ๋‹ค.
    1. ๋จธ์ง€ ์†ŒํŠธ ํŠธ๋ฆฌ๋Š”, ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ์™€ ๊ฑฐ์˜ ๊ฐ™์€ ๋ฐฉ๋ฒ•์œผ๋กœ ๋งŒ๋“ค๋˜, ๊ฐ ํŠธ๋ฆฌ๊ฐ€ ๋จธ์ง€ ์†ŒํŠธ์˜ ์ค‘๊ฐ„ ๊ณผ์ •์„ ๋‹ด๊ณ  ์žˆ๋Š” ํŠธ๋ฆฌ์ž…๋‹ˆ๋‹ค.

    2. ์ฆ‰, ๊ฐ ํŠธ๋ฆฌ๊ฐ€ ์ •์ˆ˜๊ฐ’ ํ•˜๋‚˜๊ฐ€ ์•„๋‹Œ ์ž‘์€ ์ˆ˜์—ด์„ ๋“ค๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค.

    3. ์ด ํŠธ๋ฆฌ๊ฐ€ ์œ„ ๋ฌธ์ œ๋ฅผ ๋น ๋ฅด๊ฒŒ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์Œ์„ ๋ณด์ด์„ธ์š”. ๋ชฉํ‘œํ•˜๋Š” ์‹œ๊ฐ„๋ณต์žก๋„๋Š” ์ฟผ๋ฆฌ๋‹น $O(\log^2 n)$ ์ž…๋‹ˆ๋‹ค.

  4. Edit Distance : ํŽธ์ง‘ ๊ฑฐ๋ฆฌ๋ž€, ๋‘ ์ˆ˜์—ด $S, T$์— ๋Œ€ํ•ด, ๊ฐ’์˜ ์‚ฝ์ž…, ์‚ญ์ œ, ๋Œ€์ฒด ์—ฐ์‚ฐ์„ ์ด์šฉํ•˜์—ฌ $S$๋ฅผ $T$๋กœ ๋งŒ๋“ค๊ณ ์ž ํ•  ๋•Œ ํ•„์š”ํ•œ ์ตœ์†Œํ•œ์˜ ์—ฐ์‚ฐ ํšŸ์ˆ˜๋กœ ์ •์˜ํ•ฉ๋‹ˆ๋‹ค. ๊ฐ ์ˆ˜์—ด์˜ ๊ธธ์ด๊ฐ€ $m, n$ ์ผ ๋•Œ, ํŽธ์ง‘ ๊ฑฐ๋ฆฌ๋ฅผ $O(mn)$์— ๊ตฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ œ์‹œํ•˜์„ธ์š”.

  5. Longest Common Subsequence : ๋‘ ์ˆ˜์—ด $S, T$์— ๋Œ€ํ•ด, ๋‘ ์ˆ˜์—ด์ด ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ์ตœ๋Œ€ ๊ณตํ†ต ๋ถ€๋ถ„ ์ˆ˜์—ด์„ ๊ตฌํ•˜๊ณ ์ž ํ•ฉ๋‹ˆ๋‹ค. ๋‘ ์ˆ˜์—ด์˜ ๊ธธ์ด๊ฐ€ $m, n$์ผ ๋•Œ, LCS์˜ ๊ธธ์ด๋ฅผ $O(mn)$์— ๊ตฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ œ์‹œํ•˜์„ธ์š”.

  6. Longest Increasing Subsequence : ์–ด๋–ค ์ˆ˜์—ด $a_1, \dots a_n$ ์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ด ์ค‘ ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด (not necessarily contiguous) ์˜ ๊ธธ์ด๋ฅผ ๊ตฌํ•˜๊ณ ์ž ํ•ฉ๋‹ˆ๋‹ค.

    1. ์ž๋ช…ํ•œ DP์‹์„ ์ƒ๊ฐํ•ด ๋ด…์‹œ๋‹ค. ๊ฐ $i$์— ๋Œ€ํ•ด, $D_i$๋Š” $i$๋ฒˆ์งธ๋ฅผ ๋ ์›์†Œ๋กœ ํ•˜๋Š” ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด์˜ ๊ธธ์ด๋กœ ์ •์˜ํ•ฉ๋‹ˆ๋‹ค.

    2. ์ด์ œ, $D_i = \max_{j < i, A_j < A_i} D_j + 1$ ๋กœ ๊ณ„์‚ฐ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค.

    3. ์ด DP๋ฅผ ๊ทธ๋Œ€๋กœ ๊ณ„์‚ฐํ•˜๋ฉด $O(n^2)$ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆด ๊ฒƒ์ž…๋‹ˆ๋‹ค.

    4. ์ด๋ณด๋‹ค ๋น ๋ฅธ ์‹œ๊ฐ„ ๋ณต์žก๋„ $O(n \log n)$ ์„ ๋‹ฌ์„ฑํ•˜๋Š” ๋ฐฉ๋ฒ•์ด, ์ง€๊ธˆ๊นŒ์ง€ ๊ณต๋ถ€ํ•œ ๋‚ด์šฉ๋งŒ์œผ๋กœ 2๊ฐ€์ง€๊ฐ€ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค. ๋‘ ๊ฐ€์ง€๋ฅผ ์ œ์‹œํ•˜์„ธ์š”. 1

  7. Lowest Common Ancestor - Binary Lifting & Sparse Table : ํŠธ๋ฆฌ $T$์— ๋Œ€ํ•ด, ์ •์  $u, v$์˜ ์ตœ์†Œ ๊ณตํ†ต ์กฐ์ƒ์„ ๊ตฌํ•˜๊ณ ์ž ํ•ฉ๋‹ˆ๋‹ค.

    1. ๊ฐ€์žฅ ์ž๋ช…ํ•œ ๋ฐฉ๋ฒ•์€ ๋‘ ๋…ธ๋“œ๋ฅผ ๋ฃจํŠธ๊นŒ์ง€ ํƒ€๊ณ  ์˜ฌ๋ผ๊ฐ€๋ฉด์„œ ๋ชจ๋“  ์กฐ์ƒ ๋…ธ๋“œ๋ฅผ ์ฐพ์€ ๋’ค, ์กฐ์ƒ ๋…ธ๋“œ ๋ฒˆํ˜ธ์˜ ์ˆ˜์—ด์„ ๋ฃจํŠธ๋ถ€ํ„ฐ ๊ฑฐ๊พธ๋กœ ํ™•์ธํ•˜๋ฉด์„œ ์–ด๋””๊นŒ์ง€ ๊ฒน์น˜๋Š”์ง€ ํ™•์ธํ•˜๋Š” ๋ฐฉ๋ฒ•์ž…๋‹ˆ๋‹ค. ์ด๋Š” $O(n)$ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆฝ๋‹ˆ๋‹ค.

    2. ์•ฝ๊ฐ„์˜ Preprocessing์„ ํ†ตํ•ด, ๊ฐ ์ฟผ๋ฆฌ๋ฅผ $O(\log n)$ ์— ์ฒ˜๋ฆฌํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ์ดํ•ดํ•ด ๋ณด๊ณ ์ž ํ•ฉ๋‹ˆ๋‹ค.

    3. ๊ฐ ๋…ธ๋“œ $u$์˜ ๋ถ€๋ชจ ๋…ธ๋“œ๋ฅผ ์•ˆ๋‹ค๋ฉด, ๋ชจ๋“  ๋…ธ๋“œ์˜ 2๋Œ€ ๋ถ€๋ชจ ๋…ธ๋“œ๋ฅผ ๋น ๋ฅด๊ฒŒ ๊ตฌํ•  ์ˆ˜ ์žˆ์Œ์„ ์ดํ•ดํ•˜์„ธ์š”. ์ด๋ฅผ ํ™•์žฅํ•˜์—ฌ $2^{k-1}$ ๋ฒˆ์งธ ๋ถ€๋ชจ๋ฅผ ์•ˆ๋‹ค๋ฉด $2^{k}$ ๋ฒˆ์งธ ๋ถ€๋ชจ๋„ ์•Œ ์ˆ˜ ์žˆ์Œ์„ ์ดํ•ดํ•˜์„ธ์š”.

    4. ๋”ฐ๋ผ์„œ, par[x][i] ๋ฅผ $x$์˜ $2^i$๋ฒˆ์งธ ๋ถ€๋ชจ๋กœ ์ •์˜ํ•  ๋•Œ, ์ด ๋ฐฐ์—ด์„ ๋ชจ๋‘ ์ฑ„์šฐ๋Š” ๋ฐ $O(n \log n)$ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆฝ๋‹ˆ๋‹ค.

    5. ์ด ๋ฐฐ์—ด์„ ์ด์šฉ, $O(\log n)$ ์‹œ๊ฐ„์— ๊ฐ ์ฟผ๋ฆฌ์— ๋‹ตํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ์ œ์‹œํ•˜์„ธ์š”. ์ผ๋ฐ˜์„ฑ์„ ์žƒ์ง€ ์•Š๊ณ , ๊นŠ์ด๊ฐ€ ๊ฐ™์€ ๊ฒฝ์šฐ๋งŒ ๋ณด์—ฌ๋„ ๋จ์„ ๊ด€์ฐฐํ•˜์„ธ์š”.

    6. ๋ชฉํ‘œ๋Š” $u$ ์˜ $k$๋ฒˆ์งธ ๋ถ€๋ชจ๊ฐ€ $v$์˜ $k$๋ฒˆ์งธ ๋ถ€๋ชจ์™€ ๊ฐ™์€ ์ตœ์†Œ $k$ ์ฐพ๊ธฐ์ž…๋‹ˆ๋‹ค. $k$ ๋ฅผ ์ด์ง„์ˆ˜๋กœ ๋งž์ถ”๊ณ , par ๋ฐฐ์—ด๋กœ ์งœ ๋งž์ถฐ ๋ด…์‹œ๋‹ค.

  1. ํ•˜๋‚˜๋Š” Binary Search, ๋‹ค๋ฅธ ํ•˜๋‚˜๋Š” Segment Treeย โ†ฉ