์ „์ฒด ๊ธ€

์ „์ฒด ๊ธ€

    [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$ ์— ๋Œ€ํ•ด์„œ, ..

    220124

    ๋ณดํ˜ธ๋˜์–ด ์žˆ๋Š” ๊ธ€์ž…๋‹ˆ๋‹ค.

    [ํŒŒ์ด์ฌ | 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)์— ํ•ด๋‹นํ•˜๋ฉฐ, ์•„๋ž˜ ์ค‘ ํ•˜๋‚˜์ด..

    220110

    ๋ณดํ˜ธ๋˜์–ด ์žˆ๋Š” ๊ธ€์ž…๋‹ˆ๋‹ค.

    [๋ฐฑ์ค€ | 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..

    220106

    ๋ณดํ˜ธ๋˜์–ด ์žˆ๋Š” ๊ธ€์ž…๋‹ˆ๋‹ค.