๐งฉ Problem Solving/[๋ฐฑ์ค]
https://www.acmicpc.net/problem/1504 1504๋ฒ: ํน์ ํ ์ต๋จ ๊ฒฝ๋ก ์ฒซ์งธ ์ค์ ์ ์ ์ ๊ฐ์ N๊ณผ ๊ฐ์ ์ ๊ฐ์ E๊ฐ ์ฃผ์ด์ง๋ค. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) ๋์งธ ์ค๋ถํฐ E๊ฐ์ ์ค์ ๊ฑธ์ณ์ ์ธ ๊ฐ์ ์ ์ a, b, c๊ฐ ์ฃผ์ด์ง๋๋ฐ, a๋ฒ ์ ์ ์์ b๋ฒ ์ ์ ๊น์ง ์๋ฐฉํฅ ๊ธธ์ด ์กด www.acmicpc.net ์์ด๋์ด 1. ๊ฐ์ค์น๊ฐ ์๋ ๊ทธ๋ํ ๋ค์ต์คํธ๋ผ ์๋๋ฉด ํ๋ก์ด๋ ๋ ๊ฐ๋ฅผ ์๊ฐํ๋ค. ๋์ ์ v1, v2๋ฅผ ์ง๋๋ ์ต๋จ๊ฒฝ๋ก๋ ๊ฐ๊ฐ์ ์ต๋จ๊ฒฝ๋ก๋ค์ ๋ํ ๊ฒ๊ณผ ๊ฐ์ผ๋ฏ๋ก ๋ค์ต์คํธ๋ผ๋ฅผ ์ฌ๋ฌ ๋ฒ ์ฌ์ฉํ๋ฉด ๋๋ค. '1 -> N' = '1 -> v1' + 'v1 -> v2' + 'v2 ->N' ๊ฐ์ด ๊ณ์ฐํด์ ๋ ์ ์ ์ ์ง๋๋ ์ต๋จ๊ฒฝ๋ก๋ฅผ ๊ตฌํ๋ค. ๋ฃจํธ๋ 1 -> v1 -..
๐งฉ Problem Solving/[๋ฐฑ์ค]
https://www.acmicpc.net/problem/12100 12100๋ฒ: 2048 (Easy) ์ฒซ์งธ ์ค์ ๋ณด๋์ ํฌ๊ธฐ N (1 ≤ N ≤ 20)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์๋ ๊ฒ์ํ์ ์ด๊ธฐ ์ํ๊ฐ ์ฃผ์ด์ง๋ค. 0์ ๋น ์นธ์ ๋ํ๋ด๋ฉฐ, ์ด์ธ์ ๊ฐ์ ๋ชจ๋ ๋ธ๋ก์ ๋ํ๋ธ๋ค. ๋ธ๋ก์ ์ฐ์ฌ ์๋ ์๋ 2 www.acmicpc.net ์์ด๋์ด 1. ๊ตฌํ์ด ๋จผ์ ๋ฌธ์ ๋ฅผ ๋ณด๊ณ N์ต๋๊ฐ 20์ด๊ณ ์ด๋๋ 5๋ฒ ํ๋ฏ๋ก ๋ฌธ์ ๊ฐ ๋งํ ๊ทธ๋๋ก ๊ตฌํํ๋ฉด ๋๊ฒ ๋ค๊ณ ์๊ฐ. ์, ํ, ์ข, ์ฐ ์ด๋ ์ค์ '์ข'๋ก ์ด๋ํ๋ ๊ฒ๋ถํฐ ๊ตฌํํ๋ฉด ๋๋จธ์ง๋ ์ฝ๊ฒ ๋ง๋ค ์ ์๋ค. ๋ง๋ค์๋ก ๋ณ์๋ if๋ฌธ์ด ๋ง์์ ธ ๋ค์ ๋ฐ๊ณ ์ฒ์๋ถํฐ ์์ฑํ๋ค. ๋๋ฌด ๋ง์ ๋ณ์๋ ํ์ ์๋ค. ์ด๊ฑด ๋ค๋ฅธ ๊ตฌํ ๋ฌธ์ ๋ ๋ง์ฐฌ๊ฐ์ง๋ผ๊ณ ์๊ฐ. '์ด๋์ํฌ ๋ธ๋ก'๊ณผ..
๐งฉ Problem Solving/[๋ฐฑ์ค]
https://www.acmicpc.net/problem/15654 15654๋ฒ: N๊ณผ M (5) N๊ฐ์ ์์ฐ์์ ์์ฐ์ M์ด ์ฃผ์ด์ก์ ๋, ์๋ ์กฐ๊ฑด์ ๋ง์กฑํ๋ ๊ธธ์ด๊ฐ M์ธ ์์ด์ ๋ชจ๋ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. N๊ฐ์ ์์ฐ์๋ ๋ชจ๋ ๋ค๋ฅธ ์์ด๋ค. N๊ฐ์ ์์ฐ์ ์ค์์ M๊ฐ๋ฅผ ๊ณ ๋ฅธ ์์ด www.acmicpc.net ์์ด๋์ด 1. ๋ฐฑํธ๋ํน ์ด๋ฏธ N๊ณผ M ๋ฌธ์ ๋ฅผ ํ์ด๋ด์ ๋ฐ๋ก ๋ ์ฌ๋๋ค. ๊น์ด๊ฐ M์ด ๋ ๋๋ง๋ค ์ฃผ์ด์ง ์ซ์๋ค์ ํ์ํ๋ฉด ๋๋ค. ์ด ๋ฌธ์ ์์๋ ์์ด, ์ค๋ณต๋์ง ์์ ์ซ์๋ค์ ๋์ดํด์ผ ํ๋ฏ๋ก ์ด๋ฏธ ์ถ๊ฐ๋ ์ซ์๊ฐ ์์ผ๋ฉด continue๋ก ๋๊ฒจ์ค๋ค. ์ ์ฒด ์ฝ๋ N, M = map(int, input().split()) numbers = [int(x) for x in input().split()] ..
๐งฉ Problem Solving/[๋ฐฑ์ค]
https://www.acmicpc.net/problem/1202 1202๋ฒ: ๋ณด์ ๋๋ ์ฒซ์งธ ์ค์ N๊ณผ K๊ฐ ์ฃผ์ด์ง๋ค. (1 ≤ N, K ≤ 300,000) ๋ค์ N๊ฐ ์ค์๋ ๊ฐ ๋ณด์์ ์ ๋ณด Mi์ Vi๊ฐ ์ฃผ์ด์ง๋ค. (0 ≤ Mi, Vi ≤ 1,000,000) ๋ค์ K๊ฐ ์ค์๋ ๊ฐ๋ฐฉ์ ๋ด์ ์ ์๋ ์ต๋ ๋ฌด๊ฒ Ci๊ฐ ์ฃผ์ด์ง๋ค. (1 ≤ Ci www.acmicpc.net ์์ด๋์ด 1. ๋ณด์์ ๊ฐ๋ฐฉ์ ์ด๋ป๊ฒ ๋ด์ ๊ฑด๊ฐ. ๋จ์ํ ์ด์ค ๋ฐ๋ณต๋ฌธ์ผ๋ก ๋น๊ตํ๋ฉด ์๊ฐ ์ด๊ณผ๊ฐ ๋๋ค. ๋ค์ ๋ฌธ์ ๋ฅผ ์ฝ๊ณ ๋ฌธ์ ์ ์๋ ํํธ๋ฅผ ๋ณด๊ณ ๊ฐ์ ์ก์๋ค. ๋จผ์ ๋ณด์ ๋ฆฌ์คํธ์ ๊ฐ๋ฐฉ ๋ฆฌ์คํธ๋ฅผ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํ๊ณ ๊ฐ ๊ฐ๋ฐฉ์ ๊ธฐ์ค์ผ๋ก ๋ณด์์ด ๊ฐ๋ฐฉ์ ๋ฃ์ ์ ์๋์ง ํ์ธํ๋ค. ๊ฐ๋ฐฉ์ ๋ฃ์ ์ ์๋ ๋ณด์ ์ค ๊ฐ์น๊ฐ ๊ฐ์ฅ ํฐ ๊ฑธ ๋ฃ์ด์ฃผ๋ฉด ๋๋ค...
๐งฉ Problem Solving/[๋ฐฑ์ค]
https://www.acmicpc.net/problem/13913 13913๋ฒ: ์จ๋ฐ๊ผญ์ง 4 ์๋น์ด๋ ๋์๊ณผ ์จ๋ฐ๊ผญ์ง์ ํ๊ณ ์๋ค. ์๋น์ด๋ ํ์ฌ ์ N(0 ≤ N ≤ 100,000)์ ์๊ณ , ๋์์ ์ K(0 ≤ K ≤ 100,000)์ ์๋ค. ์๋น์ด๋ ๊ฑท๊ฑฐ๋ ์๊ฐ์ด๋์ ํ ์ ์๋ค. ๋ง์ฝ, ์๋น์ด์ ์์น๊ฐ X์ผ www.acmicpc.net ์จ๋ฐ๊ผญ์ง ์๋ฆฌ์ฆ ๋ง์ง๋ง ์จ๋ฐ๊ผญ์ง 1 ๋จผ์ ํ์ด๋ณด๋ ๊ฒ ์ข๋ค. ์์ด๋์ด 1. bfs ํ์ x +1, x - 1, x * 2๋ฅผ ์กฐ๊ฑด์ ๋ง์ผ๋ฉด ์ถ๊ฐํด์ค๋ค. ํ์ ์์น์ ์๊ฐ ๊ทธ๋ฆฌ๊ณ ์ง๋์จ ๊ธธ๋ ๊ฐ์ด ๋ฃ์ด์ค๋ค. ๋์ฐฉํ๋ฉด ๋์ฐฉ ์๊ฐ๊ณผ ๊ฒฝ๋ก๋ฅผ ๋ฆฌํด ํ ์ถ๋ ฅ. ์ ์ฒด ์ฝ๋ from collections import deque N, K = map(int,input().split(..
๐งฉ Problem Solving/[๋ฐฑ์ค]
https://www.acmicpc.net/problem/12851 12851๋ฒ: ์จ๋ฐ๊ผญ์ง 2 ์๋น์ด๋ ๋์๊ณผ ์จ๋ฐ๊ผญ์ง์ ํ๊ณ ์๋ค. ์๋น์ด๋ ํ์ฌ ์ N(0 ≤ N ≤ 100,000)์ ์๊ณ , ๋์์ ์ K(0 ≤ K ≤ 100,000)์ ์๋ค. ์๋น์ด๋ ๊ฑท๊ฑฐ๋ ์๊ฐ์ด๋์ ํ ์ ์๋ค. ๋ง์ฝ, ์๋น์ด์ ์์น๊ฐ X์ผ ๋ www.acmicpc.net ์์ด๋์ด 1. bfs ์ด๋ฏธ ์จ๋ฐ๊ผญ์ง 1๊ณผ 3์ ํ์ด์ ๋์ถฉ ์๊ณ ์๋ค. x - 1, x + 1, x * 2 ํ์ ๋ฃ์ด์ฃผ๋ฉด์ ํ์ํ๋ฉด ๋จ. ๊ฒฝ์ฐ์ ์๋ฅผ ์ด๋ป๊ฒ ๊ตฌํ ์ง ์๊ฐ๋ง ํ๋ฉด ๋๋ค. 2. ๊ฒฝ์ฐ์ ์ ์ญ ํ์์ ํ๋ค๊ฐ ๋งจ ์ฒ์ ๋์ํํ
๋์ฐฉํ ์๊ฐ์ ์ ์ฅํ๊ณ ์ดํ ๋์ํํ
๋์ฐฉํ์ ๋ ์ ์ฅํด๋ ์๊ฐ๊ณผ ๊ฐ๋ค๋ฉด ๊ฒฝ์ฐ์ ์๋ฅผ +1 ํด์ค๋ค. ์ ์ฒด ์ฝ๋ from col..
๐งฉ Problem Solving/[๋ฐฑ์ค]
https://www.acmicpc.net/problem/1043 1043๋ฒ: ๊ฑฐ์ง๋ง ์ง๋ฏผ์ด๋ ํํฐ์ ๊ฐ์ ์ด์ผ๊ธฐ ํ๋ ๊ฒ์ ์ข์ํ๋ค. ํํฐ์ ๊ฐ ๋๋ง๋ค, ์ง๋ฏผ์ด๋ ์ง๋ฏผ์ด๊ฐ ๊ฐ์ฅ ์ข์ํ๋ ์ด์ผ๊ธฐ๋ฅผ ํ๋ค. ์ง๋ฏผ์ด๋ ๊ทธ ์ด์ผ๊ธฐ๋ฅผ ๋งํ ๋, ์๋ ๊ทธ๋๋ก ์ง์ค๋ก ๋งํ๊ฑฐ๋ ์์ฒญ๋๊ฒ www.acmicpc.net ์์ด๋์ด 1. ๋ฐ๋ณต๋ฌธ ๋ฌธ์ ๋๋์ด ์ง์ค์ ์๋ ์ฌ๋์ด ์ข๋น๊ฐ์ด ๊ฐ์ผ์ํค๋ ๊ฒ์ด๋ผ ์๊ฐ ๊ทธ๋์ ์ง์ค์ ์๋ ์ฌ๋๊ณผ ๊ฐ์ด ์๋ ์ฌ๋๋ค์ ์ง์ค์ ์๋ ์ฌ๋์ผ๋ก ๋ฐ๊ฟจ๋ค. ๊ทผ๋ฐ ์ด๋ฌ๋ฉด ์ง์ค์ ์๋ ์ฌ๋๋ค์ด ๋ฐ๋์ด์ ์ ์ฒด ํํฐ๋ฅผ ๋ ํ์ํด์ผ ํ๊ณ ์ด๋ฅผ ๊ณ์ ๋ฐ๋ณตํด์ผ ํด์ ์คํจํ๋ค. 2. ๊ทธ๋ํ ๊ทธ๋ฌ๋ค๊ฐ ๋์์ ํ ๋ฒ์ ํด์ผ ๋๋ค๋ ๊ฒ์ ๊นจ๋ซ๊ณ ๊ทธ๋ํ๋ฅผ ์ฌ์ฉํ๊ธฐ๋ก ๊ฒฐ์ ๊ฐ ํํฐ๋ง๋ค ์๋ ์ฌ๋๋ค์ ๋ ๋ช
์ฉ ์๋ฐฉํฅ์ผ๋ก ์ด์ด..
๐งฉ Problem Solving/[๋ฐฑ์ค]
https://www.acmicpc.net/problem/2467 2467๋ฒ: ์ฉ์ก ์ฒซ์งธ ์ค์๋ ์ ์ฒด ์ฉ์ก์ ์ N์ด ์
๋ ฅ๋๋ค. N์ 2 ์ด์ 100,000 ์ดํ์ ์ ์์ด๋ค. ๋์งธ ์ค์๋ ์ฉ์ก์ ํน์ฑ๊ฐ์ ๋ํ๋ด๋ N๊ฐ์ ์ ์๊ฐ ๋น์นธ์ ์ฌ์ด์ ๋๊ณ ์ค๋ฆ์ฐจ์์ผ๋ก ์
๋ ฅ๋๋ฉฐ, ์ด ์๋ค์ ๋ชจ๋ - www.acmicpc.net ์์ด๋์ด 1. ์กฐํฉ ๋จ์ํ๊ฒ ๋ฆฌ์คํธ์ ์๋ ๊ฐ ์ค์์ ๋ ๊ฐ๋ฅผ ๋ฝ์ ๊ณ์ฐํ๋ ์ฝ๋๋ฅผ ์งฐ๋ค. ์๊ฐ ์ด๊ณผ ๋ฐ์ ์๊ฐํด๋ณด๋๊น ์กฐํฉ์ด๋ฉด 100000C2์ธ๋ฐ 1์ด๋ก๋ ํ๋ ์๋ค. 2. ๋ฌธ์ ์ ์ค๋ฆ์ฐจ์์ด ํํธ ๋ฏธ๋ฆฌ ์ ๋ ฌ์ด ๋์ด์์ผ๋๊น ์ด๊ฑธ ์ด์ฉํ๋ผ๋ ์๋ฏธ๋ก ํด์ ์ด๋ถ ํ์๊ณผ ๋น์ทํ๊ฒ ์ข์ฐ์์ ํ๋์ฉ ์ขํ๊ฐ๋ฉฐ ์ต์๊ฐ(0์ ๊ฐ๊น์ด ๊ฐ)์ ์ฐพ๊ธฐ๋ก ๊ฒฐ์ . ์ฝ๋ ์ค๋ช
while l < r: cur_value =..