์ ์ฒด ๊ธ
[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
Dependency Inversion Principle - ์์กด๊ด๊ณ ์ญ์ ์์น์ ๋ํด์
๊ฐ์ฒด์งํฅ ์ค๊ณ SOLID 5์์น ์ค์์ ๋ง์ง๋ง ์์น์ ํด๋นํ๋ DI (Dependency Inversion Principle)์ ๋ํด์ ์์๋ณด์. ๊ฐ์ฒด์งํฅ์ ์ค๊ณ์๋ ์์กด๊ด๊ณ๊ฐ ์๊ธฐ๊ธฐ ๋ง๋ จ์ด๋ค. ๊ฐ ํด๋์ค๋ ๋จ์ผ ์ฑ ์ ์์น์ ๋ฐ๋ผ ํ๋์ ์ฑ ์๋ง ์ ธ์ผ ํ๊ณ , ๊ฐ ํด๋์ค๊ฐ ๊ฒฐํฉ๋ผ ํ๋ก๊ทธ๋จ์ด ๊ตฌ๋๋๋ค๋ ๊ฒ์ ๋ณด๋ฉด, ์ด๋ค ํด๋์ค๊ฐ ๋ค๋ฅธ ํด๋์ค์ ์์กดํ๋ ๊ฒ์ ๋น์ฐํ๋ค. class Dog: def speak(self): print("Bark") class Cat: def speak(self): print("Meow") class Zoo: def __init__(self): self.cat = Cat() self.dog = Dog() def speak_all(self): self.cat.speak() self.do..
[Codeforces] Round #773 Div. 2
์์ฆ ์ฝ๋ํฌ์ค๋ฅผ ๋๋ฆฌ๊ณ ์๋๋ฐ, ์ด๋ ต๋ค,, Div2 4๊ฐ ํธ๋ ๊ฑธ ๋ชฉํ๋ก ๋ฌ๋ฆฌ๊ณ ์๋ค๋ง, ๊ณ์ํด์ ABC๋ฅผ ํ๊ฑฐ๋ ABE๋ฅผ ํ๊ฑฐ๋(???)... A. Hard Way ์ผ๊ฐํ์ด ์ฃผ์ด์ก์ ๋, $(0, x)$ ์ ์์ ์ผ๊ฐํ์ ๋ฟ์ง ์๋ ๋ณ์ ๊ธธ์ด๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ์ด๋ค. ๊ทธ๋ฆผ์ ๋ช ๋ฒ ๊ทธ๋ ค ๋ณด๋ฉด, ์ผ๊ฐํ์ ํ ๋ณ์ด x์ถ์ ํํํ๊ณ , ๋๋จธ์ง ํ ์ ์ด ๊ทธ ๋ณ๋ณด๋ค ์๋์ ์๋ ๊ฒฝ์ฐ, x์ถ์ ํํํ ๋ณ์ ๋ฟ์ ์ ์๋ค. ๋คํํ ๋ฟ์ง ์๋ ๋ณ์ ๊ธธ์ด๋ฅผ ๊ตฌํ๋ฉด ๋๋, ์ ๊ฒฝ์ฐ๋ฉด ๋ณ์ ๊ธธ์ด๋ฅผ, ๊ทธ๋ ์ง ์์ผ๋ฉด 0์ ์ถ๋ ฅํ๋ฉด ๋๋ค. B. Power Walking $N$ ๊ฐ์ ํ์์ ์ ์ ๋นํ ๋๋ ์, ๋๋ ๊ทธ๋ฃน๋ง๋ค uniqueํ ์์์ ๊ฐ์์ ํฉ์ ์ต์ํํ๋ ๋ฌธ์ ์ด๋ค. ์ด ๋, $1$ ๋ถํฐ $N$ ๊น์ง์ ์ ์ $K$ ์ ๋ํด์, ..
[ํ์ด์ฌ | Python] Mutable object, Immutable object
ํ์ด์ฌ์ ๋ชจ๋ ๊ฒ์ ๊ฐ์ฒด(object)์ด๋ค. ๊ฑฐ์ ๋ชจ๋ ๊ฐ์ฒด๋ ์์ฑ(attributes)๊ณผ ๋ฉ์๋(methods)๋ก ์ด๋ฃจ์ด์ ธ ์์ผ๋ฉฐ, ๊ฐ์ฒด๋ผ๋ฆฌ์ ์๋ณ์ id(object)๋ฅผ ํตํด์ ํ๋ค. id๊ฐ ๊ฐ๋ค๋ฉด ๋์ผํ ๊ฐ์ฒด, ๊ทธ๋ ์ง ์์ผ๋ฉด ๋ค๋ฅธ ๊ฐ์ฒด์ด๋ค. id๋ ํด๋น ๊ฐ์ฒด๋ฅผ ๊ฐ๋ฆฌํค๋ ์ ์ผํ ์์(unique constant)์ด๋ฉฐ, ๊ฐ์ฒด๊ฐ ์๋ก ๊ฐ์์ง ๋น๊ต๋ฅผ ์ํด์๋ $==$ ๊ฐ ์๋ is ๋ฅผ ์ฌ์ฉํ๋ค. C์ธ์ด์ ํฌ์ธํฐ์ ๊ฐ์ ๊ฐ๋ ์ด์ง๋ง, ์ค์ ๋ก id๊ฐ ๊ฐ๋ฆฌํค๋ ๊ฒ์ด ๋ฉ๋ชจ๋ฆฌ์ ์ฃผ์๋ฅผ ์๋ฏธํ๋ ๊ฒ์ ์๋๋ค. ๊ฐ์ฒด๋ ๋ณ๊ฒฝ ๊ฐ๋ฅํ๊ฑฐ๋, ๊ทธ๋ ์ง ์๋ค. ์ด๊ฒ์ด mutable object์ immutable object์ ์ฐจ์ด์ด๋ค. ์ฌ์ด ์๋ก, a = "abc" a.replace("a", "x") # a๋ ์ฌ์ ํ "abc"์ด..
[๊น | Git] Udacity Git Commit Message Style Guide - ๊น ์ปค๋ฐ ๋ฉ์์ง ์ผ๊ด์ฑ์๊ฒ ์ฐ๊ธฐ (์คํ์ผ ๊ฐ์ด๋)
์ปค๋ฐ ๋ฉ์์ง๊ฐ ๋ณด๊ธฐ ์ข์์ผ (์ผ๊ด์ฑ์๊ณ ์ฒด๊ณ์ ์ผ๋ก ์์ฑํด์ผ) ๋์ค์ ๋ค์ ๋ณด์์ ๋ ์ด๋ค ๊ธฐ๋ฅ์ ์ถ๊ฐํ๋์ง, ์ด๋ค ๋ฒ๊ทธ๋ฅผ ๊ณ ์ณค๋์ง ์๊ธฐ ํธํ๋ค. ์ต๊ทผ์ ์ฝ๋๋ฅผ ์ฒด๊ณ์ ์ผ๋ก ์์ฑํ๊ธฐ ์ํด์ Java, Python์ Style Guide๋ฅผ ์ฐธ๊ณ ํ์๋๋ฐ, ์ปค๋ฐ ๋ฉ์์ง์๋ ๊ฐ์ด๋๋ผ์ธ์ด ์๋ค! ์ค๋์ ๊ทธ ์ค์์ ์ ๋ค์ํฐ์ ์ปค๋ฐ๋ฉ์์ง ์คํ์ผ๊ฐ์ด๋๋ฅผ ์๊ฐํ๋ค. - Commit Message Structure (์ปค๋ฐ ๋ฉ์์ง ๊ตฌ์กฐ) ์ปค๋ฐ ๋ฉ์์ง๋ ๋น ์ค๋ก ๋๋์ด์ง ์ธ ๊ฐ์ง ํํธ๋ก ๊ตฌ์ฑ๋๋ค. title, body(optional), footer(optional) ๋ ์ด์์์ ์๋์ ๊ฐ๋ค. type: Subject body footer - The Type (์ปค๋ฐ ํ์ ) ์ปค๋ฐ ํ์ ์ ์ ๋ชฉ(title)์ ํด๋นํ๋ฉฐ, ์๋ ์ค ํ๋์ด..
[๋ฐฑ์ค | BOJ] ๋ฌธ์ ํ์ด
์๊ณ ๋ฆฌ์ฆ ๊ณต๋ถํ๋ ์๋ชจ์์ด ์๋ค! ๋๋ ๊ฐ ์์ง ์์ผ๋ ค๊ณ ๊ฐ์ ํด์ ๊ณต๋ถ๋ ๊ณ์ ์ด์ฌํ ํ๋ ค๊ณ ํ๋ ์ค. ์ค๋ 20-22์๊น์ง ๋ฌธ์ ํ์ด๋ฅผ ์ ์ด๋๋๋ฐ, ๊ธฐ๋กํด ๋๋ ค๊ณ ๋ธ๋ก๊ทธ์๋ ๊ณต์ . ๋ฌธ์ ๋ชฉ๋ก์ ์๋์ ๊ฐ๋ค. A: ์ ์ก๊ฐํ๊ณผ ์ผ๊ฐํ https://www.acmicpc.net/problem/14264 B: ๊ฐํฌ์ผ ๊ฑฐ๊ธฐ์ ์๋ ๊ฑฐ ์๋์ผ https://www.acmicpc.net/problem/21771 C: Router https://www.acmicpc.net/problem/15828 D: ์ ํ์ ์ฉฐ๋ฆฌ (Small) https://www.acmicpc.net/problem/16173 E: ์ ๋ง๋๊ธฐ https://www.acmicpc.net/problem/10799 F: Ocean View (Large) h..