๐ป Computer Science191 [์๊ณ ๋ฆฌ์ฆ PS] ๋ฐฑ์ค 1697๋ฒ ์จ๋ฐ๊ผญ์ง ์๋ฐ ๋ฌธ์ ํ์ด ๋ฌธ์ ํด๋น ํฌ์คํ ์ ๋ฐฑ์ค์ 1697๋ฒ ์จ๋ฐ๊ผญ์ง ์ ์ ๊ทผ๊ณผ ํด๊ฒฐ ๋ฐฉ๋ฒ์ ์ค๋ช ํ ๊ธ ์ ๋๋ค. ์ ๋ต ์์ค ์ฝ๋๋ฅผ ํ์ธํ์๋ ค๋ฉด solve url ์์ ํ์ธ ๊ฐ๋ฅํฉ๋๋ค. 1697๋ฒ: ์จ๋ฐ๊ผญ์ง ์๋น์ด๋ ๋์๊ณผ ์จ๋ฐ๊ผญ์ง์ ํ๊ณ ์๋ค. ์๋น์ด๋ ํ์ฌ ์ N(0 โค N โค 100,000)์ ์๊ณ , ๋์์ ์ K(0 โค K โค 100,000)์ ์๋ค. ์๋น์ด๋ ๊ฑท๊ฑฐ๋ ์๊ฐ์ด๋์ ํ ์ ์๋ค. ๋ง์ฝ, ์๋น์ด์ ์์น๊ฐ X์ผ www.acmicpc.net ์ด ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด ์ด๋ค ๋ฐฉ์์ผ๋ก ์ ๊ทผํด์ผ ํ๋์ง๋ฅผ ๋จผ์ ์๊ฐํด๋ณด์. ๋ฌธ์ ์ ๊ทผ ์ด ๋ฌธ์ ๋ BFS ์ ๋ฐฉ๋ฌธ ์ฒ๋ฆฌ๋ฅผ ์ด์ฉํ๋ค๋ฉด ์ฝ๊ฒ ํด๊ฒฐํ ์ ์๋ ๋ฌธ์ ์ด๋ค. ํด๊ฒฐ๋ฒ bfs๋ก ๊ฐ๊ฐ์ ์ผ์ด์ค์ ๋ํด์ ํ์ธ์ ํ๋ค. ํ์ฌ ๊ฑฐ๋ฆฌ์์ - 1 ํ ๊ฒฝ์ฐ ํ์ฌ ๊ฑฐ๋ฆฌ์์ + 1 ํ ๊ฒฝ์ฐ .. 2021. 7. 29. [์๊ณ ๋ฆฌ์ฆ-PS] ๋ฐฑ์ค 7576๋ฒ ํ ๋งํ ์๋ฐ ๋ฌธ์ ํ์ด ๋ฌธ์ ํด๋น ํฌ์คํ ์ ๋ฐฑ์ค์ 7576๋ฒ ํ ๋งํ ์ ์ ๊ทผ๊ณผ ํด๊ฒฐ ๋ฐฉ๋ฒ์ ์ค๋ช ํ ๊ธ ์ ๋๋ค. ์ ๋ต ์์ค ์ฝ๋๋ฅผ ํ์ธํ์๋ ค๋ฉด solve url ์์ ํ์ธ ๊ฐ๋ฅํฉ๋๋ค. 7576๋ฒ: ํ ๋งํ ์ฒซ ์ค์๋ ์์์ ํฌ๊ธฐ๋ฅผ ๋ํ๋ด๋ ๋ ์ ์ M,N์ด ์ฃผ์ด์ง๋ค. M์ ์์์ ๊ฐ๋ก ์นธ์ ์, N์ ์์์ ์ธ๋ก ์นธ์ ์๋ฅผ ๋ํ๋ธ๋ค. ๋จ, 2 โค M,N โค 1,000 ์ด๋ค. ๋์งธ ์ค๋ถํฐ๋ ํ๋์ ์์์ ์ ์ฅ๋ ํ ๋งํ www.acmicpc.net ์ด ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด ์ด๋ค ๋ฐฉ์์ผ๋ก ์ ๊ทผํด์ผ ํ๋์ง๋ฅผ ๋จผ์ ์๊ฐํด๋ณด์. ๋ฌธ์ ์ ๊ทผ ์ด๋ฒ ๋ฌธ์ ๋ BFS ๋ฅผ ์ด์ฉํด์ ํ ์ ์๋ ๋ฌธ์ ์ด๋ค. ๊ฐ๊ฐ์ ๋ ธ๋๋ 4๋ฐฉ์ผ๋ก ์, ํ, ์ข, ์ฐ ๋ก ์ฐ๊ฒฐ๋ ๊ทธ๋ํ๋ฅผ ๋๊ณ ์๋๋ฐ, visited ๋ผ๋ ๋ฐฉ๋ฌธ ์ฒดํฌ flag ๊ฐ ํ์ ์๋ ๋ฌธ์ ์ด๋ค. ํ๋ฃจ์ .. 2021. 7. 28. [์๊ณ ๋ฆฌ์ฆ-PS] ๋ฐฑ์ค 1325๋ฒ ํจ์จ์ ์ธ ํดํน ์๋ฐ ๋ฌธ์ ํ์ด (์๊ฐ ์ด๊ณผ ํด๊ฒฐ) ๋ฌธ์ ํด๋น ํฌ์คํ ์ ๋ฐฑ์ค์ 1325๋ฒ ํจ์จ์ ์ธ ํดํน ์ ์ ๊ทผ๊ณผ ํด๊ฒฐ ๋ฐฉ๋ฒ์ ์ค๋ช ํ ๊ธ ์ ๋๋ค. ์ ๋ต ์์ค ์ฝ๋๋ฅผ ํ์ธํ์๋ ค๋ฉด solve url ์์ ํ์ธ ๊ฐ๋ฅํฉ๋๋ค. ์ด ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด ์ด๋ค ๋ฐฉ์์ผ๋ก ์ ๊ทผํด์ผ ํ๋์ง๋ฅผ ๋จผ์ ์๊ฐํด๋ณด์. ๋ฌธ์ ์ ๊ทผ ์ด ๋ฌธ์ ๋ ๊ฐ๋จํ dfs/bfs ๋ก ํด๊ฒฐํ ์ ์๋ ๋ฌธ์ ์ด๋ค. ์ด ์ ๋ ฅ์ด 1๋ง๊ฐ๊ฐ ์ต์ ์ ๊ฒฝ์ฐ ๋ค์ด์ค๊ณ ๊ฐ๊ฐ์ ๋ ธ๋์ dfs ๊ฒฐ๊ณผ๋ฅผ ํ์ํด์ผ ํ๋ ์กฐ๊ธ ๊ฐ๋น๊ฐ๋นํ๊ฒ ์๊ฐ ๋ณต์ก๋์ ๊ฑธ๋ฆด ์ ์๋ค. ๊ทธ๋์ ์ด ๋ฌธ์ ๋ ์ผ๋ฐ์ ์ธ dfs๋ก ํด๊ฒฐํ๋ฉด ์๊ฐ ์ด๊ณผ๊ฐ ๋ ์ ์๋ ๋ฌธ์ ์ด๋ค. ํด๊ฒฐ๋ฒ ์ด ๋ฌธ์ ๋ ์ฌ๊ท dfs, ์คํ dfs ๋ฑ ์ฌ๋ฌ ๋ฐฉ๋ฒ์ ํตํด์ ๊ตฌํ์ ํด๋ณด์์ง๋ฏผ ๊ฒฐ๊ณผ๋ฅผ ์กฐ๊ธ ๋ ๋นจ๋ฆฌ ๋ผ ์ ์๋ bfs ๋ก ํด๊ฒฐํ์๋ค. ํดํนํ ์ ์๋ ๋ ธ๋์ ์๋ฅผ ํํํ๊ธฐ ์ํด.. 2021. 7. 27. [Network] IP๋ฅผ ํจ๊ณผ์ ์ผ๋ก ๋๋๋ ๋ฐฉ๋ฒ : ์ฌ์ด๋ (CIDR) ์ง๋ ์๊ฐ ์ฐ๋ฆฌ๋ ๋คํธ์ํฌ ํด๋์ค์ ์๋ธ๋ท ๋ง์คํฌ๋ฅผ ์ด์ฉํด์ ๋ถ์กฑํ IPv4 ์ ์ฃผ์ ๊ณต๊ฐ์ ํจ์จ์ ์ผ๋ก ๋ํ๋ด๋ ๋ฐฉ๋ฒ์ ๋ํด์ ์์๋ณด์๋ค. ๋คํธ์ํฌ ํด๋์ค ์ค๋์ ๋คํธ์ํฌ ํด๋์ค๋ณด๋ค ๋์ฑ ์งํํ๊ณ ์๋ธ๋ท ๋ง์คํฌ๋ณด๋ค ๋ ํจ๊ณผ์ ์ธ CIDR ์ ๋ํด์ ์์๋ณด๋ ค ํ๋ค. ์ฌ์ค๋ง, Private IP ์ฐ๋ฆฌ๋ ๋ณดํต ๊ณต์ ๊ธฐ๋ฅผ ์ฌ์ฉํ๊ฑฐ๋, AWS ์์ VPC Group ์ ์์ฑํ๊ธฐ ์ํด์ ์ฌ์ค๋ง, Private IP ๋ฅผ ์ฌ์ฉํ๊ฒ ๋๋ค. ์ฌ์ค๋ง์ ํ๋์ Public IP ๋ฅผ ์ฌ๋ฌ ๊ธฐ๊ธฐ๊ฐ ๊ณต์ ํ ์ ์๋ ํจ๊ณผ์ ์ธ ๋ฐฉ๋ฒ์ด๋ผ๊ณ ์๊ฐํ ์ ์๋๋ฐ, ํ๋์ ์ฌ์ค๋ง์๋ private ip ๋ฅผ ๋ถ์ฌ๋ฐ์ ๊ธฐ๊ธฐ์ gateway ๋ก ๊ตฌ์ฑ๋์ด ๊ฐ ๊ธฐ๊ธฐ๋ ์ธํฐ๋ท๊ณผ ํต์ ํ ๋ gateway ๋ฅผ ๊ฑฐ์ณ์ ํต์ ์ ํ๊ฒ ๋๋ค. ๊ฐ๊ฐ์ private i.. 2021. 7. 24. [Network] ๋คํธ์ํฌ ํด๋์ค, Network Class ์ ๋ํ์ฌ ๋คํธ์ํฌ ํด๋์ค์ ๋ํด์ ์ดํดํ๊ธฐ ์ ์ ์์์ผ ํ ๊ธฐ๋ณธ ์ง์๋ค (์ธํฐ๋ท, IP) ์ ๋ํด์ ๋จผ์ ์์๋ณด์. ์ธํฐ๋ท์ TCP/IP ํ๋กํ ์ฝ์ ๊ธฐ๋ฐ์ผ๋ก ํ์ฌ ๋คํธ์ํฌ์์ ํต์ ์ ํ๋ ์ฐ๊ฒฐ๋ ๊ด๋ฒ์ํ ํต์ ๋ง์ ์๋ฏธํ๋ค. ์ต์ด์ ๋คํธ์ํฌ๋ ๋ฏธ ๊ตญ๋ฐฉ์ฑ์ ARPANET ์์ ์์๋์๋๋ฐ, ์ด๋ฌํ ์ธํฐ๋ท ํ๊ฒฝ์์ ๊ฐ๊ฐ์ ๊ธฐ๊ธฐ๋ค์ด ์๋ก๋ฅผ ์๋ณํ๊ธฐ ์ํด์ IP ๋ผ๋ ์ฒด๊ณ๋ฅผ ์ฌ์ฉํ๊ฒ ๋๋ค. IP ๋ Internet Protocol Address ์ ์ค์๋ง๋ก ์ธํฐ๋ท์ ์ฐ๊ฒฐ๋ ๋ชจ๋ ์ปดํจํฐ ์์์ ๊ตฌ๋ถํ๊ธฐ ์ํ ๊ณ ์ ํ ์ฃผ์๋ฅผ ์๋ฏธํ๋ค. ์ด๋ฌํ IP๋ฅผ ์ฌ๋ฌ ๊ธฐ๊ธฐ์์ ์ฌ์ฉํ๊ธฐ ์ํด์ IP๋ฅผ ๋๋๋ ๋ค์ํ ๋ฐฉ๋ฒ์ ๊ณ ์ํด ๋ด์๋๋ฐ, ๊ทธ ๋ฐฉ๋ฒ ์ค ํ๋๊ฐ ๋ฐ๋ก ๋คํธ์ํฌ ํด๋์ค์ด๋ค. ๋คํธ์ํฌ ํด๋์ค, Network Class ๋คํธ์ํฌ ํด๋.. 2021. 7. 22. [Network] Packet Switching, ํจํท ๊ตํ ๋ฐฉ์์ ๋ํด์ ๋คํธ์ํฌ ํต์ ์์ ๋ฐ์ดํฐ๋ฅผ ์ด๋ป๊ฒ ์ ๋ฌํ ์ง์ ๋ฐ๋ผ์ ํฌ๊ฒ 2๊ฐ์ง๋ก ๋๋๊ฒ ๋๋ค. ํ์ ๊ตํ ๋ฐฉ์ ํจํท ๊ตํ ๋ฐฉ์ ์ค๋์ ์ปดํจํฐ ๋คํธ์ํฌ์์ ๊ฐ์ฅ ๋ง์ด, ๋ณดํธ์ ์ผ๋ก ์ฌ์ฉ๋๋ ํจํท ๊ตํ ๋ฐฉ์์ ๋ํด์ ์ด์ผ๊ธฐํด๋ณด๋ ค ํ๋ค. Packet Switching ๋ฐฉ๋ฒ ํจํท ๊ตํ(Packet Switching) ์ ๊ทธ ์ด๋ฆ์์ ์ ์ ์์ง๋ง ๋ฐ์ดํฐ์ ๋จ์์ธ ํจํท์ ์ด์ฉํด์ ๋ชฉ์ ์ง์ ์ปดํจํฐ๋ก ๋ฐ์ดํฐ๋ฅผ ์ ๋ฌํ๋ ๋ฐฉ๋ฒ์ ๋งํ๋ค. ์์ ๋ธ๋ก์ ํจํท์ ๋ฐ์ดํฐ๋ฅผ ์ ์กํ๊ณ ๋ฐ์ดํฐ๋ฅผ ์ ์กํ๋ ๋์๋ง ๋คํธ์ํฌ ์์์ ์ฐ๊ฒฐํ๋ ํํ์ด๋ค. ์ ์ฉ ํ์ ์ด๋ผ๋ ๊ฒ์ด ์กด์ฌํ๊ณ ํด๋น ํ์ ์ ๋ ์ ์ ์ผ๋ก ์ ์ ํ๋ ํ์ ๊ตํ ๋ฐฉ์๊ณผ๋ ๋์กฐ์ ์ธ ๋ฐฉ๋ฒ์ด๋ค. ์ด๋ฌํ ํจํท ๊ตํ์๋ 2๊ฐ์ง ๋ฐฉ๋ฒ์ผ๋ก ๊ตฌํ๋ ์ ์๋๋ฐ, ๋ฐ์ดํฐ ๊ทธ๋จ ๋ฐฉ์ (Datagram) ๊ฐ์ .. 2021. 7. 22. ์ด์ 1 2 3 4 5 6 7 ยทยทยท 32 ๋ค์