๐งฉ Problem Solving/[๋ฐฑ์ค]
https://www.acmicpc.net/problem/1074 1074๋ฒ: Z ํ์๋ ํฌ๊ธฐ๊ฐ 2N × 2N์ธ 2์ฐจ์ ๋ฐฐ์ด์ Z๋ชจ์์ผ๋ก ํ์ํ๋ ค๊ณ ํ๋ค. ์๋ฅผ ๋ค์ด, 2×2๋ฐฐ์ด์ ์ผ์ชฝ ์์นธ, ์ค๋ฅธ์ชฝ ์์นธ, ์ผ์ชฝ ์๋์นธ, ์ค๋ฅธ์ชฝ ์๋์นธ ์์๋๋ก ๋ฐฉ๋ฌธํ๋ฉด Z๋ชจ์์ด๋ค. N > 1์ธ ๊ฒฝ์ฐ, ๋ฐฐ์ด์ www.acmicpc.net ZZZ ์์ด๋์ด 1. ์ซ์๋ฅผ ์ด๋ป๊ฒ ์ฐพ์ง ์ฒ์์๋ ๋ฐฐ์ด์ ๋ง๋ค์ด๋ณด๋ ค ํ์ผ๋ ์ต๋๊ธธ์ด๊ฐ 2^15์ธ๊ฑธ ๋ณด๊ณ ์ ์๋ค. ๋ถํ ํ์๊ฐ์ด ์๊ฒผ์ง๋ง ํน์ ๋ค๋ฅธ ๋ฐฉ๋ฒ์ด ์์๊น ๋ด ๊ณ ๋ฏผํ๋ค๊ฐ ๊ทธ๋ฅ ๋ถํ ์ ๋ณต์ผ๋ก ํ๊ธฐ๋ก ํ๋ค. 2. ๊ท์น์ ์ฐพ์์ผ ํด ๋ฌธ์ ์์ ์ฃผ์ด์ง ๊ทธ๋ฆผ์ ๋ณด๋ฉด 4๋ฑ๋ถ ํ์ ๋ ๋๋์ด ์จ๋ค. 4๋ฑ๋ถ ํ์๋ ๊ฐ๊ฐ์ ์ฒซ ๋ฒ์งธ ์์๊ฐ ์ผ์ ํ ๊ท์น์ด ์๋ค๋ ๊ฒ ๋ณด์ธ๋ค. ์๋ฅผ ๋ค์ด N = 3์ผ๋ก ์ฃผ..
๐งฉ Problem Solving/[๋ฐฑ์ค]
https://www.acmicpc.net/problem/9019 9019๋ฒ: DSLR ๋ค ๊ฐ์ ๋ช
๋ น์ด D, S, L, R ์ ์ด์ฉํ๋ ๊ฐ๋จํ ๊ณ์ฐ๊ธฐ๊ฐ ์๋ค. ์ด ๊ณ์ฐ๊ธฐ์๋ ๋ ์ง์คํฐ๊ฐ ํ๋ ์๋๋ฐ, ์ด ๋ ์ง์คํฐ์๋ 0 ์ด์ 10,000 ๋ฏธ๋ง์ ์ญ์ง์๋ฅผ ์ ์ฅํ ์ ์๋ค. ๊ฐ ๋ช
๋ น์ด๋ ์ด ๋ ์ง์คํฐ์ www.acmicpc.net ์์ด๋์ด 1. bfs ์ต์ํ์ ๋ช
๋ น ์ด์ ์ถ๋ ฅ ํ๋ผ ํ์ผ๋ฏ๋ก bfs๊ฐ ์๋๋ฉด ๋ชป ํ ๊ฑฐ ๊ฐ๋ค๊ณ ์๊ฐํ๋ค. ์๊ฐ์ ํ๋ 6์ด๋ก ๋๋ํ๊ฒ ์์ด์ ์ถฉ๋ถํ๋ค๊ณ ์๊ฐํ๋ค. 2. ์๊ฐ ์ด๊ณผ ์์ฆ ๊ณ์ ์๊ฐ ์ด๊ณผ๊ฐ ๋ฌ๋ค. 6์ด๋ผ์ ๋๋ํ ์ค ์์๋๋ฐ. ์๊ฐ ์ด๊ณผ๊ฐ ๋ฌ์ด์ ๋ ๋ค์๊ณผ ๊ฐ๋ค. D, S, L, R ๊ฐ๊ฐ์ ๋ช
๋ น์ด๋ฅผ ๊ฐ์ํ๊ฒ ๊ตฌํํด์ผ ํ๋๋ฐ, if๋ฌธ์ด๋ ๋ฆฌ์คํธ๋ฅผ ์ฌ์ฉํด ์๊ฐ์ ํ์ด ๊ฑธ๋ฆฐ ๊ฑฐ ๊ฐ๋ค..
๐งฉ Problem Solving/[๋ฐฑ์ค]
https://www.acmicpc.net/problem/14500 14500๋ฒ: ํ
ํธ๋ก๋ฏธ๋
ธ ํด๋ฆฌ์ค๋ฏธ๋
ธ๋ ํฌ๊ธฐ๊ฐ 1×1์ธ ์ ์ฌ๊ฐํ์ ์ฌ๋ฌ ๊ฐ ์ด์ด์ ๋ถ์ธ ๋ํ์ด๋ฉฐ, ๋ค์๊ณผ ๊ฐ์ ์กฐ๊ฑด์ ๋ง์กฑํด์ผ ํ๋ค. ์ ์ฌ๊ฐํ์ ์๋ก ๊ฒน์น๋ฉด ์ ๋๋ค. ๋ํ์ ๋ชจ๋ ์ฐ๊ฒฐ๋์ด ์์ด์ผ ํ๋ค. ์ ์ฌ๊ฐํ์ ๋ณ www.acmicpc.net ์์ด๋์ด 1. ๋ ๊ฐ์ง๋ก ๋๋ ์๊ฐํ๋ฉด ํ
ํธ๋ก๋ฏธ๋
ธ ๋ํ ๋ง๋ค๊ธฐ ์ข
์ด ์์ ์ฌ๋ฆฌ๊ธฐ 2. ๋ํ ๋ง๋ค๊ธฐ ๋ํ์ด ํ์ ์ด๋ ๋์นญ๋ ๊ฐ๋ฅํ๋ dfs๋ฅผ ์ฌ์ฉํ๋ฉด T๋ํ ๋นผ๊ณ ์ ๋ถ ๋ค ๋ง๋ค ์ ์๋ค. dfs ํ์ ๊น์ด๋ฅผ 4๊น์ง ์ค์ ํ๋ฉด ๋ํ์ ํ์ธํ ์ ์๋ค. T ๋ชจ์์ ๋ฐ๋ก ํจ์๋ฅผ ๋ง๋ค์ด ์ฒ๋ฆฌํ๋ค. 3. ์ข
์ด์ ๋ํ ๋๊ธฐ ์๊ฐ์ ํ์ด๋ N, M ํฌ๊ธฐ๋ฅผ ๋ณด๊ณ ๋ธ๋ฃจํธ ํฌ์ค๋ฅผ ์ฌ์ฉํ๊ธฐ๋ก ๊ฒฐ์ ํ๋ค. ๊ฐ ์์น๋ง๋ค ๋ง๋ค์ด..
๐งฉ Problem Solving/[๋ฐฑ์ค]
https://www.acmicpc.net/problem/18111 18111๋ฒ: ๋ง์ธํฌ๋ํํธ ํ ๋ ๋์ํํธ๋ ๋ํ ์ค๋น๋ฅผ ํ๋ค๊ฐ ์ง๋ฃจํด์ ธ์ ์๋๋ฐ์ค ๊ฒ์์ธ ‘๋ง์ธํฌ๋ํํธ’๋ฅผ ์ผฐ๋ค. ๋ง์ธํฌ๋ํํธ๋ 1 × 1 × 1(์ธ๋ก, ๊ฐ๋ก, ๋์ด) ํฌ๊ธฐ์ ๋ธ๋ก๋ค๋ก ์ด๋ฃจ์ด์ง 3์ฐจ์ ์ธ๊ณ์์ ์์ ๋กญ๊ฒ www.acmicpc.net ์์ด๋์ด 1. ๋ธ๋ฃจํธ ํฌ์ค ๋ฌธ์ ์์ ๋์ด ์ด๊ฐ 256๊น์ง ๊ทธ๋ฆฌ๊ณ N, M์ด 500๊น์ง๊ฐ ์ต๋๋ค. 256*500*500 = 64000000์ด๋ฏ๋ก 1์ด ์์ ๊ฐ๋ฅํ๋ค ์๊ฐ.. 2. ์๊ฐ ์ด๊ณผ ๋ธ๋ฃจํธ ํฌ์ค๋ก ๊ฐ๋ฅํ๋ค ์๊ฐํ๋๋ฐ ๊ณ์ ์๊ฐ ์ด๊ณผ๊ฐ ๊ฑธ๋ ธ๋ค. ๋ค๋ฅธ ์ฌ๋๋ค์ด ์ง ์ฝ๋๋ฅผ ํ์ธํด ๋ณด๋ elif๊ฐ ์๋ else๋ฅผ ์ฌ์ฉํ๋ค. pypy๋ก ํต๊ณผํ๋ค. else์ elif๊ฐ ์๊ฐ ์ฐจ์ด๊ฐ ๋ง์ด ๋๋ค๋ ๊ฒ์ ..
๐งฉ Problem Solving/[๋ฐฑ์ค]
https://www.acmicpc.net/problem/1107 1107๋ฒ: ๋ฆฌ๋ชจ์ปจ ์ฒซ์งธ ์ค์ ์๋น์ด๊ฐ ์ด๋ํ๋ ค๊ณ ํ๋ ์ฑ๋ N (0 ≤ N ≤ 500,000)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค์๋ ๊ณ ์ฅ๋ ๋ฒํผ์ ๊ฐ์ M (0 ≤ M ≤ 10)์ด ์ฃผ์ด์ง๋ค. ๊ณ ์ฅ๋ ๋ฒํผ์ด ์๋ ๊ฒฝ์ฐ์๋ ์
์งธ ์ค์๋ ๊ณ ์ฅ๋ ๋ฒํผ www.acmicpc.net ์์ด๋์ด 1. ์๊ณ ๋ฆฌ์ฆ ์ ํ ์ฒ์ ๋ฌธ์ ๋ฅผ ๋ณด๊ณ DP๋ก ํ์ด์ผ ํ๋ ์๊ฐํ๋ฉด์ ๋์ ํ ๋ชจ๋ฅด๊ฒ ์ด์ ์๊ณ ๋ฆฌ์ฆ ๋ถ๋ฅ๋ฅผ ๋ณด๋๊น ๊ทธ๋ฅ ๋ธ๋ฃจํธ ํฌ์ค ๋ฌธ์ ๋ค. 2. ๊ตฌํ ๋จผ์ ํ์ฌ ์ฑ๋(100)์์ ์ต์๊ฐ์ด ๋์ฌ ์ ์๋์ง ํ์ธ ์ดํ 0๋ถํฐ 1000000๊น์ง ๋ฒํผ์ผ๋ก ๋ง๋ค ์ ์๋ ์ฑ๋์ธ์ง ํ์ธ ๊ทธ ์ฑ๋ ์ซ์๋ฅผ ๋ง๋๋๋ฐ ํ์ํ ๋ฒํผ ๊ฐ์ ํ์ธ ์ฝ๋ ์ค๋ช
N = int(input()) M = in..
๐งฉ Problem Solving/[๋ฐฑ์ค]
https://www.acmicpc.net/problem/16234 16234๋ฒ: ์ธ๊ตฌ ์ด๋ N×Nํฌ๊ธฐ์ ๋
์ด ์๊ณ , ๋
์ 1×1๊ฐ์ ์นธ์ผ๋ก ๋๋์ด์ ธ ์๋ค. ๊ฐ๊ฐ์ ๋
์๋ ๋๋ผ๊ฐ ํ๋์ฉ ์กด์ฌํ๋ฉฐ, rํ c์ด์ ์๋ ๋๋ผ์๋ A[r][c]๋ช
์ด ์ด๊ณ ์๋ค. ์ธ์ ํ ๋๋ผ ์ฌ์ด์๋ ๊ตญ๊ฒฝ์ ์ด ์กด์ฌํ๋ค. ๋ชจ www.acmicpc.net ์์ด๋์ด 1. ํ์ด์ฌ ์ด์ ์ฒ์์ dfs๋ก ์ ๊ทผํ๋๋ฐ Python3๋ก ์ฑ์ ํ๋ฉด 80% ์์ ์๊ฐ ์ด๊ณผ๊ฐ ๋ฐ์ํ๋ค. (pypy๋ก๋ ํต๊ณผ) ํฌ๊ธฐํ๊ณ bfs๋ก ์ ๊ทผํ๋๋ฐ ๋ ์๊ฐ ์ด๊ณผ๊ฐ ๋ฐ์ํด์ ์กฐ๊ฑด์ ๋ช ๊ฐ ์ถ๊ฐํ๋ ํต๊ณผ๋จ. c++ ์์ผ๋ฉด dfs๋ก ํต๊ณผํ์ ๊ฑฐ ๊ฐ๋ค. 2. ๊ตฌํ ํํธ๋ ํฌ๊ฒ ๋ ๊ฐ๋ก ๋๋ด๋ค. ๊ตญ๊ฒฝ์ ์ด๊ธฐ ์ธ๊ตฌ์ ๋ถ๋ฐฐ ์ฝ๋ ์ค๋ช
๊ธฐ๋ณธ์ ์ผ๋ก ์ด์ค for๋ฌธ์ ์ฌ์ฉํด์ ๊ฐ ์์น..
๐งฉ Problem Solving/[๋ฐฑ์ค]
https://www.acmicpc.net/problem/1389 1389๋ฒ: ์ผ๋น ๋ฒ ์ด์ปจ์ 6๋จ๊ณ ๋ฒ์น ์ฒซ์งธ ์ค์ ์ ์ ์ ์ N (2 ≤ N ≤ 100)๊ณผ ์น๊ตฌ ๊ด๊ณ์ ์ M (1 ≤ M ≤ 5,000)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ M๊ฐ์ ์ค์๋ ์น๊ตฌ ๊ด๊ณ๊ฐ ์ฃผ์ด์ง๋ค. ์น๊ตฌ ๊ด๊ณ๋ A์ B๋ก ์ด๋ฃจ์ด์ ธ ์์ผ๋ฉฐ, A์ B๊ฐ ์น๊ตฌ๋ผ๋ ๋ป www.acmicpc.net ๋ฌธ์ ๋ฅผ ๋ณด๋ค๊ฐ ์ต๊ทผ์ ๊ณต๋ถํ ํ๋ก์ด๋ ์์ฌ๋ก ํ ์ ์์ ๊ฑฐ ๊ฐ์ ์ฌ์ฉํ๋๋ ํต๊ณผ๋๋ค. ํ์ด ๊ณผ์ for _ in range(M): a,b = map(int,sys.stdin.readline().rstrip().split()) graph[a][b] = 1 graph[b][a] = 1 for i in range(1, N + 1): for j in ra..
๐งฉ Problem Solving/[๋ฐฑ์ค]
https://www.acmicpc.net/problem/7562 7562๋ฒ: ๋์ดํธ์ ์ด๋ ์ฒด์คํ ์์ ํ ๋์ดํธ๊ฐ ๋์ฌ์ ธ ์๋ค. ๋์ดํธ๊ฐ ํ ๋ฒ์ ์ด๋ํ ์ ์๋ ์นธ์ ์๋ ๊ทธ๋ฆผ์ ๋์์๋ค. ๋์ดํธ๊ฐ ์ด๋ํ๋ ค๊ณ ํ๋ ์นธ์ด ์ฃผ์ด์ง๋ค. ๋์ดํธ๋ ๋ช ๋ฒ ์์ง์ด๋ฉด ์ด ์นธ์ผ๋ก ์ด๋ํ ์ www.acmicpc.net ๋ฏธ๋ก ์ฐพ๊ธฐ๋ ๋น์ทํ๋ค. ์ ๋ฒ์ ํ์ ๋ฌธ์ ํ ๋ bfs๋ก ์๊ฐ ์ด๊ณผ๊ฐ ๋ฌ ๊ฒฝํ์ ์ผ์ dfs๋ก ํ์๋๋ฐ ํด๊ฒฐ์ด ์ ๋๋ค. ์๊ฐํด๋ณด๋ค๊ฐ bfs๋ก ํ์๋๋ฐ ๋ฐ๋ก ๋ต์ด ๋์๋ค. ๋ด ์๊ฐ์๋ bfs๋๊น ์์ฐ์ค๋ฝ๊ฒ ์ต๋จ๊ฑฐ๋ฆฌ๊ฐ ๋์ค๋๊น(depth ๋ณ๋ก ํ์) ์ด๋ฐ ๋ฌธ์ ๋ bfs๋ก ํธ๋ ๊ฒ ์ข์ ๊ฑฐ ๊ฐ๋ค. ํ์ด ๊ณผ์ dx = [2,2,1,1,-1,-1,-2,-2] dy = [1,-1,2,-2,2,-2,1,-1]..