์ ์ฒด ๊ธ
[๋ฐฑ์ค | BOJ] ๊ฐํฌ์ ํจ๊ป ํ๋ 1ํ ์ฝ๋ฉ ํ ์คํธ ํ๊ธฐ
์์ฆ ๋ฐฑ์ค์์ ๋ฌธ์ ๋ฅผ ์ข ํ๊ณ ์๋ค. ์ด๋ ค์ด ๊ณ ๊ธ์๊ณ ๋ฆฌ์ฆ๋ณด๋ค๋ ๋ํ๋ ์ฝ๋ฉํ ์คํธ์์ ์์ฃผ ๋ณด์ด๋ ์๊ณ ๋ฆฌ์ฆ ์์ฃผ๋ก ์ฐ์ตํ๋ ค๊ณ ํ๋ค. Codeforces์ Round๋, ๋ฐฑ์ค์ ๋ํ๋, Atcoder์ Contest ๋ชจ๋ ์ฐธ ์ข์ง๋ง, ์ ๋ถ์ด ๊ตฐ์ธ์ธ์ง๋ผ ์ฝ๊ฒ ์์ํ์ง ๋ชปํ๊ณ ์๋ค. ๊ฐํฌ์ ํจ๊ป ํ๋ 1ํ ์ฝ๋ฉ ํ ์คํธ www.acmicpc.net ์ค๋ ๊ด์ฐฎ์ ์๊ฐ๋์ ๋ํ๊ฐ ์ด๋ ค์ ์ฐธ๊ฐํ๊ฒ ๋๋ค. ๋ฌธ์ ๋ค์ ์ฌ๋ฐ์๊ณ , ๋ค์ํ ์๊ณ ๋ฆฌ์ฆ๋ค์ด ๋ฌธ์ ์ ์ ๋ น์์์ด์ ์ด๋ ๊ฒ์ ๋ ๊ฒ ํ์ด๋ณด๊ธฐ๋ ํ๋ค. ๊ณต์ง์ฌํญ์์ ๋ฏธ๋ฆฌ "๋น ๋ฅธ ์ ์ถ๋ ฅ"์ ์ฌ์ฉํ๋ผ๊ณ ์กฐ์ธํ์๋๋ฐ, ๊ฝค ํ ์คํธ์ผ์ด์ค๋ค์ด ๋ฌด๊ฑฐ์ด ๋ชจ์์ด๋ค. ํ์ด์ฌ์ผ๋ก ํ๊ฒน๊ฒ ๋์๊ฐ๋ค. ์ ๋ฒ ์๋ช ์ฌ๋ SMUPC์์๋ 2๋ฌธ์ ๋ง ํ๊ณ ๋ํ๋ฅผ ๋ง๋ฌด๋ฆฌํ์๋๋ฐ, ์ด๋ฒ ๋ํ์์๋ 8๋ฌธ์ ์ค์์ 6๋ฌธ..
[ํ์ด์ฌ | Python] ํธ๋ผ์ด (Trie) ์๋ฃ๊ตฌ์กฐ
๋ฌธ์์ด์ ํญ์ ์ด๋ ต๋ค. KMP๋ ๊ทธ๋ ๊ณ , digit์ผ๋ก ์ ๋ ฌํ๋ ๊ฒ๋ ๊ทธ๋ ๊ณ , ์๋ฉด ์์๋ก ๋จธ๋ฆฌ์ํ์ง๋ ๋ถ์ผ. ๊ทธ๋งํผ ์ด๋ ต๊ฒ ๋ง๋ค๋ฉด ํจ์ฌ ์ด๋ ต๊ฒ๋ ๋ง๋ค ์ ์๋ค๋ ์ด์ผ๊ธฐ๊ฒ ์ง. ์ค๋์ ํธ๋ผ์ด๋ฅผ ๊ณต๋ถํ๋ค. Radix tree / Prefix tree ๋ผ๊ณ ๋ ๋ถ๋ฆฌ๋๋ฐ, ํ ๋จ์ด์ ์ ๋์ฌ(์ ๋์ด)๋ฅผ ๋ชจ๋ ์ ์ฅํ๊ณ ์๋ค. (ํด๋น ๋จ์ด์ ๋๋ฌํ๊ธฐ๊น์ง์ ๋ฌธ์๋ค์ ์ ์ฅํ๋ค) donghoon ์ด๋ผ๋ ๋จ์ด๋ฅผ ๋ณด๋ฉด, dong ๋ ์ ๋์ฌ๊ฐ ๋ ์ ์๊ณ , do ๋ ์ ๋์ฌ๊ฐ ๋ ์ ์๋ค. ํธ๋ผ์ด์์๋ ์ด ๋จ์ด๋ค์ด ์๋ก ํฌํจ๊ด๊ณ์ ์๋ค๋ ๊ฒ์ ์๋ ค์ค๋ค. ํธ๋ผ์ด์ "app", "ant", "apple"์ด๋ผ๋ ๋จ์ด๋ค์ ์ ์ฅํ๋ค๊ณ ํ์. ํธ๋ผ์ด์๋ ์ง๊ธ๊น์ง์ ๋ชจ๋ ๋จ์ด์ ์์ทจ๋ฅผ ์ ์ฅํ๋ค๊ณ ํ๋ค. ๋จ์ด์ ๊ฐ ๊ธ์๋ง๋ค, ์กด์ฌํ์ง ์์ผ๋ฉด ์..
[ํ๋ก๊ทธ๋๋จธ์ค | Programmers] ์๊ฐ ์ฝ๋ ์ฑ๋ฆฐ์ง ์์ฆ2 5์ ๋ฌธ์ ํ์ด
ํ๋ก๊ทธ๋๋จธ์ค์์ ์๊ฐ ์ฝ๋ ์ฑ๋ฆฐ์ง๋ฅผ ์งํํ๋ค ! ์๊ฐ์ด ์ ์ ํ ์๊ฐ๋์ ์กํ์ ์ฌ์ ๋กญ๊ฒ ์ฐธ์ฌํ ์ ์์๋ค. 4์๋ฌ์ ํ ๋ฒ, ์ด๋ฒ ๋ฌ์ ํ ๋ฒ์ด ์์ฆ 2 ์ฑ๋ฆฐ์ง์๋๋ฐ, ๋๋ ์ด๋ฒ ์ฑ๋ฆฐ์ง๋ฅผ ๋ ๋ฒ์งธ ๋ํ๊ฐ ๋ผ์์ผ ์ ํ๋ค. ๋ ๋ฒ์งธ ๋ํ๊น์ง ์ด 8๋ฌธ์ ์ค์ 4๋ฌธ์ ๋ง ํ์ด๋ ์ด๋ฒคํธ์ ์๋ชจํ ์ ์๋ค๋๋ฐ, ์ด๋ฒ์ 3๋ฌธ์ ๋ฅผ ํ๋ฉด์ ์์ฝ๊ฒ ์๋ชจ๋ ํ์ง ๋ชปํ๋ค. ์ด๋ฒ ๋ฌ ์ฑ๋ฆฐ์ง์์๋ 6546๋ช ์ค 53์๋ฅผ ๋ฌ์ฑํ๋ค ! ๊ฐ์ธ์ ์ผ๋ก DP๊ฐ ๊ต์ฅํ ์ฝํ ํธ์ด๋ผ๊ณ ์๊ฐํ๋๋ฐ, ์ด๋ฒ ๋ฌธ์ ์ ์์๋ ๊ตฌํ / ๊ทธ๋ฆฌ๋ / ์๋ฃ๊ตฌ์กฐ / ๊ทธ๋ํ ์ชฝ์ผ๋ก ์ถ์ ๋ผ์ 3๋ฌธ์ ๋ฅผ ๋ง์๋ค. 1. ์ฝ์์ ๊ฐ์์ ๋ง์ ์ฝ์์ ๊ฐ์๊ฐ ์ง์๋ฉด ๋ํ๊ณ , ํ์๋ฉด ๋นผ์ผ ํ๋ค. ์ฝ์์ ๊ฐ์๊ฐ ํ์์ธ ๊ฒฝ์ฐ๋ ์ ๊ณฑ์์ธ ๊ฒฝ์ฐ์ด๊ณ , ์์ ๋ฒ์๊ฐ $1000$ ์ด๋๊น $3..
[๋ฐฑ์ค | BOJ] ์๋ช ์ฌ์๋ํ๊ต SMUPC ํ์ด๋ณด๊ธฐ
13์๋ถํฐ 17์๊น์ง 4์๊ฐ์ง๋ฆฌ ์คํ์ฝํ ์คํธ๊ฐ ์ด๋ ธ๋๋ฐ, ๋ค๋ฅธ ๋ฌธ์ ํธ๋๋ผ 30๋ถ๋์๋ฐ์ ๋ชป ํ์๋ค. ์ค๋ ๋ผ์ ์์นจ์ ๋ฌธ์ ํ์ด๋ณด๊ณ ํ์ด. ๋ฌด๋ํ๊ณ ์ฌ๋ฐ์๋ ๋ฌธ์ ์ ์ด์ง๋ง, ํ ์ชฝ์ ์น์ฐ์ณ์ง ์๊ณ ๋ฆฌ์ฆ ์ ์ด๋ผ๋ ์ ์ด ์์ฝ๋ค. ์ 1ํ ์๋ช ์ฌ์๋ํ๊ต ๊ต๋ด ์๊ณ ๋ฆฌ์ฆ ๊ฒฝ์ง๋ํ (SMUPC) Open www.acmicpc.net 21734: SMUPC์ ๋ฑ์ฅ ๊ฐ ์ํ๋ฒณ์ ์์คํค ์ฝ๋๋ฅผ ๊ตฌํ ๋ค์, ๊ฐ ์๋ฆฌ์๋ฅผ ๋ํ ๋งํผ ์ํ๋ฒณ์ ์ถ๋ ฅํ๋ฉด ๋๋ค. for i in input(): print(i * sum(list(map(int, list(str(ord(i))))))) 21735: ๋๋ฉ์ด ๊ตด๋ฆฌ๊ธฐ dp๋ก ํ๋ค๊ฐ ์๊ฐ๊น์ง ์ ์ฅ์ ์ด๋ป๊ฒ ํ์ง,, ๋ผ๋ ์๊ฐ์ ๋ํ๋ ์๋ ๋๊ธฐ๊ณ ์์นจ์ ๋ค์ ๋ณด๋ dfs๋ก ํ๊ณ ๋ด๋ ค๊ฐ๋ฉด ๋๋ ๋ฌธ์ ..