์ ์ฒด ๊ธ
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 ๊ฐ๋จํ ์๊ฐํ๋ฉด, ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๋ค ๋ฐ์ ธ..
[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..
[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..
[Codeforces] Round #784 Div. 4
์ฒ์์ผ๋ก ์ฌ์๋ธ๋ฅผ ํ๋ค ! ๋งค๋ฒ ์ฝํฌ ์น๋ค๊ฐ ์ผ์ด ์๊ฒจ์ ์ ์๊ฐ ๋ฐ๋ฅ์ผ๋ก ๊ณ ๊พธ๋ผ์ก๋๋ฐ, ์ด๋ฒ์ ์ ๋๋ก ์ง์คํด์ ํ์ด๋ดค๋ค. A. Division? ๋จ์ ์กฐ๊ฑด๋ฌธ์ผ๋ก ํ๋จํ๋ค. B. Triple $N