ํ๋ฅด๋“œ

ํ๋ฅด๋“œ

    [Algorithm | Python] HeavyLight Decomposition (HLD)

    ใ…Žใ„นใ„ท ์˜ฌ๋ ค์•ผ์ง€, ์˜ฌ๋ ค์•ผ์ง€ ํ•˜๊ณ  ํ•˜๋˜ ๊ฑธ ์ด์ œ์•ผ ์ •๋ฆฌ. ์•„์ง ์™„์„ฑ๋˜์ง€ ์•Š์•˜๋‹ค HeavyLight Decomposition (HLD)๋Š” ํŠธ๋ฆฌ์—์„œ์˜ ์ฟผ๋ฆฌ๋ฅผ ํšจ์œจ์ ์œผ๋กœ ์ˆ˜ํ–‰ํ•˜๋„๋ก ํ•˜๋Š” ํ…Œํฌ๋‹‰์ด๋‹ค. ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋‘ ์ฟผ๋ฆฌ๊ฐ€ ์žˆ๋‹ค. 1. ํŠธ๋ฆฌ์˜ ์ •์  $u$ ์—์„œ $v$ ๋กœ ๊ฐ€๋Š” ๊ฒฝ๋กœ ์ค‘ ๊ฐ€์žฅ ํฐ ๊ฐ€์ค‘์น˜๋ฅผ ๊ฐ€์ง„ ์ •์ ์„ ์ฐพ๋Š” ์ฟผ๋ฆฌ 2. ์ •์ ์˜ ๊ฐ€์ค‘์น˜๋ฅผ ๋ฐ”๊พธ๋Š” ์ฟผ๋ฆฌ ๋ฐฐ์—ด์—์„œ ์œ„ ์ฟผ๋ฆฌ๋“ค์„ ์ฒ˜๋ฆฌํ•˜๋Š” ๊ฒƒ์€ ๊ฐ„๋‹จํ•˜๋‹ค. ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ๋‚˜ ํŽœ์œ… ํŠธ๋ฆฌ๋ฅผ ์‚ฌ์šฉํ•˜๋ฉด $O(QlogN)$์— ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋‹ค. ํ•˜์ง€๋งŒ ์ด๋Š” ๋ฐฐ์—ด์ด ์„ ํ˜•์ธ ์ ์„ ํ™œ์šฉํ•œ ํ’€์ด๋ฒ•์ด๊ธฐ์—, ๋น„์„ ํ˜• ์ž๋ฃŒ๊ตฌ์กฐ์ธ ํŠธ๋ฆฌ์—๋Š” ์ ์šฉํ•  ์ˆ˜ ์—†๋‹ค. ํŠธ๋ฆฌ๋ฅผ ์ ๋‹นํžˆ ๋‚˜๋ˆ ์„œ, ๋‚˜๋ˆˆ ๊ตฌ๊ฐ„์„ ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ๋กœ ๊ด€๋ฆฌํ•˜๋ฉด ์–ด๋–จ๊นŒ? ๋ผ๋Š” ๋ฐœ์ƒ์—์„œ ๋‚˜์˜จ ๊ฒŒ ์˜ค๋Š˜ ๋‹ค๋ฃฐ HeavyLight Decompos..