์•Œ๊ณ ๋ฆฌ์ฆ˜

์•Œ๊ณ ๋ฆฌ์ฆ˜

    [Algorithm | Python] HeavyLight Decomposition (HLD)

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

    [๋ฐฑ์ค€ | BOJ] Good Bye, BOJ 2021! ํ›„๊ธฐ ๋ฐ ํ’€์ด (ABCD)

    ๋ฐฑ์ค€์—์„œ๋Š” ์—ฐ๋ง์— ๊ตฟ๋ฐ”์ด ๋ฐฑ์ค€, ์—ฐ์ดˆ์— ํ—ฌ๋กœ ๋ฐฑ์ค€(๊ตฟ๋ชจ๋‹ ๋ฐฑ์ค€) ํ–‰์‚ฌ๊ฐ€ ์žˆ๋‹ค. 2021 ๋ฐฑ์ค€ ๋งˆ๋ฌด๋ฆฌํ•  ๊ฒธ ๋ฌธ์ œํ’€์ด. ๋Œ€ํšŒ์—์„œ๋Š” 2์†”๋ธŒ, ๋๋‚˜๊ณ  CD ์—…์†”๋น™๊นŒ์ง€ ํ–ˆ๋‹ค. A. 2021์€ ๋ฌด์—‡์ด ํŠน๋ณ„ํ• ๊นŒ? $N$ ๋ฒ”์œ„๊ฐ€ $10,000$์ด๋‹ค. ์†Œ์ˆ˜๋ฅผ ์ญ‰ ๋Š˜์–ด๋†“๊ณ , ๋‘๊ฐœ๋ฅผ ๋ฏธ๋ฆฌ ๊ณฑํ•ด๋‘๊ณ  ์ด๋ถ„ํƒ์ƒ‰ํ•ด์„œ ํ’€์—ˆ๋‹ค. ์‚ฌ์‹ค ์ด๋ถ„ํƒ์ƒ‰์€ ํ•„์š”๊ฐ€ ์—†๋Š”๋ฐ. ์›์†Œ ๊ฐœ์ˆ˜๊ฐ€ 30๊ฐœ๊ฐ€ ์•ˆ ๋œ๋‹ค. ๋ฐฐ์—ด์„ ํ•œ ๋ฐ”ํ€ด ๋Œ ๊ฑธ. $N = 10,000$์ผ ๋•Œ 103๊นŒ์ง€ ๋„ฃ์–ด๋‘ฌ์•ผ ํ•˜๋Š”๋ฐ, ๋„ฃ์ง€ ์•Š์•„์„œ WA, ํ…Œ์ŠคํŠธํ•œ๋‹ต์‹œ๊ณ  ๋„ฃ์€ ์ฝ”๋“œ๋ฅผ ์•ˆ ์—†์• ์„œ WA. ์ž์ž˜ํ•œ ์‹ค์ˆ˜๋ฅผ ๋งŽ์ด ํ–ˆ๋‹ค. ์ œ์ถœ ์ „์—๋Š” ๊ผญ ์ฒดํฌํ•˜์ž. B. ์˜ˆ์œ ์ผ€์ดํฌ ๋Œ€ํšŒ ์ค‘์—๋Š” OEIS์˜ ํž˜์„ ๋ฐ›์•„์„œ ํ’€์—ˆ๋‹ค. ์†์œผ๋กœ ์ค„์ค„ ์“ฐ๋‹ค๊ฐ€ ๋ญ”๊ฐ€ ๊ทœ์น™์ด ์žˆ๋Š” ๊ฒƒ ๊ฐ™์•„์„œ ๋„˜๊ฒผ๋‹ค. ์ฆ๋ช…์€ ์•„๋ž˜์™€ ๊ฐ™๋‹ค. $N ..