๐งฉ Problem Solving/[๋ฐฑ์ค]
https://www.acmicpc.net/problem/6064 6064๋ฒ: ์นด์ ๋ฌ๋ ฅ ์
๋ ฅ ๋ฐ์ดํฐ๋ ํ์ค ์
๋ ฅ์ ์ฌ์ฉํ๋ค. ์
๋ ฅ์ T๊ฐ์ ํ
์คํธ ๋ฐ์ดํฐ๋ก ๊ตฌ์ฑ๋๋ค. ์
๋ ฅ์ ์ฒซ ๋ฒ์งธ ์ค์๋ ์
๋ ฅ ๋ฐ์ดํฐ์ ์๋ฅผ ๋ํ๋ด๋ ์ ์ T๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ํ
์คํธ ๋ฐ์ดํฐ๋ ํ ์ค๋ก ๊ตฌ์ฑ๋๋ค. www.acmicpc.net ์์ด๋์ด 1. ์๊ฐ ์ด๊ณผ ์ฒ์์๋ x, y๊ฐ์ด ๋์ฌ ๋๊น์ง 1์ฉ ๋ํด๊ฐ๋ฉฐ count๋ฅผ ํ๋ค. ์ซ์๊ฐ ๋ฐ๋ณต๋๋ฉด -1์ ์ถ๋ ฅํ๊ฒ ํ๋ค. ์๊ฐ์ด ๋๋ฌด ์ฌ์ ๋์ง ์๊ฐ ์ด๊ณผ๊ฐ ๋ฐ์ํ๋ค. ๋ค๋ฅธ ๋ฐฉ๋ฒ์ ์ฌ์ฉํ๊ธฐ๋ก ๊ฒฐ์ ์ฝ๋ ์ค๋ช
def find_K(M, N, x, y): K = x while K
๐งฉ Problem Solving/[๋ฐฑ์ค]
https://www.acmicpc.net/problem/11403 11403๋ฒ: ๊ฒฝ๋ก ์ฐพ๊ธฐ ๊ฐ์ค์น ์๋ ๋ฐฉํฅ ๊ทธ๋ํ G๊ฐ ์ฃผ์ด์ก์ ๋, ๋ชจ๋ ์ ์ (i, j)์ ๋ํด์, i์์ j๋ก ๊ฐ๋ ๊ฒฝ๋ก๊ฐ ์๋์ง ์๋์ง ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. www.acmicpc.net ์์ด๋์ด 1. ํ๋ก์ด๋ ์์ฌ ์์ ์ ๊ฐ์ค์น๊ฐ ์๋ ํ๋ก์ด๋ ์์ฌ์ ํผ ๊ฒฝํ์ด ์์ด์ ์ด๋ฒ์๋ ๊ฐ๋จํ๊ฒ ํด๊ฒฐํ๋ค. ๊ธฐ์กด ์๊ณ ๋ฆฌ์ฆ์์ ์ฝ๊ฐ๋ง ๋ณํํ๋ฉด ๋จ ์ฝ๋ ์ค๋ช
for k in range(N): for i in range(N): for j in range(N): if adj_matrix[i][k] == 1 and adj_matrix[k][j] == 1: adj_matrix[i][j] = 1 k๋ ๊ฑฐ์ณ๊ฐ๋ ๋
ธ๋, i๋ ์์ ๋
ธ๋, j๋ ๋์ฐฉ..
๐งฉ Problem Solving/[๋ฐฑ์ค]
https://www.acmicpc.net/problem/16236 16236๋ฒ: ์๊ธฐ ์์ด N×N ํฌ๊ธฐ์ ๊ณต๊ฐ์ ๋ฌผ๊ณ ๊ธฐ M๋ง๋ฆฌ์ ์๊ธฐ ์์ด 1๋ง๋ฆฌ๊ฐ ์๋ค. ๊ณต๊ฐ์ 1×1 ํฌ๊ธฐ์ ์ ์ฌ๊ฐํ ์นธ์ผ๋ก ๋๋์ด์ ธ ์๋ค. ํ ์นธ์๋ ๋ฌผ๊ณ ๊ธฐ๊ฐ ์ต๋ 1๋ง๋ฆฌ ์กด์ฌํ๋ค. ์๊ธฐ ์์ด์ ๋ฌผ๊ณ ๊ธฐ๋ ๋ชจ๋ ํฌ๊ธฐ๋ฅผ ๊ฐ www.acmicpc.net ์์ด๋์ด 1. ์ต์ ๊ฒฝ๋ก bfs ์ง๋์ ์ต์ ๊ฒฝ๋ก๊ฐ ํ์ํ๋ค๋ ๊ฒ์ ๋ณด๊ณ bfs๋ฅผ ์ฌ์ฉํ๊ธฐ๋ก ๊ฒฐ์ . ์ฌ์ ๋ก์ด ์๊ฐ๊ณผ nํฌ๊ธฐ๋ฅผ ๋ณด๊ณ bfs๋ฅผ ์ฌ๋ฌ ๋ฒ ํด๋ ๊ด์ฐฎ๊ฒ ๋ค๊ณ ์๊ฐํ๋ค. ๊ทธ๋์ ๊ฐ์ฅ ๊ฐ๊น์ด ๋จน์ด๋ฅผ ์ฐพ์ ๋๋ง๋ค bfs๋ฅผ ์ฌ์ฉํ๊ธฐ๋ก ํ๋ค. 2. ๊ฐ์ฅ ๊ฐ๊น์ด ๋ฌผ๊ณ ๊ธฐ a. ๋ฌผ๊ณ ๊ธฐ๊น์ง ์ด๋์ด ๊ฐ๋ฅํ์ง check b. ๊ทธ ๋ฌผ๊ณ ๊ธฐ๋ฅผ ๋จน์ ์ ์๋์ง c. ๊ฐ๋ฅํ ๋ฌผ๊ณ ๊ธฐ๋ค์ ๋ฆฌ์คํธ์ ๋ด์๋๊ณ lamb..
๐งฉ Problem Solving/[๋ฐฑ์ค]
https://www.acmicpc.net/problem/17626 17626๋ฒ: Four Squares ๋ผ๊ทธ๋์ฃผ๋ 1770๋
์ ๋ชจ๋ ์์ฐ์๋ ๋ท ํน์ ๊ทธ ์ดํ์ ์ ๊ณฑ์์ ํฉ์ผ๋ก ํํํ ์ ์๋ค๊ณ ์ฆ๋ช
ํ์๋ค. ์ด๋ค ์์ฐ์๋ ๋ณต์์ ๋ฐฉ๋ฒ์ผ๋ก ํํ๋๋ค. ์๋ฅผ ๋ค๋ฉด, 26์ 52๊ณผ 12์ ํฉ์ด๋ค; ๋ํ 42 + 32 + 1 www.acmicpc.net ์์ด๋์ด 1. ๊ทธ๋ฆฌ๋์ dp ์ฒ์์๋ n์ ๋์ง ์๋ ์ต๋ ์ ๊ณฑ์๋ฅผ n์ ๋นผ๊ฐ๋ฉด ๋์ง ์์๊น ์๊ฐํ๋ค. ์ด๋ ๊ฒ ํ๋ฉด ์์ธ๊ฐ ์๊ธด๋ค. ์๋ฅผ ๋ค์ด 12๋ ๊ทธ๋ฆฌ๋๋ก ์๊ฐํ๋ฉด 9, 1, 1, 1์ด์ง๋ง ์ ๋ต์ 4,4,4๋ก 3๊ฐ๊ฐ ์ต์ ๊ฐ์๋ค. ๋ค์ ๋ฌธ์ ๋ด์ฉ์ ๋ณด๊ณ dp๋ก ํ๊ธฐ๋ก ๊ฒฐ์ DP[n] = (n์ด๋ผ๋ ์๋ฅผ ๋ง๋๋๋ฐ ํ์ํ ์์ ๊ฐ์) ์ฝ๋ ์ค๋ช
k = 1 whi..
๐งฉ Problem Solving/[๋ฐฑ์ค]
https://www.acmicpc.net/problem/2293 2293๋ฒ: ๋์ 1 ์ฒซ์งธ ์ค์ n, k๊ฐ ์ฃผ์ด์ง๋ค. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) ๋ค์ n๊ฐ์ ์ค์๋ ๊ฐ๊ฐ์ ๋์ ์ ๊ฐ์น๊ฐ ์ฃผ์ด์ง๋ค. ๋์ ์ ๊ฐ์น๋ 100,000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค. www.acmicpc.net DP ๋๋ฌด ์ด๋ ต๋ค์์ ์์ด๋์ด 1. DP ๋ฌธ์ ๋ฅผ ๋ณด๊ณ dp๋ฌธ์ ์ธ ๊ฒ๋ ์๊ณ 'DP [k] = ํฉ์ด k๊ฐ ๋๋ ๊ฒฝ์ฐ์ ์'๋ผ๋ ๊ฒ๋ ์์๋ค. ๊ทผ๋ฐ ์ ํ์ ์์ด๋์ด๊ฐ ๋ ์ค๋ฅด์ง ์์ ๊ฒ์์ ํ์ ๋น๋ ธ๋ค. ์ผ์ฃผ์ผ ๋ค์ ๋ ํ์ด๋ดค๋๋ฐ ๋ ๊น๋จน์๋ค. ์ดํด๋ฅผ ๋ชป ํ๋ค๋ ๋ป์ด๋ค. ์ด๋ฒ ๊ธฐํ์ ์ ๋๋ก ์ดํดํ๊ณ ๋์ด๊ฐ๊ธฐ๋ก ํจ. ์ฝ๋ ์ค๋ช
DP = [0] * (k + 1) DP[0] = 1 for c in coins:..
๐งฉ Problem Solving/[๋ฐฑ์ค]
https://www.acmicpc.net/problem/2096 2096๋ฒ: ๋ด๋ ค๊ฐ๊ธฐ ์ฒซ์งธ ์ค์ N(1 ≤ N ≤ 100,000)์ด ์ฃผ์ด์ง๋ค. ๋ค์ N๊ฐ์ ์ค์๋ ์ซ์๊ฐ ์ธ ๊ฐ์ฉ ์ฃผ์ด์ง๋ค. ์ซ์๋ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ์ค์ ํ๋๊ฐ ๋๋ค. www.acmicpc.net ๋ฉ๋ชจ๋ฆฌ ์ ํ(4MB)์ด ์๋ dp๋ฌธ์ ์์ด๋์ด 1. ๋ฉ๋ชจ๋ฆฌ ์ ํ ๋งค์ฐ ์ ์ ๋ฉ๋ชจ๋ฆฌ ์ ํ์ ๋ณด๊ณ dp๋ฅผ ์ฌ์ฉํ๊ธฐ๋ก ๊ฒฐ์ ๋จ์ํ ๋ฌธ์ ์ ์ฃผ์ด์ง N๊ฐ๋ง ๋ณด๊ณ ๋ฐฐ์ด์ ๋ง๋ค๊ธฐ์ 4MB๋ก๋ ํฑ์์ด ๋ถ์กฑํ๋ค. ๋ฐ๋ผ์ ์์๋ก ์ ์ฅํด์ฃผ๋ ๋ณ์๋ฅผ ๋ฐ๋ก ๋ง๋ค์ด ์ฌ์ฉ ์ฝ๋ ์ค๋ช
max_arr = [int(x) for x in sys.stdin.readline().rstrip().split()] min_arr = copy.copy(m..
๐งฉ Problem Solving/[๋ฐฑ์ค]
https://www.acmicpc.net/problem/16928 16928๋ฒ: ๋ฑ๊ณผ ์ฌ๋ค๋ฆฌ ๊ฒ์ ์ฒซ์งธ ์ค์ ๊ฒ์ํ์ ์๋ ์ฌ๋ค๋ฆฌ์ ์ N(1 ≤ N ≤ 15)๊ณผ ๋ฑ์ ์ M(1 ≤ M ≤ 15)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์๋ ์ฌ๋ค๋ฆฌ์ ์ ๋ณด๋ฅผ ์๋ฏธํ๋ x, y (x < y)๊ฐ ์ฃผ์ด์ง๋ค. x๋ฒ ์นธ์ ๋์ฐฉํ๋ฉด, y๋ฒ ์นธ์ผ www.acmicpc.net ์์ด๋์ด 1. bfs ์ฃผ์ฌ์๋ฅผ ์ ํ(1 ~ 6)ํ ์ ์๋ ์ ๊ณผ ์ต๋จ ํ์๋ฅผ ๊ตฌํดํ๋ค๋ ์ ์ bfs๋ฅผ ์ ํ ๋ฑ๊ณผ ์ฌ๋ค๋ฆฌ๋ง ์ ์ฒดํฌํด์ฃผ๋ฉด ๋๋ ๋ฌธ์ . ์ฝ๋ ์ค๋ช
deq = deque() deq.append([1, 0]) visited[1] = True while deq: po, count = deq.popleft() if po == 100: print(..
๐งฉ Problem Solving/[๋ฐฑ์ค]
https://www.acmicpc.net/problem/5525 5525๋ฒ: IOIOI N+1๊ฐ์ I์ N๊ฐ์ O๋ก ์ด๋ฃจ์ด์ ธ ์์ผ๋ฉด, I์ O์ด ๊ต๋๋ก ๋์ค๋ ๋ฌธ์์ด์ PN์ด๋ผ๊ณ ํ๋ค. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O๊ฐ N๊ฐ) I์ O๋ก๋ง ์ด๋ฃจ์ด์ง ๋ฌธ์์ด S์ ์ ์ N์ด ์ฃผ์ด์ก์ ๋, S์์ PN์ด ๋ช www.acmicpc.net ์ค๋๋ง์ ๋ถ๋ถ์ ์๊ฐ ์๋ ๋ฌธ์ ์์ด๋์ด 1. ๊ฐ์ฅ ๋จผ์ ๋ ์ค๋ฅธ ๊ฑด ์ฌ๋ผ์ด์ฑ ๋จ์ํ๊ฒ ์๊ฐํด์ ๊ทธ๋ฅ Pn ํฌ๊ธฐ๋งํผ ์๋ผ์ ํ์ํ๋ค. ์์ด๋์ด๊ฐ ๋๋ฌด ์ฌ์ด๋งํผ ๋ถ๋ถ์ ์ 50์ ๋ง ์คฌ๋ค. 2. ์๊ฐ ์ด๊ณผ๋ฅผ ํผํ๋ ค๋ฉด ์ด๋ฒ์ ์๊ฒ ๋๋๋ฐ, ํ์ด์ฌ์์ arr [a:b]์ ์๊ฐ ๋ณต์ก๋๋ O(b - a)๋ผ๊ณ ํ๋ค. ์ฌ๋ผ์ด์ค๋ฅผ ์ต๋ํ ๋ ์ฐ๊ณ ๋ฐ๋ณต..