๋ฐฑ์ค84 [Java] BOJ 7662 ์ด์ค ์ฐ์ ์์ ํ ๋ฌธ์ ๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/7662์ด์ค ์ฐ์ ์์ ํ(dual priority queue)๋ ์ ํ์ ์ธ ์ฐ์ ์์ ํ์ฒ๋ผ ๋ฐ์ดํฐ๋ฅผ ์ฝ์ , ์ญ์ ํ ์ ์๋ ์๋ฃ ๊ตฌ์กฐ์ด๋ค.์ ํ์ ์ธ ํ์์ ์ฐจ์ด์ ์ ๋ฐ์ดํฐ๋ฅผ ์ญ์ ํ ๋ ์ฐ์ฐ(operation) ๋ช ๋ น์ ๋ฐ๋ผ ์ฐ์ ์์๊ฐ ๊ฐ์ฅ ๋์ ๋ฐ์ดํฐ ๋๋ ๊ฐ์ฅ ๋ฎ์ ๋ฐ์ดํฐ ์ค ํ๋๋ฅผ ์ญ์ ํ๋ ์ ์ด๋ค.์ด์ค ์ฐ์ ์์ ํ๋ฅผ ์ํด์ ๋ ๊ฐ์ง ์ฐ์ฐ์ด ์ฌ์ฉ๋๋๋ฐ, ํ๋๋ ๋ฐ์ดํฐ๋ฅผ ์ฝ์ ํ๋ ์ฐ์ฐ์ด๊ณ ๋ค๋ฅธ ํ๋๋ ๋ฐ์ดํฐ๋ฅผ ์ญ์ ํ๋ ์ฐ์ฐ์ด๋ค.๋ฐ์ดํฐ๋ฅผ ์ญ์ ํ๋ ์ฐ์ฐ์ ๋ ๋ ๊ฐ์ง๋ก ๊ตฌ๋ถ๋๋๋ฐ ํ๋๋ ์ฐ์ ์์๊ฐ ๊ฐ์ฅ ๋์ ๊ฒ์ ์ญ์ ํ๊ธฐ ์ํ ๊ฒ์ด๊ณ ๋ค๋ฅธ ํ๋๋ ์ฐ์ ์์๊ฐ ๊ฐ์ฅ ๋ฎ์ ๊ฒ์ ์ญ์ ํ๊ธฐ ์ํ ๊ฒ์ด๋ค.์ ์๋ง ์ ์ฅํ๋ ์ด์ค ์ฐ์ ์์ ํ Q๊ฐ ์๋ค๊ณ .. 2024. 9. 7. [Java] BOJ 16928 ๋ฑ๊ณผ ์ฌ๋ค๋ฆฌ ๊ฒ์ ๋ฌธ์ ๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/16928๋ฑ๊ณผ ์ฌ๋ค๋ฆฌ ๊ฒ์์ ์ฆ๊ฒจ ํ๋ ํ๋ธ๋ฌ๋ฒ๋ ์ด๋ ๋ ๊ถ๊ธํ ์ ์ด ์๊ฒผ๋ค.์ฃผ์ฌ์๋ฅผ ์กฐ์ํด ๋ด๊ฐ ์ํ๋ ์๊ฐ ๋์ค๊ฒ ๋ง๋ค ์ ์๋ค๋ฉด, ์ต์ ๋ช ๋ฒ๋ง์ ๋์ฐฉ์ ์ ๋์ฐฉํ ์ ์์๊น?๊ฒ์์ ์ ์ก๋ฉด์ฒด ์ฃผ์ฌ์๋ฅผ ์ฌ์ฉํ๋ฉฐ, ์ฃผ์ฌ์์ ๊ฐ ๋ฉด์๋ 1๋ถํฐ 6๊น์ง ์๊ฐ ํ๋์ฉ ์ ํ์๋ค. ๊ฒ์์ ํฌ๊ธฐ๊ฐ 10×10์ด๊ณ , ์ด 100๊ฐ์ ์นธ์ผ๋ก ๋๋์ด์ ธ ์๋ ๋ณด๋ํ์์ ์งํ๋๋ค. ๋ณด๋ํ์๋ 1๋ถํฐ 100๊น์ง ์๊ฐ ํ๋์ฉ ์์๋๋ก ์ ํ์ ธ ์๋ค. ํ๋ ์ด์ด๋ ์ฃผ์ฌ์๋ฅผ ๊ตด๋ ค ๋์จ ์๋งํผ ์ด๋ํด์ผ ํ๋ค. ์๋ฅผ ๋ค์ด, ํ๋ ์ด์ด๊ฐ i๋ฒ ์นธ์ ์๊ณ , ์ฃผ์ฌ์๋ฅผ ๊ตด๋ ค ๋์จ ์๊ฐ 4๋ผ๋ฉด, i+4๋ฒ ์นธ์ผ๋ก ์ด๋ํด์ผ ํ๋ค. ๋ง์ฝ ์ฃผ์ฌ์๋ฅผ ๊ตด๋ฆฐ ๊ฒฐ๊ณผ๊ฐ 100๋ฒ ์นธ์ ๋์ด๊ฐ๋ค๋ฉด .. 2024. 9. 7. [Java] BOJ 10026 ์ ๋ก์์ฝ ๋ฌธ์ ๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/11723์ ๋ก์์ฝ์ ๋นจ๊ฐ์๊ณผ ์ด๋ก์์ ์ฐจ์ด๋ฅผ ๊ฑฐ์ ๋๋ผ์ง ๋ชปํ๋ค. ๋ฐ๋ผ์, ์ ๋ก์์ฝ์ธ ์ฌ๋์ด ๋ณด๋ ๊ทธ๋ฆผ์ ์๋ ์ฌ๋์ด ๋ณด๋ ๊ทธ๋ฆผ๊ณผ๋ ์ข ๋ค๋ฅผ ์ ์๋ค.ํฌ๊ธฐ๊ฐ N×N์ธ ๊ทธ๋ฆฌ๋์ ๊ฐ ์นธ์ R(๋นจ๊ฐ), G(์ด๋ก), B(ํ๋) ์ค ํ๋๋ฅผ ์์น ํ ๊ทธ๋ฆผ์ด ์๋ค.๊ทธ๋ฆผ์ ๋ช ๊ฐ์ ๊ตฌ์ญ์ผ๋ก ๋๋์ด์ ธ ์๋๋ฐ, ๊ตฌ์ญ์ ๊ฐ์ ์์ผ๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. ๋, ๊ฐ์ ์์์ด ์ํ์ข์ฐ๋ก ์ธ์ ํด ์๋ ๊ฒฝ์ฐ์ ๋ ๊ธ์๋ ๊ฐ์ ๊ตฌ์ญ์ ์ํ๋ค. (์์์ ์ฐจ์ด๋ฅผ ๊ฑฐ์ ๋๋ผ์ง ๋ชปํ๋ ๊ฒฝ์ฐ๋ ๊ฐ์ ์์์ด๋ผ ํ๋ค)์๋ฅผ ๋ค์ด, ๊ทธ๋ฆผ์ด ์๋์ ๊ฐ์ ๊ฒฝ์ฐ์RRRBBGGBBBBBBRRBBRRRRRRRRโ์ ๋ก์์ฝ์ด ์๋ ์ฌ๋์ด ๋ดค์ ๋ ๊ตฌ์ญ์ ์๋ ์ด 4๊ฐ์ด๋ค. (๋นจ๊ฐ 2, ํ๋ 1, .. 2024. 9. 3. [Java] BOJ 7576 ํ ๋งํ ๋ฌธ์ ๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/7576์ฒ ์์ ํ ๋งํ ๋์ฅ์์๋ ํ ๋งํ ๋ฅผ ๋ณด๊ดํ๋ ํฐ ์ฐฝ๊ณ ๋ฅผ ๊ฐ์ง๊ณ ์๋ค. ํ ๋งํ ๋ ์๋์ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ด ๊ฒฉ์ ๋ชจ์ ์์์ ์นธ์ ํ๋์ฉ ๋ฃ์ด์ ์ฐฝ๊ณ ์ ๋ณด๊ดํ๋ค.์ฐฝ๊ณ ์ ๋ณด๊ด๋๋ ํ ๋งํ ๋ค ์ค์๋ ์ ์ต์ ๊ฒ๋ ์์ง๋ง, ์์ง ์ต์ง ์์ ํ ๋งํ ๋ค๋ ์์ ์ ์๋ค.๋ณด๊ด ํ ํ๋ฃจ๊ฐ ์ง๋๋ฉด, ์ต์ ํ ๋งํ ๋ค์ ์ธ์ ํ ๊ณณ์ ์๋ ์ต์ง ์์ ํ ๋งํ ๋ค์ ์ต์ ํ ๋งํ ์ ์ํฅ์ ๋ฐ์ ์ต๊ฒ ๋๋ค.ํ๋์ ํ ๋งํ ์ ์ธ์ ํ ๊ณณ์ ์ผ์ชฝ, ์ค๋ฅธ์ชฝ, ์, ๋ค ๋ค ๋ฐฉํฅ์ ์๋ ํ ๋งํ ๋ฅผ ์๋ฏธํ๋ค. ๋๊ฐ์ ๋ฐฉํฅ์ ์๋ ํ ๋งํ ๋ค์๊ฒ๋ ์ํฅ์ ์ฃผ์ง ๋ชปํ๋ฉฐ, ํ ๋งํ ๊ฐ ํผ์ ์ ์ ๋ก ์ต๋ ๊ฒฝ์ฐ๋ ์๋ค๊ณ ๊ฐ์ ํ๋ค.์ฒ ์๋ ์ฐฝ๊ณ ์ ๋ณด๊ด๋ ํ ๋งํ ๋ค์ด ๋ฉฐ์น ์ด ์ง๋๋ฉด ๋ค ์ต๊ฒ ๋๋์ง, ๊ทธ ์ต์.. 2024. 9. 2. [Java] BOJ 7569 ํ ๋งํ ๋ฌธ์ ๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/7569์ฒ ์์ ํ ๋งํ ๋์ฅ์์๋ ํ ๋งํ ๋ฅผ ๋ณด๊ดํ๋ ํฐ ์ฐฝ๊ณ ๋ฅผ ๊ฐ์ง๊ณ ์๋ค. ํ ๋งํ ๋ ์๋์ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ด ๊ฒฉ์๋ชจ์ ์์์ ์นธ์ ํ๋์ฉ ๋ฃ์ ๋ค์, ์์๋ค์ ์์ง์ผ๋ก ์์ ์ฌ๋ ค์ ์ฐฝ๊ณ ์ ๋ณด๊ดํ๋ค.์ฐฝ๊ณ ์ ๋ณด๊ด๋๋ ํ ๋งํ ๋ค ์ค์๋ ์ ์ต์ ๊ฒ๋ ์์ง๋ง, ์์ง ์ต์ง ์์ ํ ๋งํ ๋ค๋ ์์ ์ ์๋ค.๋ณด๊ด ํ ํ๋ฃจ๊ฐ ์ง๋๋ฉด, ์ต์ ํ ๋งํ ๋ค์ ์ธ์ ํ ๊ณณ์ ์๋ ์ต์ง ์์ ํ ๋งํ ๋ค์ ์ต์ ํ ๋งํ ์ ์ํฅ์ ๋ฐ์ ์ต๊ฒ ๋๋ค.ํ๋์ ํ ๋งํ ์ ์ธ์ ํ ๊ณณ์ ์, ์๋, ์ผ์ชฝ, ์ค๋ฅธ์ชฝ, ์, ๋ค ์ฌ์ฏ ๋ฐฉํฅ์ ์๋ ํ ๋งํ ๋ฅผ ์๋ฏธํ๋ค. ๋๊ฐ์ ๋ฐฉํฅ์ ์๋ ํ ๋งํ ๋ค์๊ฒ๋ ์ํฅ์ ์ฃผ์ง ๋ชปํ๋ฉฐ, ํ ๋งํ ๊ฐ ํผ์ ์ ์ ๋ก ์ต๋ ๊ฒฝ์ฐ๋ ์๋ค๊ณ ๊ฐ์ ํ๋ค.์ฒ ์๋ ์ฐฝ๊ณ ์ ๋ณด๊ด๋ ํ .. 2024. 9. 1. [Java] BOJ 5430 AC ๋ฌธ์ ๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/5430์ ์์ด๋ ์ฃผ๋ง์ ํ ์ผ์ด ์์ด์ ์๋ก์ด ์ธ์ด AC๋ฅผ ๋ง๋ค์๋ค. AC๋ ์ ์ ๋ฐฐ์ด์ ์ฐ์ฐ์ ํ๊ธฐ ์ํด ๋ง๋ ์ธ์ด์ด๋ค.์ด ์ธ์ด์๋ ๋ ๊ฐ์ง ํจ์ R(๋ค์ง๊ธฐ)๊ณผ D(๋ฒ๋ฆฌ๊ธฐ)๊ฐ ์๋ค.ํจ์๋ ์กฐํฉํด์ ํ ๋ฒ์ ์ฌ์ฉํ ์ ์๋ค.์๋ฅผ ๋ค์ด, "AB"๋ A๋ฅผ ์ํํ ๋ค์์ ๋ฐ๋ก ์ด์ด์ B๋ฅผ ์ํํ๋ ํจ์์ด๋ค. ์๋ฅผ ๋ค์ด, "RDD"๋ ๋ฐฐ์ด์ ๋ค์ง์ ๋ค์ ์ฒ์ ๋ ์๋ฅผ ๋ฒ๋ฆฌ๋ ํจ์์ด๋ค.๋ฐฐ์ด์ ์ด๊ธฐ๊ฐ๊ณผ ์ํํ ํจ์๊ฐ ์ฃผ์ด์ก์ ๋, ์ต์ข ๊ฒฐ๊ณผ๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.ํจ์ R์ ๋ฐฐ์ด์ ์๋ ์์ ์์๋ฅผ ๋ค์ง๋ ํจ์์ด๊ณ , D๋ ์ฒซ ๋ฒ์งธ ์๋ฅผ ๋ฒ๋ฆฌ๋ ํจ์์ด๋ค. ๋ฐฐ์ด์ด ๋น์ด์๋๋ฐ D๋ฅผ ์ฌ์ฉํ ๊ฒฝ์ฐ์๋ ์๋ฌ๊ฐ ๋ฐ์ํ๋ค.์ฒซ์งธ ์ค์ ํ ์คํธ ์ผ์ด์ค์ .. 2024. 8. 31. ์ด์ 1 2 3 4 ยทยทยท 14 ๋ค์