์ „์ฒด ๊ธ€

์ „์ฒด ๊ธ€

    ICPC 2022 Seoul Regional ํ›„๊ธฐ

    ๋ง‰ํ•™๊ธฐ riroan, 3ํ•™๋…„ delena0702์™€ ํ•จ๊ป˜ ICPC 2022์— ์ฐธ๊ฐ€ํ–ˆ๋‹ค. ์›๋ž˜๋Š” UCPC(์ผ๊ฐํ˜ธ๋Š”์šฐ๋ฆฌ๊ฐ€์ง€ํ‚จ๋‹ค)๋ฅผ ํ•จ๊ป˜ ํ–ˆ๋˜ ์ผ€์ด(kth990303)์™€ ํ•จ๊ป˜ ์…‹์ด์„œ ํ˜ธํก์„ ๋งž์ถ˜ ์  ์žˆ์—ˆ๋Š”๋ฐ, ์˜ฌํ•ด ํœดํ•™์œผ๋กœ ์ฐธ๊ฐ€๋ฅผ ๋ชป ํ•ด์„œ ํ•œ ๋ช… ๊ตฌํ•˜๊ฒŒ ๋๋‹ค. ํ•œ ๋ช…์„ ๋ชจ์…”์˜ค๋Š” ๊ฑด ๋˜ ๋ช…๊ธฐํ˜•์ด ํ•œ ๊ฑด ํ–ˆ๋‹คใ…‹ใ…‹ใ…‹ ๋‚˜ํ•œํ…Œ ํ–ˆ๋˜ ์ˆ˜๋ฒ•์„ ๋˜‘๊ฐ™์ด ์จ์„œ ๋จนํ˜”๋‹ค.. ๋ฉ”์ผ ์ฃผ์†Œ๋„ ์ฐพ์•„๋ณด๊ธฐ ํž˜๋“ค์–ด์„œ github๋ฅผ ๋”ฐ๋ผ๊ฐ€ ํ”„๋กœํ•„ ๋ฆฌํฌ์— ์ด์Šˆ ๋‹ฌ์•„์„œ ์ฐพ์•„ ์™”๋‹ค. ์ด๊ฑธ๋กœ 100% ์„ฑ๊ณตํ•œ ๊ฑธ ๋ณด๋ฉด, ๋‚˜์ค‘์— ๋‚ด๊ฐ€ ์จ๋จน์–ด๋„ ์ •๋ง ์ข‹์„ ๋“ฏ..? ์˜ˆ์„ ์—์„œ ํ•œ ๋ฌธ์ œ๋„ ๋ชป ํ’€์—ˆ๋˜ ํ„ฐ๋ผ ๊ฝค๋‚˜ ๊ธด์žฅ์„ ๋งŽ์ด ํ–ˆ๊ณ .. ๊ต๋‚ด ๋Œ€ํšŒ๋ฅผ ์ค€๋น„ํ•˜๋Š๋ผ๊ณ  ๋ฆฌ์ €๋„ ์ค€๋น„๋ฅผ ๊ผผ๊ผผํ•˜๊ฒŒ ํ•˜์ง€ ๋ชปํ•œ ๊ฒŒ ์ฐธ ์•„์‰ฝ๋‹ค. ๊ทธ๋ž˜๋„ ์ง„์งœ์ง„์งœ ์ข‹์€ ๊ฒฝํ—˜์„ ํ•œ ๊ฒƒ ๊ฐ™์•„์„œ ๋ฟŒ๋“ฏํ•ด, ๋งŽ์€ ์‚ฌ..

    Longest Increasing Subsequence (LIS)๋ฅผ NlogN์— ๊ตฌํ•˜๊ธฐ

    ์ตœ์žฅ ์ฆ๊ฐ€ ๋ถ€๋ถ„ ์ˆ˜์—ด์ด๋ผ๊ณ  ๋ถˆ๋ฆฌ๋Š” Longest Increasing Subsequence๋Š” $O(NlogN)$ ์— ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค. ๋งŽ์€ ๋ธ”๋กœ๊ทธ์—์„œ ์ด๋ถ„ ํƒ์ƒ‰์„ ํ™œ์šฉํ•œ๋‹ค๋ผ๋Š” ํ•ด๊ฒฐ์ฑ…์„ ์ œ์‹œํ•˜๋Š”๋ฐ, ํ•ด๋‹น ํ’€์ด๋ฅผ ๋„์ถœํ•ด๋‚˜๊ฐ€๋Š” ๊ณผ์ •์„ ์ž์„ธํžˆ ์ž‘์„ฑํ•˜๊ณ ์ž ํ•œ๋‹ค. ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ฐ•์˜๋ฅผ ๋“ค์œผ๋ฉฐ ์ •๋ฆฌํ•œ ๋‚ด์šฉ์œผ๋กœ, ์˜ค๋ฅ˜๊ฐ€ ์žˆ์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋ฐœ๊ฒฌํ•˜์‹ ๋‹ค๋ฉด ๋Œ“๊ธ€๋กœ ์•Œ๋ ค์ฃผ์‹œ๋ฉด ๊ฐ์‚ฌํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค ๐Ÿ™Œ 0. Longest Increasing Subsequence LIS๋Š” ์ฃผ์–ด์ง„ ์ˆ˜์—ด์—์„œ ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด์ด๋‹ค. ์ฃผ์–ด์ง„ ์ˆ˜์—ด์„ $S$ ๋ผ๊ณ  ํ•˜๊ณ , LIS๋ฅผ $L$ ๋ผ๊ณ  ํ•˜์ž. ์ด๋•Œ, $L$ ์˜ ์›์†Œ๋“ค์ด $S$์—์„œ ์—ฐ์†์ ์œผ๋กœ ์กด์žฌํ•ด์•ผํ•  ํ•„์š”๋Š” ์—†๋‹ค. LIS๋Š” ์–ด๋–ป๊ฒŒ ๊ตฌํ•ด์•ผ ํ• ๊นŒ? 1. Naive ๊ฐ„๋‹จํžˆ ์ƒ๊ฐํ•˜๋ฉด, ๋ชจ๋“  ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๋‹ค ๋”ฐ์ ธ..

    Minimum Spanning Tree ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์ฆ๋ช…

    MST๋ฅผ ์•Œ๊ณ  ์žˆ๊ณ , ํฌ๋ฃจ์Šค์นผ๊ณผ ํ”„๋ฆผ์„ ์•Œ๊ณ  ์žˆ์ง€๋งŒ ๊ทธ๋ƒฅ ์“ฐ๊ณ ์žˆ์ง€ ์•Š์€๊ฐ€? ์ด ๊ธ€์„ ํ†ตํ•ด์„œ "์™œ ๋ผ?" ์— ๋Œ€ํ•œ ํ•ด๋‹ต์„ ์ฐพ์„ ์ˆ˜ ์žˆ์—ˆ์œผ๋ฉด ์ข‹๊ฒ ๋‹ค. ๊ทธ๋ž˜ํ”„๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ๋ชจ๋“  ๋…ธ๋“œ๋ฅผ ์—ฐ๊ฒฐํ•˜๋Š” ํŠธ๋ฆฌ๋ฅผ Spanning Tree๋ผ๊ณ  ํ•˜๊ณ , ์ด ์ค‘์—์„œ ๊ฐ€์žฅ ๊ฐ„์„ ์˜ ๊ฐ€์ค‘์น˜์˜ ํ•ฉ์ด ๋‚ฎ์€ ํŠธ๋ฆฌ๋ฅผ Minimum spanning tree(์ดํ•˜ MST)๋ผ๊ณ  ํ•œ๋‹ค. MST๋ฅผ ๋งŒ๋“œ๋Š” ๋ฐฉ๋ฒ•์œผ๋กœ๋Š” Prim, Kruskal ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ ๋‘ ๊ฐ€์ง€๊ฐ€ ์žˆ์œผ๋ฉฐ, ๊ฐ๊ฐ $O(ElogV), O(ElogE)$ ๊ฐ€ ์†Œ์š”๋œ๋‹ค. (๊ทธ๋ž˜ํ”„๊ฐ€ denseํ•  ์ˆ˜๋ก $E$ ๋Š” $V^2$ ์— ๊ฐ€๊นŒ์›Œ์ง€๋ฉฐ, $O(ElogE) = O(ElogV^2) = O(2ElogV)$ ๋กœ ๋น„์Šทํ•œ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง„๋‹ค.) ๋‘ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ชจ๋‘ ๊ทธ๋ฆฌ๋””๋กœ ์ง„ํ–‰ํ•˜๋ฉฐ, ๋‘ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์ฆ๋ช… ..

    [TDD | Python] Test-Driven-Development 1-3์žฅ

    TDD(Test-Driven-Development, ํ…Œ์ŠคํŠธ ์ฃผ๋„ ๊ฐœ๋ฐœ)๋ฅผ ๊ณต๋ถ€ํ•˜๊ธฐ ์œ„ํ•ด์„œ Test-Driven-Development with Python์„ ์ฝ์œผ๋ฉด์„œ ๊ฐœ๋…์„ ์ตํžˆ๊ณ  ์žˆ๋‹ค. ๊ฐœ๋ฐœ์„ ํ•  ๋•Œ, ํ…Œ์ŠคํŠธ๋Š” ๊ฝค๋‚˜ ์ค‘์š”ํ•˜๋‹ค. ์‚ฌ์šฉ์ž๊ฐ€ ํ•ญ์ƒ ๋‚˜์˜ ํ”„๋กœ์ ํŠธ์— '์ด์ƒ์ ์œผ๋กœ' ์ ‘๊ทผํ–ˆ์œผ๋ฉด ์ข‹๊ฒ ์ง€๋งŒ, ์‹ค์ƒ์€ ๊ทธ๋ ‡์ง€ ์•Š๋‹ค. ์šฐ๋ฆฌ๋Š” ํ•ญ์ƒ ์ตœ์•…์˜ ์ƒํ™ฉ์„ ์ƒ๊ฐํ•˜๊ณ , ๊ทธ์— ๋Œ€ํ•œ ๋Œ€๋น„๊ฐ€ ์™„๋ฒฝํ•˜๊ฒŒ ๋˜์–ด์žˆ์–ด์•ผ ํ•œ๋‹ค. TDD๋Š” ๊ทธ๋Ÿฌํ•œ ํ…Œ์ŠคํŠธ๋“ค์„ ๋งŒ๋“ค์–ด ๋‘๊ณ , ํ•ด๋‹น ํ…Œ์ŠคํŠธ๊ฐ€ ํ†ต๊ณผํ•˜๊ฒŒ๋” ์ฝ”๋“œ๋ฅผ ์งœ๊ฒŒ ํ•œ๋‹ค. ์ฝ”๋“œ๋ฅผ ์ง  ๋’ค ํ…Œ์ŠคํŠธ๋ฅผ ํ•˜๋Š” ๊ฒŒ ์•„๋‹ˆ๋ผ, ํ…Œ์ŠคํŠธ๋ฅผ ์ง  ๋’ค ์ฝ”๋“œ๋ฅผ ์ง ๋‹ค. ์–ด๋–ป๊ฒŒ ๋ณด๋ฉด ๋‚˜๋Š” TDD๋ฅผ ์ด๋ฏธ ๊ฒฝํ—˜ํ•ด ๋ณด์•˜์„์ง€๋„ ๋ชจ๋ฅธ๋‹ค. ์˜จ๋ผ์ธ ์ €์ง€ ๋ฌธ์ œ๋“ค์„ ๋งŽ์ด ํ’€์–ด๋ณธ ์ž…์žฅ์œผ๋กœ, ๋ฌธ์ œ๊ฐ€ ํ‹€๋ ธ์„ ๋•Œ, ํ…Œ์ŠคํŠธ์ผ€์ด์Šค(๋ฐ˜๋ก€)๋ฅผ ๋งŒ๋“ค๊ณ , ํ•ด๋‹น..

    [Tex | MathJax] Tex ๋ฌธ๋ฒ•์„ Tistory์—์„œ ํ˜ธํ™˜์„ฑ ์žˆ๊ฒŒ ์‚ฌ์šฉํ•˜๊ธฐ (๋ชจ๋ฐ”์ผ, PC)

    ๋งŽ์€ ๋ธ”๋กœ๊ทธ์—์„œ $\LaTeX$ ์—์„œ ์‚ฌ์šฉํ•˜๋Š” Tex ๋ฌธ๋ฒ•์„ ์ ์šฉํ•˜๊ธฐ ์œ„ํ•ด MathJax๋ฅผ ์‚ฌ์šฉํ•œ๋‹ค. MathJax๋Š” ์ˆ˜์‹์„ ์‚ฌ์šฉํ•˜๋Š” Tex ๋ฌธ๋ฒ•์„ ์›น ํŽ˜์ด์ง€์— ๋ Œ๋”ํ•  ์ˆ˜ ์žˆ๋„๋ก ๋งŒ๋“  JS ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ์ด๋‹ค. y = ax ์™€ ๊ฐ™์€ ์ˆ˜์‹์„ $$y = ax$$ ๋ณด๊ธฐ ์ข‹๊ฒŒ ๋ Œ๋”๋งํ•ด์ฃผ๋Š” ์—ญํ• ์„ ํ•œ๋‹ค. 0. TL;DR (์š”์•ฝ) ์•„๋ž˜ ์ฝ”๋“œ๋ฅผ HTML ์— ๋„ฃ์œผ๋ฉด ๋ชจ๋ฐ”์ผ / PC ํ™˜๊ฒฝ์— ์ƒ๊ด€์—†์ด ์ž˜ ์ž‘๋™ํ•œ๋‹ค. 1. MathJax 3.0์„ ๋ธŒ๋ผ์šฐ์ €์— ํƒ‘์žฌํ•˜๊ธฐ ์—ฌ๋Ÿฌ ๋ธ”๋กœ๊ทธ์—์„œ MathJax 2.x๋ฒ„์ „์„ ์†Œ๊ฐœํ•˜๊ณ  ์žˆ๋‹ค. ํ˜„์žฌ MathJax๊ฐ€ ์ง€์›ํ•˜๋Š” ์ตœ์‹  ๋ฒ„์ „์€ 3.0์ด๋‹ค! ๋ฒ„์ „ 2์™€๋Š” ๋งŽ์ด ๋‹ค๋ฅธ configuration์„ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค๊ณ  ํ•œ๋‹ค. ์ด ๊ธ€์—์„œ๋Š” ์ตœ์‹  ๋ฒ„์ „์— ํ•ด๋‹นํ•˜๋Š” MathJax๋ฅผ ์„ค์น˜ํ•˜๊ฒ ๋‹ค. ์˜๋ฌธ document..

    [algorithm] ์ˆ˜ํ•™์  ๊ท€๋‚ฉ๋ฒ•์„ ์‚ฌ์šฉํ•ด ์žฌ๊ท€๋ฅผ ์ฆ๋ช…ํ•˜๊ธฐ

    0. ๊ธ€์„ ์“ฐ๋Š” ์ด์œ ์™€ ์žก๋‹คํ•œ ์ด์•ผ๊ธฐ ์ด๋ฒˆ ํ•™๊ธฐ์—๋Š” ์ด๋ผ๋Š” ๊ณผ๋ชฉ์„ ์ˆ˜๊ฐ•ํ•œ๋‹ค. ๋‚˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ํ†ตํ•œ ๋ฌธ์ œํ•ด๊ฒฐ(Problem Solving)์— ๊ด€์‹ฌ์ด ๋งŽ์•„์„œ ํ˜ผ์ž ์—ฌ๋Ÿฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜๋“ค์„ ๊ณต๋ถ€ํ•ด์™”๋‹ค. ๊ตฐ๋Œ€๋ฅผ ๋‹ค๋…€์˜ค๊ธฐ ์ „, ์ƒˆ๋‚ด๊ธฐ ์‹œ์ ˆ์—๋Š” ๋™์•„๋ฆฌ ๋‚ด์—์„œ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋Œ€ํšŒ๋ฅผ ์—ด์–ด ๋ฌธ์ œ๋ฅผ ์ถœ์ œํ•˜๊ธฐ๋„ ํ–ˆ์—ˆ๋‹ค. ์ฝ”๋กœ๋‚˜์˜ ์—ฌํŒŒ๊ฐ€ ๊ฐ€์‹œ์งˆ ์•Š์•„ ์ด๋ฒˆ ํ•™๊ธฐ๋„ ๋Œ€๋ถ€๋ถ„์˜ ๊ณผ๋ชฉ๋“ค์ด ๋น„๋Œ€๋ฉด์œผ๋กœ ์ง„ํ–‰ํ–ˆ๊ณ , ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋˜ํ•œ ๊ทธ๋žฌ๋‹ค. 1์ฃผ์ฐจ ๊ฐ•์˜๋ฐ–์— ๋“ฃ์ง€ ์•Š์•˜์ง€๋งŒ, ๋Š๋‚€ ๊ฒŒ ๊ฝค๋‚˜ ๋งŽ๋‹ค. ๋‚˜์˜ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ณต๋ถ€๋ฒ•์ด ์™„๋ฒฝํ•˜๊ฒŒ ํ‹€๋ ธ๋‹ค๊ณ  ํ•  ์ˆ˜ ์žˆ์„ ์ •๋„์˜€๋‹ค. ์—ฌ๋Ÿฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์œ ํ˜•์˜ ๋ฌธ์ œ๋“ค์„ ํ’€์–ด์™”์ง€๋งŒ, ๋ฌธ์ œ์— ๋Œ€ํ•œ ์ •๋‹น์„ฑ์ด๋‚˜ ์ฆ๋ช…์„ ๋Ÿฌํ”„ํ•˜๊ฒŒ ๋„˜๊ธฐ๊ฑฐ๋‚˜, ํ”ํžˆ๋“ค ๋งํ•˜๋Š” Proof by AC (๋งž์•˜์Šต๋‹ˆ๋‹ค๋กœ ์ฆ๋ช…ํ•˜๊ธฐ)๋กœ ํ‰์ณค๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค. ์ง€๊ธˆ ์ƒ๊ฐํ•ด ๋ณด๋ฉด ๊ต‰์žฅํžˆ ๋‚˜..

    [Python] Offline Dynamic Connectivity - ๋™์  ์—ฐ๊ฒฐ์„ฑ ๋ฌธ์ œ๋ฅผ ์˜คํ”„๋ผ์ธ์œผ๋กœ ํ•ด๊ฒฐํ•˜๊ธฐ

    ๊ทธ๋ž˜ํ”„ ๋ฌธ์ œ์—์„œ, Dynamic Connectivity Problem์ด๋ผ๊ณ  ํ•˜๋Š” ๊ฒƒ์€ ๋‹ค์Œ ์„ธ ๊ฐ€์ง€ ์ฟผ๋ฆฌ๋ฅผ ํ•ด๊ฒฐํ•˜๋Š” ๋ฌธ์ œ๋ฅผ ์˜๋ฏธํ•œ๋‹ค. 1. ๋‘ ์ •์  $u$, $v$ ๋ฅผ ์ž‡๋Š” ๊ฐ„์„ ์„ ์ถ”๊ฐ€ํ•œ๋‹ค 2. ๋‘ ์ •์  $u$, $v$ ๋ฅผ ์ž‡๋Š” ๊ฐ„์„ ์„ ์ œ๊ฑฐํ•œ๋‹ค 3. ์ •์  $u$ ์—์„œ $v$ ๋กœ ๋„๋‹ฌ ๊ฐ€๋Šฅํ•œ์ง€ ํ™•์ธํ•œ๋‹ค ๋‹จ์ˆœํ•˜๊ฒŒ 1, 3๋ฒˆ ์ฟผ๋ฆฌ๋กœ๋งŒ ์ด๋ฃจ์–ด์ง„ ๋ฌธ์ œ์ด๊ฑฐ๋‚˜, 2-3๋ฒˆ ์ฟผ๋ฆฌ๋กœ๋งŒ ์ด๋ฃจ์–ด์ง„ ๋ฌธ์ œ๋ผ๋ฉด Disjoint-Set Union(DSU) ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ์‚ฌ์šฉํ•ด์„œ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋‹ค. ๊ฐ„์„ ์„ ์ถ”๊ฐ€ํ•˜๊ณ  ์ œ๊ฑฐํ•˜๋ฉด์„œ ๊ทธ์™€ ๋™์‹œ์— ์ •์  ์‚ฌ์ด์— ๊ฒฝ๋กœ๊ฐ€ ์žˆ๋Š”์ง€ ํ™•์ธํ•˜๋ ค๋ฉด.. ๊ฝค๋‚˜ ์–ด๋ ค์šธ ๊ฒƒ ๊ฐ™๋‹ค. ์ด๋Ÿฐ ์‹์˜ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๋Š” ๋ฐฉ๋ฒ•์€ ํฌ๊ฒŒ ๋‘ ๊ฐ€์ง€๊ฐ€ ์žˆ๋‹ค๊ณ  ์ƒ๊ฐํ•˜๋Š”๋ฐ, ํ•˜๋‚˜๋Š” (๋‚ด๊ฐ€ ๋ชจ๋ฅด๋Š”) ์ž๋ฃŒ๊ตฌ์กฐ๋‚˜ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•ด์„œ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๋Š” ..

    UCPC 2022 ๋ณธ์„  ํ›„๊ธฐ

    ์˜ˆ์„ ์„ ์šด์ข‹๊ฒŒ ์ง„ํ–‰ํ•œ ๋•๋ถ„์— ๋ณธ์„ ์„ ์ž˜ ๋ณด๊ณ  ์™”๋‹ค! ์ธํ„ฐ๋„ท์œผ๋กœ ๋Œ์•„๋‹ค๋‹ˆ๋ฉด์„œ ๊ตฌ๊ฒฝํ–ˆ๋˜ ํ’์„  ๋‹ฌ๊ธฐ, ๋‹จ์ฒด ํ‹ฐ์…”์ธ  ์ž…๊ธฐ, ๊ฐ„์‹ ๋จน์œผ๋ฉด์„œ ๋ฌธ์ œํ’€๊ธฐ ๋“ฑ๋“ฑ.. ๋‹ค์–‘ํ•œ ์‚ฌ๋žŒ๋“ค์ด ๋ชจ์—ฌ์„œ ๊ฐ™์€ ๋ชฉํ‘œ๋ฅผ ๊ฐ€์ง€๊ณ  ์˜ค๋žœ ์‹œ๊ฐ„๋™์•ˆ ๊ณ ๋ฏผํ•œ๋‹ค๋Š” ๊ฒŒ ์ฐธ ๋งค๋ ฅ์ ์ด๋‹ค. ์šฐ๋ฆฌ ํŒ€์€ ์ด 12๋ฌธ์ œ ์ค‘์— 4๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•ด์„œ 41์œ„๋ฅผ ์ฐจ์ง€ํ–ˆ๋‹ค! ๋ณธ์„  ์ง„์ถœ ํŒ€์ด 53ํŒ€์ด๋ผ ๋†’์€ ์ˆœ์œ„๋Š” ์•„๋‹ˆ์—ˆ์ง€๋งŒ, ์ด์ œ ์‹œ์ž‘์ด๋ผ๋Š” ์ƒ๊ฐ์œผ๋กœ ์ฆ๊ธฐ๊ณ  ์™”๋‹ค. ๋Œ€ํšŒ๋Š” ์‚ผ์„ฑ์—ญ ์ฃผ๋ณ€ ์ง€ํ•˜ ๋Œ€๊ด€ํ™€์—์„œ ์ง„ํ–‰๋๋‹ค. ์Šคํƒญ ๋ถ„๋“ค๊ป˜์„œ๋Š” ๋‹ค๋“ค ๋ชฉ๊ฑธ์ด๋ฅผ ๋ฏธ๋ฆฌ ํ•˜๊ณ  ๊ณ„์…จ๋Š”๋ฐ, ๋ฐฑ์ค€์—์„œ ์ž์ฃผ ๋ดค๋˜ ์•„์ด๋””๋“ค์ด ๋ชฉ์— ๊ฑธ๋ ค์žˆ๋Š” ๊ฑธ ๋ณด๊ณ  ์ •๋ง ๋†€๋ž๋‹ค. ์ธ์‚ฌ๋ฅผ ํ•˜๊ณ  ์‹ถ์—ˆ์ง€๋งŒ ์ •๋ง์ •๋ง ๋ฐ”๋น  ๋ณด์—ฌ์„œ ๋ง ๊ฑธ๊ธฐ๋„ ์–ด๋ ค์› ๋‹ค ๐Ÿ™„ ์„ธ๋ช…์ด์„œ ํ•˜๋‚˜์˜ ๋…ธํŠธ๋ถ์œผ๋กœ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•ด์•ผ ํ–ˆ์–ด์„œ, ์ข…์ด๋ฅผ ๋ณด๋ฉด์„œ ํ’€์ด๋ฅผ ๋– ์˜ฌ๋ฆฌ๊ณ  ์ฝ”๋”ฉ..

    UCPC 2022 ์˜ˆ์„  ํ›„๊ธฐ

    ์–ด๋–ป๊ฒŒ ๊ฐ™์€ ํ•™๊ต์—์„œ ์ธ์—ฐ์ด ๋งž์•„ ํ•จ๊ป˜ ์ฐธ๊ฐ€ํ•œ UCPC, ๋ช‡๋ฒˆ ๋งŒ๋‚˜ ์—ฐ์Šต์…‹๋„ ํ’€์—ˆ๋‹ค ์ด๋ฒˆ์— 2์‹œ๋ถ€ํ„ฐ 3์‹œ๊ฐ„๋™์•ˆ ์˜ˆ์„ ์ด ์ง„ํ–‰๋๋Š”๋ฐ, ์–ดํ›„ ์ด๊ฑฐ ์ง„์งœ ๋„ˆ๋ฌด ์–ด๋ ต๋‹ค A ๋Š” ๊ธฐ๋ณธ ์ž…์ถœ๋ ฅ ๋ฌธ์ œ๋ผ์„œ ๋ฐ”๋กœ ํƒœํ˜„๋‹˜์ด ์†”๋ธŒ G ์ฝ์–ด๋ณด๋‹ค๊ฐ€ ํ• ๋งŒํ•œ ๊ฒƒ ๊ฐ™์•˜๋Š”๋ฐ ์ˆœ์„œ ๊ตฌ๋ถ„ํ•˜๋Š” ๊ฑธ ๋‚˜์ค‘์— ์•Œ์•„์ฑ„์„œ ํŒจ์Šค B ๋ณด๋‹ค๊ฐ€ CCW ๋„ฃ์œผ๋ฉด ๋  ๊ฒƒ ๊ฐ™์•„์„œ ๊ฑด๋“œ๋ฆฌ๋‹ค๊ฐ€ ํƒœํ˜„๋‹˜ํ•œํ…Œ ๋„˜๊ธฐ๊ณ  F ๊ตฌํ˜„ ๋ช‡๋ฒˆ ํ‹€๋ฆฌ๊ณ  AC (๋ฏฟ์Œ์˜ ์ œ์ถœ์„ ํ–ˆ์–ด์•ผ ํ–ˆ๋‹ค,,,). ์ด๋•Œ ํƒœํ˜„๋‹˜์ด B๋„ ๊ฐ™์ด ํ•ด๊ฒฐํ•ด ์ฃผ์…จ์Œ E, J๋Š” ๋ช…๊ธฐ๋‹˜์ด ํ•ด๊ฒฐ. :fan: ๋๋‚˜๊ธฐ ์ „์— D๋ฅผ ์˜คํ”„๋ผ์ธ์ฟผ๋ฆฌ + ๋ ˆ์ด์ง€์„ธ๊ทธ + ์ด๋ถ„ํƒ์ƒ‰์œผ๋กœ ํ’€๋‹ค๊ฐ€ ์‹œ๊ฐ„ ์—†์–ด์„œ ๋ชป ํ’€๊ฒŒ ๋๋‹ค. (์ด๋ ‡๊ฒŒ ํ‘ธ๋Š” ๊ฑฐ ๋งž์•„์š”..?) 5์†”๋ธŒ๋ฅผ ํ•ด์„œ ์•„์Šฌ์•„์Šฌํ•œ ๊ณณ์— ์œ„์น˜ํ–ˆ๋‹ค. UCPC ๊ผญ ๋‚˜๊ฐ€๋ณด๊ณ  ์‹ถ์—ˆ๋Š”๋ฐ ์ƒ๊ฐ๋ณด๋‹ค ์ข‹์€ ์„ฑ์ ์„ ..

    [Algorithm | Python] HeavyLight Decomposition (HLD)

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