โ๏ธ ์ฝํ
์ค๋น/DFS, BFS
๋ณธ ๊ฒ์๊ธ์ PC๋ฒ์ ์ ์ต์ ํ ๋์ด์์ต๋๋ค. www.acmicpc.net/problem/1260 1260๋ฒ: DFS์ BFS ์ฒซ์งธ ์ค์ ์ ์ ์ ๊ฐ์ N(1 โค N โค 1,000), ๊ฐ์ ์ ๊ฐ์ M(1 โค M โค 10,000), ํ์์ ์์ํ ์ ์ ์ ๋ฒํธ V๊ฐ ์ฃผ์ด์ง๋ค. ๋ค์ M๊ฐ์ ์ค์๋ ๊ฐ์ ์ด ์ฐ๊ฒฐํ๋ ๋ ์ ์ ์ ๋ฒํธ๊ฐ ์ฃผ์ด์ง๋ค. ์ด๋ค ๋ ์ ์ ์ฌ www.acmicpc.net ์
๋ ฅ ์ฒซ์งธ ์ค์ ์ ์ ์ ๊ฐ์ N(1 โค N โค 1,000), ๊ฐ์ ์ ๊ฐ์ M(1 โค M โค 10,000), ํ์์ ์์ํ ์ ์ ์ ๋ฒํธ V๊ฐ ์ฃผ์ด์ง๋ค. ๋ค์ M๊ฐ์ ์ค์๋ ๊ฐ์ ์ด ์ฐ๊ฒฐํ๋ ๋ ์ ์ ์ ๋ฒํธ๊ฐ ์ฃผ์ด์ง๋ค. ์ด๋ค ๋ ์ ์ ์ฌ์ด์ ์ฌ๋ฌ ๊ฐ์ ๊ฐ์ ์ด ์์ ์ ์๋ค. ์
๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ ๊ฐ์ ์ ์๋ฐฉํฅ์ด๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ DFS๋ฅผ..
โ๏ธ ์ฝํ
์ค๋น/Shortest Path
๋ณธ ๊ฒ์๊ธ์ PC๋ฒ์ ์ ์ต์ ํ ๋์ด์์ต๋๋ค. 1956๋ฒ: ์ด๋ ์ฒซ์งธ ์ค์ V์ E๊ฐ ๋น์นธ์ ์ฌ์ด์ ๋๊ณ ์ฃผ์ด์ง๋ค. (2 โค V โค 400, 0 โค E โค V(V-1)) ๋ค์ E๊ฐ์ ์ค์๋ ๊ฐ๊ฐ ์ธ ๊ฐ์ ์ ์ a, b, c๊ฐ ์ฃผ์ด์ง๋ค. a๋ฒ ๋ง์์์ b๋ฒ ๋ง์๋ก ๊ฐ๋ ๊ฑฐ๋ฆฌ๊ฐ c์ธ ๋๋ก๊ฐ ์๋ค๋ ์ www.acmicpc.net ์
๋ ฅ ์ฒซ์งธ ์ค์ V์ E๊ฐ ๋น์นธ์ ์ฌ์ด์ ๋๊ณ ์ฃผ์ด์ง๋ค. (2 โค V โค 400, 0 โค E โค V(V-1)) ๋ค์ E๊ฐ์ ์ค์๋ ๊ฐ๊ฐ ์ธ ๊ฐ์ ์ ์ a, b, c๊ฐ ์ฃผ์ด์ง๋ค. a๋ฒ ๋ง์์์ b๋ฒ ๋ง์๋ก ๊ฐ๋ ๊ฑฐ๋ฆฌ๊ฐ c์ธ ๋๋ก๊ฐ ์๋ค๋ ์๋ฏธ์ด๋ค. (a โ b์์ ์ฃผ์) ๊ฑฐ๋ฆฌ๋ 10,000 ์ดํ์ ์์ฐ์์ด๋ค. (a, b) ์์ด ๊ฐ์ ๋๋ก๊ฐ ์ฌ๋ฌ ๋ฒ ์ฃผ์ด์ง์ง ์๋๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ์ต์..
โ๏ธ ์ฝํ
์ค๋น/DFS, BFS
www.acmicpc.net/problem/1707 1707๋ฒ: ์ด๋ถ ๊ทธ๋ํ ์
๋ ฅ์ ์ฌ๋ฌ ๊ฐ์ ํ
์คํธ ์ผ์ด์ค๋ก ๊ตฌ์ฑ๋์ด ์๋๋ฐ, ์ฒซ์งธ ์ค์ ํ
์คํธ ์ผ์ด์ค์ ๊ฐ์ K(2โคKโค5)๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ํ
์คํธ ์ผ์ด์ค์ ์ฒซ์งธ ์ค์๋ ๊ทธ๋ํ์ ์ ์ ์ ๊ฐ์ V(1โคVโค20,000)์ ๊ฐ์ ์ ๊ฐ์ www.acmicpc.net ์
๋ ฅ ์
๋ ฅ์ ์ฌ๋ฌ ๊ฐ์ ํ
์คํธ ์ผ์ด์ค๋ก ๊ตฌ์ฑ๋์ด ์๋๋ฐ, ์ฒซ์งธ ์ค์ ํ
์คํธ ์ผ์ด์ค์ ๊ฐ์ K(2โคKโค5)๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ํ
์คํธ ์ผ์ด์ค์ ์ฒซ์งธ ์ค์๋ ๊ทธ๋ํ์ ์ ์ ์ ๊ฐ์ V(1โคVโค20,000)์ ๊ฐ์ ์ ๊ฐ์ E(1โคEโค200,000)๊ฐ ๋น ์นธ์ ์ฌ์ด์ ๋๊ณ ์์๋๋ก ์ฃผ์ด์ง๋ค. ๊ฐ ์ ์ ์๋ 1๋ถํฐ V๊น์ง ์ฐจ๋ก๋ก ๋ฒํธ๊ฐ ๋ถ์ด ์๋ค. ์ด์ด์ ๋์งธ ์ค๋ถํฐ E๊ฐ์ ์ค์ ๊ฑธ์ณ ๊ฐ์ ์ ๋ํ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋๋ฐ..
โ๏ธ ์ฝํ
์ค๋น/DFS, BFS
www.acmicpc.net/problem/7562 7562๋ฒ: ๋์ดํธ์ ์ด๋ ์ฒด์คํ ์์ ํ ๋์ดํธ๊ฐ ๋์ฌ์ ธ ์๋ค. ๋์ดํธ๊ฐ ํ ๋ฒ์ ์ด๋ํ ์ ์๋ ์นธ์ ์๋ ๊ทธ๋ฆผ์ ๋์์๋ค. ๋์ดํธ๊ฐ ์ด๋ํ๋ ค๊ณ ํ๋ ์นธ์ด ์ฃผ์ด์ง๋ค. ๋์ดํธ๋ ๋ช ๋ฒ ์์ง์ด๋ฉด ์ด ์นธ์ผ๋ก ์ด๋ํ ์ www.acmicpc.net ์
๋ ฅ ์
๋ ฅ์ ์ฒซ์งธ ์ค์๋ ํ
์คํธ ์ผ์ด์ค์ ๊ฐ์๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ํ
์คํธ ์ผ์ด์ค๋ ์ธ ์ค๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. ์ฒซ์งธ ์ค์๋ ์ฒด์คํ์ ํ ๋ณ์ ๊ธธ์ด l(4 โค l โค 300)์ด ์ฃผ์ด์ง๋ค. ์ฒด์คํ์ ํฌ๊ธฐ๋ l ร l์ด๋ค. ์ฒด์คํ์ ๊ฐ ์นธ์ ๋ ์์ ์ {0, ..., l-1} ร {0, ..., l-1}๋ก ๋ํ๋ผ ์ ์๋ค. ๋์งธ ์ค๊ณผ ์
์งธ ์ค์๋ ๋์ดํธ๊ฐ ํ์ฌ ์๋ ์นธ, ๋์ดํธ๊ฐ ์ด๋ํ๋ ค๊ณ ํ๋ ์นธ์ด ์ฃผ์ด์ง๋ค. ์ถ๋ ฅ ๊ฐ ํ
..
โ๏ธ ์ฝํ
์ค๋น/Dynamic Programming
www.acmicpc.net/problem/2565 2565๋ฒ: ์ ๊น์ค ์ฒซ์งธ ์ค์๋ ๋ ์ ๋ด๋ ์ฌ์ด์ ์ ๊น์ค์ ๊ฐ์๊ฐ ์ฃผ์ด์ง๋ค. ์ ๊น์ค์ ๊ฐ์๋ 100 ์ดํ์ ์์ฐ์์ด๋ค. ๋์งธ ์ค๋ถํฐ ํ ์ค์ ํ๋์ฉ ์ ๊น์ค์ด A์ ๋ด๋์ ์ฐ๊ฒฐ๋๋ ์์น์ ๋ฒํธ์ B์ ๋ด๋์ ์ฐ๊ฒฐ๋๋ www.acmicpc.net ์
๋ ฅ ์ฒซ์งธ ์ค์๋ ๋ ์ ๋ด๋ ์ฌ์ด์ ์ ๊น์ค์ ๊ฐ์๊ฐ ์ฃผ์ด์ง๋ค. ์ ๊น์ค์ ๊ฐ์๋ 100 ์ดํ์ ์์ฐ์์ด๋ค. ๋์งธ ์ค๋ถํฐ ํ ์ค์ ํ๋์ฉ ์ ๊น์ค์ด A์ ๋ด๋์ ์ฐ๊ฒฐ๋๋ ์์น์ ๋ฒํธ์ B์ ๋ด๋์ ์ฐ๊ฒฐ๋๋ ์์น์ ๋ฒํธ๊ฐ ์ฐจ๋ก๋ก ์ฃผ์ด์ง๋ค. ์์น์ ๋ฒํธ๋ 500 ์ดํ์ ์์ฐ์์ด๊ณ , ๊ฐ์ ์์น์ ๋ ๊ฐ ์ด์์ ์ ๊น์ค์ด ์ฐ๊ฒฐ๋ ์ ์๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ๋จ์์๋ ๋ชจ๋ ์ ๊น์ค์ด ์๋ก ๊ต์ฐจํ์ง ์๊ฒ ํ๊ธฐ ์ํด ์์ ์ผ ํ๋ ์ ๊น์ค์ ์ต์ ..
โ๏ธ ์ฝํ
์ค๋น/Dynamic Programming
www.acmicpc.net/problem/11054 11054๋ฒ: ๊ฐ์ฅ ๊ธด ๋ฐ์ดํ ๋ ๋ถ๋ถ ์์ด ์ฒซ์งธ ์ค์ ์์ด A์ ํฌ๊ธฐ N์ด ์ฃผ์ด์ง๊ณ , ๋์งธ ์ค์๋ ์์ด A๋ฅผ ์ด๋ฃจ๊ณ ์๋ Ai๊ฐ ์ฃผ์ด์ง๋ค. (1 โค N โค 1,000, 1 โค Ai โค 1,000) www.acmicpc.net ์
๋ ฅ ์ฒซ์งธ ์ค์ ์์ด A์ ํฌ๊ธฐ N์ด ์ฃผ์ด์ง๊ณ , ๋์งธ ์ค์๋ ์์ด A๋ฅผ ์ด๋ฃจ๊ณ ์๋ Ai๊ฐ ์ฃผ์ด์ง๋ค. (1 โค N โค 1,000, 1 โค Ai โค 1,000) ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ์์ด A์ ๋ถ๋ถ ์์ด ์ค์์ ๊ฐ์ฅ ๊ธด ๋ฐ์ดํ ๋ ์์ด์ ๊ธธ์ด๋ฅผ ์ถ๋ ฅํ๋ค. ํด๊ฒฐ ๋ฐฉ๋ฒ ์ด์ ๋ฌธ์ ์ธ ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด์ ๋ณํ ๋ฌธ์ ์ด๋ค. (์์ง ํ์ง ์์๋ค๋ฉด ์๋ ๋ฌธ์ ๋ฅผ ๋จผ์ ํ์ด๋ณด๋๋ก ํ์.) www.acmicpc.net/problem/11053 11..
โ๏ธ ์ฝํ
์ค๋น/Dynamic Programming
www.acmicpc.net/problem/11053 11053๋ฒ: ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด ์์ด A๊ฐ ์ฃผ์ด์ก์ ๋, ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์๋ฅผ ๋ค์ด, ์์ด A = {10, 20, 10, 30, 20, 50} ์ธ ๊ฒฝ์ฐ์ ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด์ A = {10, 20, 10, 30, 20, 50} ์ด www.acmicpc.net ์
๋ ฅ ์ฒซ์งธ ์ค์ ์์ด A์ ํฌ๊ธฐ N (1 โค N โค 1,000)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค์๋ ์์ด A๋ฅผ ์ด๋ฃจ๊ณ ์๋ Ai๊ฐ ์ฃผ์ด์ง๋ค. (1 โค Ai โค 1,000) ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ์์ด A์ ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด์ ๊ธธ์ด๋ฅผ ์ถ๋ ฅํ๋ค. ํด๊ฒฐ ๋ฐฉ๋ฒ a[i]๋ฅผ ์
๋ ฅ๋ ์์ด, dp[i]๋ฅผ i๋ฒ์งธ๊น์ง ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด์ ๊ธธ์ด๋ผ๊ณ ..
โ๏ธ ์ฝํ
์ค๋น/Dynamic Programming
www.acmicpc.net/problem/2156 2156๋ฒ: ํฌ๋์ฃผ ์์ ํจ์ฃผ๋ ํฌ๋์ฃผ ์์ํ์ ๊ฐ๋ค. ๊ทธ ๊ณณ์ ๊ฐ๋๋, ํ
์ด๋ธ ์์ ๋ค์ํ ํฌ๋์ฃผ๊ฐ ๋ค์ด์๋ ํฌ๋์ฃผ ์์ด ์ผ๋ ฌ๋ก ๋์ฌ ์์๋ค. ํจ์ฃผ๋ ํฌ๋์ฃผ ์์์ ํ๋ ค๊ณ ํ๋๋ฐ, ์ฌ๊ธฐ์๋ ๋ค์๊ณผ ๊ฐ์ ๋ ๊ฐ์ง ๊ท www.acmicpc.net ์
๋ ฅ ์ฒซ์งธ ์ค์ ํฌ๋์ฃผ ์์ ๊ฐ์ n์ด ์ฃผ์ด์ง๋ค. (1โคnโค10,000) ๋์งธ ์ค๋ถํฐ n+1๋ฒ์งธ ์ค๊น์ง ํฌ๋์ฃผ ์์ ๋ค์ด์๋ ํฌ๋์ฃผ์ ์์ด ์์๋๋ก ์ฃผ์ด์ง๋ค. ํฌ๋์ฃผ์ ์์ 1,000 ์ดํ์ ์์ด ์๋ ์ ์์ด๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ์ต๋๋ก ๋ง์ค ์ ์๋ ํฌ๋์ฃผ์ ์์ ์ถ๋ ฅํ๋ค. ํด๊ฒฐ ๋ฐฉ๋ฒ ํฌ๋์ฃผ๋ฅผ ๋ง์ค ์ ์๋ ๋ฐฉ๋ฒ์ ์ด๋ป๊ฒ ๋ ๊น? dp๋ฅผ n๋ฒ์งธ ์๊น์ง ๋ง์ค ๋ ๊ฐ์ฅ ๋ง์ ์์ ํฌ๋์ฃผ, grape๋ฅผ n๋ฒ์งธ ์์ ํฌ๋..
โ๏ธ ์ฝํ
์ค๋น/Dynamic Programming
www.acmicpc.net/problem/10844 10844๋ฒ: ์ฌ์ด ๊ณ๋จ ์ ์ฒซ์งธ ์ค์ ์ ๋ต์ 1,000,000,000์ผ๋ก ๋๋ ๋๋จธ์ง๋ฅผ ์ถ๋ ฅํ๋ค. www.acmicpc.net ์
๋ ฅ ์ฒซ์งธ ์ค์ N์ด ์ฃผ์ด์ง๋ค. N์ 1๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , 100๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ์ ๋ต์ 1,000,000,000์ผ๋ก ๋๋ ๋๋จธ์ง๋ฅผ ์ถ๋ ฅํ๋ค. ํด๊ฒฐ ๋ฐฉ๋ฒ ์ฐ์ ๊ท์น์ ์ฐพ์ ํ์๊ฐ ์๋ค. ๊ธธ์ด๊ฐ 1์ธ ๊ณ๋จ์ ์๋ ๋ช ๊ฐ๊ฐ ์์๊น? 1 2 3 4 5 6 7 8 9 ๋ต์ 9๊ฐ ๊ทธ๋ผ ๊ธธ์ด๊ฐ 2์ธ ๊ณ๋จ์ ์๋? 10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 98 ๋ต์ 17๊ฐ ๊ท์น์ด ๋ณด์ด๋๊ฐ? ๋ณด์ด์ง ์์๋ ๋๋ค. (๋ณธ์ธ๋ ํธ๋๋ฐ ์ค๋๊ฑธ๋ ธ์ผ๋... ์ด ๋ฌธ์ ๋ง์ด ์ด๋ ค์ ..
โ๏ธ ์ฝํ
์ค๋น/Dynamic Programming
www.acmicpc.net/problem/1463 1463๋ฒ: 1๋ก ๋ง๋ค๊ธฐ ์ฒซ์งธ ์ค์ 1๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , 106๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์ ์ N์ด ์ฃผ์ด์ง๋ค. www.acmicpc.net ์
๋ ฅ ์ฒซ์งธ ์ค์ 1๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , 10^6๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์ ์ N์ด ์ฃผ์ด์ง๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ์ฐ์ฐ์ ํ๋ ํ์์ ์ต์๊ฐ์ ์ถ๋ ฅํ๋ค. ํด๊ฒฐ ๋ฐฉ๋ฒ ์ฐ์ ๊ท์น์ ์ฐพ์๋ณด์. ๊ณ์ฐ์์ ๊ฒฝ์ฐ ์ฌ๋ฌ๊ฐ์ง ๊ฒฝ์ฐ์ ์๊ฐ ๋์ฌ ์๋ ์๋ค. N ์ฐ์ฐ ํ์ ๊ณ์ฐ์ 1 1 1 2 1 2/2=1 3 1 3/3=1 4 2 (4-1)/3=1 5 3 (5-1)/2/2=1 6 2 6/3/2=1 7 3 (7-1)/3/2=1 8 3 8/2/2/2=1 9 2 9/3/3=1 10 3 (10-1)/3/3=1 ์ด๋ค ๊ท์น์ ์ฐพ์ ์ ์์๊น? ์ฐ์ ์๊ฐ 1์ฉ ์ปค์ง ..
'C++' ํ๊ทธ์ ๊ธ ๋ชฉ๋ก
๋จ์ถํค
๋ด ๋ธ๋ก๊ทธ
๋ด ๋ธ๋ก๊ทธ - ๊ด๋ฆฌ์ ํ ์ ํ |
Q
Q
|
์ ๊ธ ์ฐ๊ธฐ |
W
W
|
๋ธ๋ก๊ทธ ๊ฒ์๊ธ
๊ธ ์์ (๊ถํ ์๋ ๊ฒฝ์ฐ) |
E
E
|
๋๊ธ ์์ญ์ผ๋ก ์ด๋ |
C
C
|
๋ชจ๋ ์์ญ
์ด ํ์ด์ง์ URL ๋ณต์ฌ |
S
S
|
๋งจ ์๋ก ์ด๋ |
T
T
|
ํฐ์คํ ๋ฆฌ ํ ์ด๋ |
H
H
|
๋จ์ถํค ์๋ด |
Shift + /
โง + /
|
* ๋จ์ถํค๋ ํ๊ธ/์๋ฌธ ๋์๋ฌธ์๋ก ์ด์ฉ ๊ฐ๋ฅํ๋ฉฐ, ํฐ์คํ ๋ฆฌ ๊ธฐ๋ณธ ๋๋ฉ์ธ์์๋ง ๋์ํฉ๋๋ค.