๐ป Computer Science/- Data Structure, Algorithm147 [์๊ณ ๋ฆฌ์ฆ PS] ๋ฐฑ์ค 1476๋ฒ ๋ ์ง ๊ณ์ฐ ์๋ฐ ๋ฌธ์ ํ์ด ๋ฌธ์ ํด๋น ํฌ์คํ ์ ๋ฐฑ์ค์ 1476๋ฒ ๋ ์ง ๊ณ์ฐ ์ ์ ๊ทผ๊ณผ ํด๊ฒฐ ๋ฐฉ๋ฒ์ ์ค๋ช ํ ๊ธ ์ ๋๋ค. ์ ๋ต ์์ค ์ฝ๋๋ฅผ ํ์ธํ์๋ ค๋ฉด solve url ์์ ํ์ธ ๊ฐ๋ฅํฉ๋๋ค. ์ด ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด ์ด๋ค ๋ฐฉ์์ผ๋ก ์ ๊ทผํด์ผ ํ๋์ง๋ฅผ ๋จผ์ ์๊ฐํด๋ณด์. ๋ฌธ์ ์ ๊ทผ ์ด๋ฒ ๋ฌธ์ ๋ ์์ ํ์์ ๊ฐ์ฅ ๊ธฐ์ด์ ์ธ ๋ฌธ์ ๋ก ๋ณผ ์ ์๋ค. ์์ ํ์ ์๊ณ ๋ฆฌ์ฆ ๊ธฐ๋ฒ ์ค ๋ธ๋ฃจํธ ํฌ์ค ์ ๊ทผ์ผ๋ก ํด๊ฒฐํ ์ ์๋ค. ๋ธ๋ฃจํธ ํฌ์ค ์๊ณ ๋ฆฌ์ฆ์ ์๊ฐ ๋ฉด์์ ๊ฐ์ฅ ๋นํจ์จ์ ์ธ ์๊ณ ๋ฆฌ์ฆ์ด์ง๋ง, ๊ฐ์ฅ ํ์คํ ๋ฐฉ๋ฒ์ผ๋ก ์๋ ค์ ธ ์๋ค. ํด๊ฒฐ๋ฒ ์ด ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด์๋ E, S, M ์ด 1๋ ์ด ์ฆ๊ฐํ ๋ ๋ง๋ค 1์ฉ ์ฆ๊ฐํ๋ ํน์ฑ์ ์ด์ฉํ๋ค. ์ฐ์ ์ ๋ ฅ๋ฐ์ E, S, M๊ณผ ๋๊ฐ์ e, s, m ๋ณ์๋ฅผ ํ๋ ๋ ๋ง๋ค์ด ์ค๋ค. ์ฐ๋ฆฌ์ e, s, m์ ๊ฐ๊ฐ 1์ฉ ๊ณ์ .. 2021. 2. 14. [์๊ณ ๋ฆฌ์ฆ PS] ๋ฐฑ์ค 2805๋ฒ ๋๋ฌด ์๋ฅด๊ธฐ ์๋ฐ ๋ฌธ์ ํ์ด ๋ฌธ์ ํด๋น ํฌ์คํ ์ ๋ฐฑ์ค์ 2805๋ฒ ๋๋ฌด ์๋ฅด๊ธฐ ์ ์ ๊ทผ๊ณผ ํด๊ฒฐ ๋ฐฉ๋ฒ์ ์ค๋ช ํ ๊ธ ์ ๋๋ค. ์ ๋ต ์์ค ์ฝ๋๋ฅผ ํ์ธํ์๋ ค๋ฉด solve url ์์ ํ์ธ ๊ฐ๋ฅํฉ๋๋ค. ์ด ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด ์ด๋ค ๋ฐฉ์์ผ๋ก ์ ๊ทผํด์ผ ํ๋์ง๋ฅผ ๋จผ์ ์๊ฐํด๋ณด์. ๋ฌธ์ ์ ๊ทผ ์ด ๋ฌธ์ ๋ ์ง๋ ๋์ ์๋ฅด๊ธฐ ๋ฌธ์ ์ ๋น์ทํ ๋ฐฉ๋ฒ์ผ๋ก ํด๊ฒฐํ ์ ์๋ค. ์ฐ์ ๋ฌธ์ ๋ฅผ ์ฝ๊ณ ์ด๋ค ๊ฒ์ ์ํ๋์ง ํ์ ๋ถํฐ ํด๋ณด์. ์ฐ๋ฆฌ์๊ฒ ๋๋ฌด์ ์ N๊ณผ ๊ทธ์ ๋ฐ๋ฅธ ๋๋ฌด๋ค์ ๋์ด๊ฐ ์ฃผ์ด์ง๋ค. ๊ทธ๋ฆฌ๊ณ ์๊ทผ์ด๊ฐ ์ง์ ๊ฐ์ ธ๊ฐ์ผ ํ ๋๋ฌด์ ๋์ด๋ํ ์ฃผ์ด์ง๋ค. ๊ทธ๋ผ ์ด๋ฅผ ํ ๋ฌธ์ฅ์ผ๋ก ์ ๋ฆฌํด๋ณด์. ๋๋ฌด์ ์ N๊ณผ ๊ฐ๊ฐ์ ๋๋ฌด ๋์ด์ ์๊ทผ์ด๊ฐ ํ์ํ ๋๋ฌด์ ๋์ด M์ด ์ฃผ์ด์ง๊ณ M์ด ์ต์๊ฐ ๋๋ ์ ๋จ๊ธฐ ๋์ด๋ฅผ ๊ตฌํ๋ผ. ๊ทธ๋ผ ์ ๋จ๊ธฐ ๋์ด๋ฅผ 1 ~ ๋๋ฌด ์ต๋ ๋์ด์ธ 20์ต ๊น์ง .. 2021. 2. 13. [์๊ณ ๋ฆฌ์ฆ PS] ๋ฐฑ์ค 1654๋ฒ ๋์ ์๋ฅด๊ธฐ ์๋ฐ ๋ฌธ์ ํ์ด ๋ฌธ์ ํด๋น ํฌ์คํ ์ ๋ฐฑ์ค์ 1654๋ฒ ๋์ ์๋ฅด๊ธฐ ์ ์ ๊ทผ๊ณผ ํด๊ฒฐ ๋ฐฉ๋ฒ์ ์ค๋ช ํ ๊ธ ์ ๋๋ค. ์ ๋ต ์์ค ์ฝ๋๋ฅผ ํ์ธํ์๋ ค๋ฉด solve url ์์ ํ์ธ ๊ฐ๋ฅํฉ๋๋ค. ์ด ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด ์ด๋ค ๋ฐฉ์์ผ๋ก ์ ๊ทผํด์ผ ํ๋์ง๋ฅผ ๋จผ์ ์๊ฐํด๋ณด์. ๋ฌธ์ ์ ๊ทผ ๋ฌธ์ ์์ ์ํ๋ ๋ด์ฉ์ ํ ๋ฌธ์ฅ์ผ๋ก ๋ง ํ์๋ฉด ๋ค์๊ณผ ๊ฐ๋ค. K๊ฐ์ ๋์ ์ N๊ฐ๋ก ๋๋์ด ์๋ฅผ ๋, ๊ฐ ๋์ ์ ๊ธธ์ด๊ฐ ์ต๋๊ฐ ๋๋ ๊ธธ์ด๋ฅผ ์ถ๋ ฅํ๋ผ. ๊ทธ๋ผ ์ฐ์ , ์๋ฌด๋ฐ ์๊ฐํ์ง ๋ง๊ณ K๊ฐ์ ๋์ ์ N๊ฐ๋ก ๋๋์ด์ ์๋ฅผ ๋ ์ต๋์ ๊ธธ์ด๋ฅผ ๊ตฌํด๋ณด์. ์ด๋ ํ ์๊ณ ๋ฆฌ์ฆ์ด ์๊ฐ๋์ง ์์๋ ์ข๋ค. ์๋ ์๊ฐํ์ง ๋ง๊ณ ํ ๋ฒ ์ง๋ณด์. public static void main(String[] args) { int k = 4; int n = 11; int[] arr = {.. 2021. 2. 13. [์๊ณ ๋ฆฌ์ฆ PS] ๋ฐฑ์ค 2178๋ฒ ๋ฏธ๋ก ํ์ ์๋ฐ ๋ฌธ์ ํ์ด ๋ฌธ์ ํด๋น ํฌ์คํ ์ ๋ฐฑ์ค์ 2178๋ฒ ๋ฏธ๋ก ํ์ ์ ์ ๊ทผ๊ณผ ํด๊ฒฐ ๋ฐฉ๋ฒ์ ์ค๋ช ํ ๊ธ ์ ๋๋ค. ์ ๋ต ์์ค ์ฝ๋๋ฅผ ํ์ธํ์๋ ค๋ฉด solve url ์์ ํ์ธ ๊ฐ๋ฅํฉ๋๋ค. ์ด ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด ์ด๋ค ๋ฐฉ์์ผ๋ก ์ ๊ทผํด์ผ ํ๋์ง๋ฅผ ๋จผ์ ์๊ฐํด๋ณด์. ๋ฌธ์ ์ ๊ทผ ๋ฌธ์ ๋ฅผ ์ฝ์ผ๋ฉฐ ๋ฐ๋ก ํ์ ํด์ผ ํ๋ ๊ฒ์ ์ต์์๋ผ๋ ํค์๋์ด๋ค. ํด๋น ๋ฌธ์ ๋ Dfs์ Bfs ๋ชจ๋ ํ ์ ์๋ ๋ฌธ์ ์ด๋ค. ํ์ง๋ง ์ฐ๋ฆฌ๋ BFS๋ฅผ ์ฌ์ฉํ๋ค. ์๋ฅผ ๋ค์ด์ ๋ค์๊ณผ ๊ฐ์ ๊ด๊ณ๊ฐ ์๋ค๊ณ ๊ฐ์ ํด๋ณด์. ์ฌ๊ธฐ์ DFS๋ฅผ ์ด์ฉํ๋๋ฐ, ์ด์ด ๋์๊ฒ DFS์์ ์ฒ์์ผ๋ก ์ ํํ ๋ ธ๋๊ฐ 6์ด๋ผ๊ณ ํด๋ณด์. ๊ทธ๋ผ ์ค์ ๋ก ์ฐพ๋ ๋ ธ๋๋ ๋ฐ๋ก ํ์นธ ์์ ์์ง๋ง, DFS๋ฅผ ์ฌ์ฉํ๋ค๋ฉด 6์ ๋ ๊น์ง ๋ค์ด๊ฐ๊ฒ ๋๋ค. ๊ทธ๋์ ์ด๋ฐ ์ต๋จ ๊ฑฐ๋ฆฌ, ๊ฒฝ๋ก๋ฌธ์ ๋ BFS๋ฅผ ์ด์ฉํด์ ํ์ด์ผ ํ๋ค.. 2021. 2. 11. [์๊ณ ๋ฆฌ์ฆ PS] ๋ฐฑ์ค 4963๋ฒ ์ฌ์ ๊ฐ์ ์๋ฐ ๋ฌธ์ ํ์ด ๋ฌธ์ ํด๋น ํฌ์คํ ์ ๋ฐฑ์ค์ 4963๋ฒ ์ฌ์ ๊ฐ์ ์ ์ ๊ทผ๊ณผ ํด๊ฒฐ ๋ฐฉ๋ฒ์ ์ค๋ช ํ ๊ธ ์ ๋๋ค. ์ ๋ต ์์ค ์ฝ๋๋ฅผ ํ์ธํ์๋ ค๋ฉด solve url ์์ ํ์ธ ๊ฐ๋ฅํฉ๋๋ค. 4963๋ฒ: ์ฌ์ ๊ฐ์ ์ ๋ ฅ์ ์ฌ๋ฌ ๊ฐ์ ํ ์คํธ ์ผ์ด์ค๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. ๊ฐ ํ ์คํธ ์ผ์ด์ค์ ์ฒซ์งธ ์ค์๋ ์ง๋์ ๋๋น w์ ๋์ด h๊ฐ ์ฃผ์ด์ง๋ค. w์ h๋ 50๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ ์ ์์ด๋ค. ๋์งธ ์ค๋ถํฐ h๊ฐ ์ค์๋ ์ง๋ www.acmicpc.net ์ด ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด ์ด๋ค ๋ฐฉ์์ผ๋ก ์ ๊ทผํด์ผ ํ๋์ง๋ฅผ ๋จผ์ ์๊ฐํด๋ณด์. ๋ฌธ์ ์ ๊ทผ ์ด ๋ฌธ์ ๋ ์ ํ์ ์ธ Connected Component ๋ฌธ์ ์ด๋ค. ๋ค๋ฅธ ๋ง๋ก๋ ์ฐ๊ฒฐ ์์ ์ฐพ๊ธฐ๋ผ๊ณ ํ๋๋ฐ, ํด๋น ๋ฌธ์ ๋ณด๋ค ์กฐ๊ธ ์ฌ์ด ๋ฒ์ ์ด ๋ฐฑ์ค์ 11724๋ฒ ์ฐ๊ฒฐ ์์์ ๊ฐ์ ๋ฌธ์ ์ด๋ค. ์ฐ๊ฒฐ ์์์ ๊ฐ์ ๋ฌธ์ .. 2021. 2. 10. [์๊ณ ๋ฆฌ์ฆ PS] ๋ฐฑ์ค 2667๋ฒ ๋จ์ง๋ฒํธ๋ถ์ด๊ธฐ ์๋ฐ ๋ฌธ์ ํ์ด ๋ฌธ์ ํด๋น ํฌ์คํ ์ ๋ฐฑ์ค์ 2667๋ฒ ๋จ์ง๋ฒํธ๋ถ์ด๊ธฐ ์ ์ ๊ทผ๊ณผ ํด๊ฒฐ ๋ฐฉ๋ฒ์ ์ค๋ช ํ ๊ธ ์ ๋๋ค. ์ ๋ต ์์ค ์ฝ๋๋ฅผ ํ์ธํ์๋ ค๋ฉด solve url ์์ ํ์ธ ๊ฐ๋ฅํฉ๋๋ค. ์ด ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด ์ด๋ค ๋ฐฉ์์ผ๋ก ์ ๊ทผํด์ผ ํ๋์ง๋ฅผ ๋จผ์ ์๊ฐํด๋ณด์. ๋ฌธ์ ์ ๊ทผ ์ด ๋ฌธ์ ๋ ์ ํ์ ์ธ Connected Component ๋ฌธ์ ์ด๋ค. ๋ค๋ฅธ ๋ง๋ก๋ ์ฐ๊ฒฐ ์์ ์ฐพ๊ธฐ๋ผ๊ณ ํ๋๋ฐ, ํด๋น ๋ฌธ์ ๋ณด๋ค ์กฐ๊ธ ์ฌ์ด ๋ฒ์ ์ด ๋ฐฑ์ค์ 11724๋ฒ ์ฐ๊ฒฐ ์์์ ๊ฐ์ ๋ฌธ์ ์ด๋ค. ์ฐ๊ฒฐ ์์์ ๊ฐ์ ๋ฌธ์ ํ์ด์์ ํด๋น ๋ฌธ์ ์ ์ ๊ทผ๊ณผ ํด๊ฒฐ์ ๋ณผ ์ ์์ผ๋ ์ฐธ๊ณ ํ๋ฉด ์ข์ ๋ฏ ํ๋ค. ํ์ง๋ง ์ง๋ ์ฐ๊ฒฐ ์์์ ๊ฐ์ ๋ฌธ์ ํ์ด์ ๋ค๋ฅธ ์ ์ด๋ผ๊ณ ํ๋ค๋ฉด, ์ธ์ ๋ฆฌ์คํธ๊ฐ ์๋๋ผ ์ด์ฐจ์ ํ๋ ฌ์ด ๊ทธ๋ํ๊ฐ ๋๋ค๋ ๊ฒ์ด๋ค. ์ธ์ ๋ฆฌ์คํธ๋ ํ๋์ ๋ ธ๋๊ฐ ๋ช ๊ฐ์ ๋ ธ๋๋ฅผ ๊ฐ.. 2021. 2. 10. ์ด์ 1 ยทยทยท 6 7 8 9 10 11 12 ยทยทยท 25 ๋ค์