์ ์ฒด ๊ธ214 [๋ฐฑ์ค] 20055 ์ปจ๋ฒ ์ด์ด ๋ฒจํธ ์์ ๋ก๋ด (Python/ํ์ด์ฌ) https://www.acmicpc.net/problem/20055 20055๋ฒ: ์ปจ๋ฒ ์ด์ด ๋ฒจํธ ์์ ๋ก๋ด ๊ธธ์ด๊ฐ N์ธ ์ปจ๋ฒ ์ด์ด ๋ฒจํธ๊ฐ ์๊ณ , ๊ธธ์ด๊ฐ 2N์ธ ๋ฒจํธ๊ฐ ์ด ์ปจ๋ฒ ์ด์ด ๋ฒจํธ๋ฅผ ์์๋๋ก ๊ฐ์ธ๋ฉฐ ๋๊ณ ์๋ค. ๋ฒจํธ๋ ๊ธธ์ด 1 ๊ฐ๊ฒฉ์ผ๋ก 2N๊ฐ์ ์นธ์ผ๋ก ๋๋์ด์ ธ ์์ผ๋ฉฐ, ๊ฐ ์นธ์๋ ์๋ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ด 1๋ถ www.acmicpc.net 1. ์ฃผ์ด์ง ์กฐ๊ฑด๋๋ก ๊ตฌํํ๋ฉด ๋๋ ๊ตฌํ ๋ฌธ์ ์ด๋ค. 2. ํฌ๊ฒ ๋ณต์กํ ์๊ณ ๋ฆฌ์ฆ์ด๋ ๊ตฌํ์ ํ์ ์๊ณ ๋ฌธ์ ์ฝ๊ณ ๋จ๊ณ๋ณ๋ก ๊ฐ ๋์์ ๊ผผ๊ผผํ ๊ตฌํํ๋ฉด ๋ฌด๋ํ๊ฒ ํต๊ณผ ๋๋ค. 3. ๋ฒจํธ ํ์ ์ deque์ rotate() ๋ฉ์๋๋ฅผ ์ด์ฉํ๋ฉด ํธํ๊ณ ๋ก๋ด์ ๋ฐฐ์ด ๊ฐ์ ๊ฒฝ์ฐ๋ ๋ฐํฌ๋ณด๋ค ๊ทธ๋ฅ ๋ฆฌ์คํธ๊ฐ ํธํ๊ณ ๋น ๋ฅด๋ค. from collections import deque import sys,.. 2022. 9. 30. UDP Multiplexing - Demultiplexing ๊ณผ์ ์์ Source port#์ ์ญํ ์ ๋ฌด์์ผ๊น? UDP Multiplexing - Demultiplexing ๊ณผ์ ์์ Source port#์ ์ญํ ๊ณผ IP address ์ด์ ๋คํธ์ํฌ ์คํฐ๋๋ฅผ ์งํํ๋ค ๋ฌธ๋ ์๊ธด ์๋ฌธ์ .... โ UDP ๋ฐฉ์์์ Demux๋ฅผ ์ํํ ๋ Destination port#์ Destination IP addreess ์ ๋ณด๋ฅผ ์ด์ฉํ๋ค. ๊ทธ๋ฐ๋ฐ ์ฌ์ง์ ๋ณด๋ฉด... โ ๊ทธ๋ฐ๋ฐ ์ธ๊ทธ๋จผํธ๋ฅผ ๋ณด๋ฉด ํค๋ ์ ๋ณด๋ฅผ ์ ๋ณด๋ฉด ๋ ๊ฐ์ง ์๋ฌธ์ ์ด ์๊ธด๋ค. ์ฐ์ง๋ ์๋ src port#๋ ์ ์๋๊ฐ? ์ ์ ํ์ํ dest IP๋ ์ด๋ ์๋๊ฐ? โ ๋ ์ง๋ฌธ์ ๋ํ ๋ต์ ๊ต์ฌ(Computer Networking A Top-Down ApproachKurose. James, Ross, Keith)์ ์์๋ค. 1. Source Port number โ ์ฐ์ .. 2022. 9. 30. [๋ฐฑ์ค] 2212 ์ผ์ (Python/ํ์ด์ฌ) https://www.acmicpc.net/problem/2212 2212๋ฒ: ์ผ์ ์ฒซ์งธ ์ค์ ์ผ์์ ๊ฐ์ N(1 ≤ N ≤ 10,000), ๋์งธ ์ค์ ์ง์ค๊ตญ์ ๊ฐ์ K(1 ≤ K ≤ 1000)๊ฐ ์ฃผ์ด์ง๋ค. ์ ์งธ ์ค์๋ N๊ฐ์ ์ผ์์ ์ขํ๊ฐ ํ ๊ฐ์ ์ ์๋ก N๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ์ขํ ์ฌ์ด์๋ ๋น ์นธ์ด ํ๋ ์ www.acmicpc.net ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ๋ถ๋ฅ๋๋ ๋ฌธ์ ์ธ๋ฐ ๋๋ถ๋ถ์ ๊ทธ๋ฆฌ๋ ๋ฌธ์ ๊ฐ ๊ทธ๋ ๋ฏ์ด ๊ทธ๋ฆฌ๋์ธ ๊ฑธ ์๊ณ ๋๋ฉด ์ฝ๋ค. ๊ทธ๋ฆฌ๋์ธ ๊ฑธ ์๊ณ ํ์ ํ๊ธฐ๊น์ง๊ฐ ์ด๋ ค์์ ๊ทธ๋ ์ง... ์ผ์์ ์ง์ค๊ตญ ๊ฐ์ ๊ฑฐ๋ฆฌ๋ฅผ ์ต์ํ ํด์ผ๋๊ธฐ ๋๋ฌธ์ ์ผ์ ๊ฐ ๊ฑฐ๋ฆฌ๊ฐ ๊ฐ์ฅ ํฐ ์ง์ญ์ด ์ง์ค๊ตญ ์์ ์์ญ ๋ด์ ํฌํจ๋์ง ์๋๋ก ํด์ผ๋๋ค. ๋ฐ๋ผ์ ์ผ์ ๊ฐ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํด์ ๊ฐ์ฅ ๊ฑฐ๋ฆฌ๊ฐ ํฐ ์ง์ญ K - 1๊ฐ๋ฅผ ์ด ์ง์ญ์์ ๋นผ์ฃผ๋ฉด ๋.. 2022. 9. 29. [์๊ณ ๋ฆฌ์ฆ] ์ต์ ์ ์ฅ ํธ๋ฆฌ (MST) ์ต์ ์ ์ฅ ํธ๋ฆฌ (MST) ์ ์ฅ ํธ๋ฆฌ (Spanning Tree) โ ๊ทธ๋ํ ๋ด์ ๋ชจ๋ ์ ์ ์ ํฌํจํ๋ ํธ๋ฆฌ โ ๊ทธ๋ํ์ ์ต์ ์ฐ๊ฒฐ ๋ถ๋ถ ๊ทธ๋ํ (N - 1)๊ฐ์ ๊ฐ์ -> ํธ๋ฆฌ ํํ ์ต์ ์ ์ฅ ํธ๋ฆฌ (Minimum spanning Tree) โ Spanning Tree ์ค์์ ๊ฐ์ ์ ๊ฐ์ค์น ํฉ์ด ์ต์(Minimun)์ธ ํธ๋ฆฌ โ ์ต์ ์ ์ฅ ํธ๋ฆฌ๋ ์ฌ๋ฌ ๊ฐ ์ผ ์ ์๋ค. MST ๊ตฌํ - ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ โ Greedy๋ฅผ ์ด์ฉํด ๊ฐ ๋จ๊ณ์์ ์ฌ์ดํด์ ์ด๋ฃจ์ง ์๋ ์ต์ ๋น์ฉ ๊ฐ์ ์ ์ ํํ๋ค. ๋์ ์์ ๊ฐ์ ์ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํ๋ค. (์ต์ ๋น์ฉ) ์ ๋ ฌ๋ ๊ฐ์ ๋ฆฌ์คํธ์์ ์์๋๋ก ์ฌ์ดํด์ ํ์ฑํ์ง ์๋ ๊ฐ์ ์ ์ ํํ๋ค. (Union - Find ์ด์ฉ: Union-Find ์๊ณ ๋ฆฌ์ฆ์ด๋?!) ์ ํํ ๊ฐ์ ์ ํ์ฌ .. 2022. 9. 29. [์๊ณ ๋ฆฌ์ฆ] Union-Find ์ ๋์จํ์ธ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ โ ์๋ก์ ์งํฉ(Disjoint Set) โ ์ฌ๋ฌ ๊ฐ์ ๋ ธ๋๊ฐ ์กด์ฌํ ๋ , ์์์ ๋ ๋ ธ๋๊ฐ ๊ฐ์ ๊ทธ๋ํ์ ์ํด์๋์ง ํ๋ณ Union & Find Find ๋ ธ๋ x๊ฐ ํฌํจ๋ ์งํฉ์ ์ฐพ๋ ์ฐ์ฐ def find_parent(parent, current): if parent[current] != current: return find_parent(parent, parent[current]) return current Union ๋ ธ๋ x๊ฐ ํฌํจ๋ ์งํฉ๊ณผ ๋ ธ๋ y๊ฐ ํฌํจ๋ ๋ ์งํฉ์ ํตํฉํ๋ ์ฐ์ฐ def union_parent(parent, x, y): x = find_parent(parent, x) y = find_parent(parent, y) # ๋จ์ํ ํํ์์๋ ์์ ์ชฝ์ผ๋ก ํฉ์น๋ค.. 2022. 9. 28. [๋ฐฑ์ค] 3190 ๋ฑ (Python/ํ์ด์ฌ) https://www.acmicpc.net/problem/3190 3190๋ฒ: ๋ฑ 'Dummy' ๋ผ๋ ๋์ค๊ฒ์์ด ์๋ค. ์ด ๊ฒ์์๋ ๋ฑ์ด ๋์์ ๊ธฐ์ด๋ค๋๋๋ฐ, ์ฌ๊ณผ๋ฅผ ๋จน์ผ๋ฉด ๋ฑ ๊ธธ์ด๊ฐ ๋์ด๋๋ค. ๋ฑ์ด ์ด๋ฆฌ์ ๋ฆฌ ๊ธฐ์ด๋ค๋๋ค๊ฐ ๋ฒฝ ๋๋ ์๊ธฐ์์ ์ ๋ชธ๊ณผ ๋ถ๋ชํ๋ฉด ๊ฒ์์ด ๋๋๋ค. ๊ฒ์ www.acmicpc.net ํ์ ์ ์ ์ ์ถ ๊ตฌ์กฐ๋ฅผ ํ์ฉํ ๊ตฌํ ๋ฌธ์ ์ด๋ค. ๊ตฌํํด์ผํ ์ฌํญ๋ค์ ๊ฐ๋ตํ๊ฒ ๋๋ ๋ณด๋ฉด ๋ค์๊ณผ ๊ฐ๋ค. ๋ฑ์ ์ด๋ ๊ฒ์ ์ข ๋ฃ ์กฐ๊ฑด ๋ฒฝ์ ๋ถ๋ชํ์ ๋(= ๋ฒ์๋ฅผ ๋ฒ์ด๋ฌ์ ๋) ๋ฑ์ ๋ชธํต์ ๋ถ๋ชํ์ ๋ ์ฌ๊ณผ๊ฐ ์์ ๋ ๋ฑ์ ํฌ๊ธฐ๋ฅผ ์ฌ๊ณผ๊ฐ ์๋ ์์ญ ํ ์นธ๋งํผ ๋๋ ค์ค๋ค. ์ฌ๊ณผ๊ฐ ์์ ๋ ๋ฑ์ ํฌ๊ธฐ๋ฅผ ์ ์งํ ์ฑ ์ฌ๊ณผ๊ฐ ์๋ ์์ญ์ผ๋ก ํ ์นธ ์ด๋ ์์ผ์ค๋ค.(๊ผฌ๋ฆฌ -1) ๋ฑ์ ๋ชธํต์ ๋ฑ์ด ์ด๋ํ๋ ๊ฒฝ๋ก๋ฅผ ํ์ํด์ฃผ๋ ๋ฐฉ์์ผ.. 2022. 9. 28. ์ด์ 1 ยทยทยท 31 32 33 34 35 36 ๋ค์