์๋
ํ์ธ์! ์ค๋์ ๋ฐฑ์ค ์จ๋ผ์ธ ์ ์ง์ ๋ฌธ์ ๋ฒํธ 11660๋ฒ์ ํ์ด๋ณด๊ฒ ์ต๋๋ค. ์ด ๋ฌธ์ ๋ ์ฃผ์ด์ง 2์ฐจ์ ๋ฐฐ์ด์์ ์ฌ๋ฌ ์ฟผ๋ฆฌ์ ๋ํ ๋ถ๋ถํฉ์ ๊ตฌํ๋ ๋ฌธ์ ์
๋๋ค. ์ขํ (x1, y1)๋ถํฐ (x2, y2)๊น์ง์ ํฉ์ ๋น ๋ฅด๊ฒ ๊ณ์ฐํ ์ ์๋๋ก ๋์ ํฉ ๋ฐฐ์ด์ ์ฌ์ฉํ์ฌ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํด๋ณด๊ฒ ์ต๋๋ค. 1. ๋ฌธ์ ์ค๋ช
์ฃผ์ด์ง 2์ฐจ์ ๋ฐฐ์ด์์ ์ฌ๋ฌ ์ฟผ๋ฆฌ์ ๋ํ ๋ถ๋ถํฉ์ ๊ตฌํ๋ ๋ฌธ์ ์
๋๋ค. ์ขํ (x1, y1)๋ถํฐ (x2, y2)๊น์ง์ ํฉ์ ๋น ๋ฅด๊ฒ ๊ณ์ฐํ ์ ์๋๋ก ๋์ ํฉ ๋ฐฐ์ด์ ์ฌ์ฉํ์ฌ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํฉ๋๋ค. 2. ์ ๊ทผ๋ฒ 1. ์
๋ ฅ๋ฐ๊ธฐ: ๋ฐฐ์ด์ ํฌ๊ธฐ(N)์ ์ฟผ๋ฆฌ์ ๊ฐ์(M)๋ฅผ ์
๋ ฅ๋ฐ์ต๋๋ค. 2. ๊ทธ๋ํ ์
๋ ฅ๋ฐ๊ธฐ: N x N ํฌ๊ธฐ์ 2์ฐจ์ ๋ฐฐ์ด์ ์
๋ ฅ๋ฐ์ต๋๋ค. 3. ๋์ ํฉ ๋ฐฐ์ด ์ด๊ธฐํ: ๋์ ํฉ ๋ฐฐ์ด(prefix sum ๋ฐฐ์ด)์ ์ด..
๐ ์๊ณ ๋ฆฌ์ฆ
์๋
ํ์ธ์! ์ค๋์ ๋ฐฑ์ค ์จ๋ผ์ธ ์ ์ง์ ๋ฌธ์ ๋ฒํธ 2304๋ฒ์ ํ์ด๋ณด๊ฒ ์ต๋๋ค. ์ด ๋ฌธ์ ๋ ์ฃผ์ด์ง ๊ธฐ๋ฅ๋ค์ ์์น์ ๋์ด๋ฅผ ์ด์ฉํ์ฌ ์ฐฝ๊ณ ๋ค๊ฐํ์ ๋ฉด์ ์ ๊ตฌํ๋ ๋ฌธ์ ์
๋๋ค. ๋ฌธ์ URL: https://www.acmicpc.net/problem/2304 1. ๋ฌธ์ ์ค๋ช
์ฃผ์ด์ง ๊ธฐ๋ฅ๋ค์ ์์น์ ๋์ด๋ฅผ ์ด์ฉํ์ฌ ์ฐฝ๊ณ ๋ค๊ฐํ์ ๋ฉด์ ์ ๊ตฌํ๋ ๋ฌธ์ ์
๋๋ค. ๊ธฐ๋ฅ์ ์์น์ ๋์ด๋ฅผ ๊ณ ๋ คํ์ฌ ์ ์ฒด ๋ค๊ฐํ์ ๋ฉด์ ์ ๊ณ์ฐํฉ๋๋ค. 2. ์ ๊ทผ๋ฒ 1. ๊ธฐ๋ฅ์ ๊ฐ์๋ฅผ ์
๋ ฅ๋ฐ์ต๋๋ค. 2. ๊ฐ ๊ธฐ๋ฅ์ ์์น์ ๋์ด๋ฅผ ์
๋ ฅ๋ฐ์ ๋ฆฌ์คํธ์ ์ ์ฅํฉ๋๋ค. 3. ๊ฐ์ฅ ๋์ ๊ธฐ๋ฅ์ ์์น์ ๋์ด๋ฅผ ์ฐพ์ต๋๋ค. 4. ์ผ์ชฝ์์ ์ค๋ฅธ์ชฝ์ผ๋ก ์ด๋ํ๋ฉฐ ๋ฉด์ ์ ๊ณ์ฐํฉ๋๋ค. 5. ์ค๋ฅธ์ชฝ์์ ์ผ์ชฝ์ผ๋ก ์ด๋ํ๋ฉฐ ๋ฉด์ ์ ๊ณ์ฐํฉ๋๋ค. 6. ๋ ๋ถ๋ถ์ ๋ฉด์ ์ ํฉ์ฐํ์ฌ ์ต์ข
๋ฉด..
์๋
ํ์ธ์! ์ค๋์ ๋ฐฑ์ค ์จ๋ผ์ธ ์ ์ง์ ๋ฌธ์ ๋ฒํธ 1912๋ฒ์ ํ์ด๋ณด๊ฒ ์ต๋๋ค. ์ด ๋ฌธ์ ๋ ์ฃผ์ด์ง ์์ด์์ ์ฐ์๋ ๋ถ๋ถ ์์ด์ ํฉ์ด ์ต๋๊ฐ ๋๋ ๊ฐ์ ์ฐพ๋ ๋ฌธ์ ์
๋๋ค. ๋ฌธ์ URL: https://www.acmicpc.net/problem/1912 1. ๋ฌธ์ ์ค๋ช
์ฃผ์ด์ง ์์ด์์ ์ฐ์๋ ๋ถ๋ถ ์์ด์ ํฉ์ด ์ต๋๊ฐ ๋๋ ๊ฐ์ ์ฐพ์์ผ ํฉ๋๋ค. ์๋ฅผ ๋ค์ด, ์ฃผ์ด์ง ์์ด์ด [2, 1, -4, 3, 4, -4, 6, 5, -5, 1]์ธ ๊ฒฝ์ฐ, ์ต๋ ํฉ์ ๊ฐ๋ ์ฐ์ ๋ถ๋ถ ์์ด์ [3, 4, -4, 6, 5]๋ก์ ๊ทธ ํฉ์ 14์
๋๋ค. 2. ์ ๊ทผ๋ฒ 1. ์์ด์ ํฌ๊ธฐ n์ ์
๋ ฅ๋ฐ์ต๋๋ค. 2. ์์ด์ ์
๋ ฅ๋ฐ์ ๋ฆฌ์คํธ๋ก ์ ์ฅํฉ๋๋ค. 3. ๋์ ์ต๋ ํฉ(prefix sum)์ ์ด์ฉํ์ฌ ํจ์จ์ ์ผ๋ก ๊ณ์ฐํฉ๋๋ค: • ๊ฐ ์์๋ฅผ ๋์ ํ๋ฉด..
์๋
ํ์ธ์! ์ค๋์ ๋ฐฑ์ค ์จ๋ผ์ธ ์ ์ง์ ๋ฌธ์ ๋ฒํธ 2559๋ฒ์ ํ์ด๋ณด๊ฒ ์ต๋๋ค. ์ด ๋ฌธ์ ๋ ์ฃผ์ด์ง ์จ๋ ๋ฆฌ์คํธ์์ ์ฐ์๋ K์ผ ๋์์ ์จ๋์ ํฉ์ด ์ต๋๊ฐ ๋๋ ๊ฐ์ ์ฐพ๋ ๋ฌธ์ ์
๋๋ค. ๋ฌธ์ URL: https://www.acmicpc.net/problem/2559 1. ๋ฌธ์ ์ค๋ช
์ฃผ์ด์ง ์จ๋ ๋ฆฌ์คํธ์์ ์ฐ์๋ K์ผ ๋์์ ์จ๋์ ํฉ์ด ์ต๋๊ฐ ๋๋ ๊ฐ์ ์ฐพ๋ ๋ฌธ์ ์
๋๋ค. ์ฃผ์ด์ง ์จ๋ ๋ฆฌ์คํธ์์ ์ฐ์๋ K์ผ ๋์์ ์จ๋์ ํฉ์ด ์ต๋๊ฐ ๋๋ ๊ฐ์ ๊ณ์ฐํด์ผ ํฉ๋๋ค. 2. ์ ๊ทผ๋ฒ 1. ๊ฐ ํ
์คํธ ์ผ์ด์ค๋ง๋ค ์จ๋ ๋ฆฌ์คํธ๊ฐ ์ฃผ์ด์ง๋๋ค. 2. ์ฐ์๋ K์ผ ๋์์ ์จ๋์ ํฉ์ ๊ณ์ฐํ์ฌ ์ต๋๊ฐ์ ์ฐพ์ต๋๋ค. 3. ๋์ ํฉ(prefix sum)์ ์ด์ฉํ์ฌ ํจ์จ์ ์ผ๋ก ๊ณ์ฐํฉ๋๋ค: • ์จ๋ ๋ฆฌ์คํธ์ ๋์ ํฉ์ ๊ณ์ฐํฉ๋๋ค. • ๋์ ํฉ์ ์ด..
1. ๋ฌธ์ ์ค๋ช
์๋
ํ์ธ์! ์ค๋์ ๋ฐฑ์ค ์จ๋ผ์ธ ์ ์ง์ ๋ฌธ์ ๋ฒํธ 7795๋ฒ์ ํ์ด๋ณด๊ฒ ์ต๋๋ค. ์ด ๋ฌธ์ ๋ ์ฃผ์ด์ง ๋ ๋ฆฌ์คํธ์์ ํน์ ์กฐ๊ฑด์ ๋ง์กฑํ๋ ์์ ๊ฐ์๋ฅผ ์ฐพ๋ ๋ฌธ์ ์
๋๋ค. ๋ฌธ์ URL: https://www.acmicpc.net/problem/7795 2. ์ ๊ทผ๋ฒ 1. ๊ฐ ํ
์คํธ ์ผ์ด์ค๋ง๋ค ๋ ๊ฐ์ ๋ฆฌ์คํธ A์ B๊ฐ ์ฃผ์ด์ง๋๋ค. 2. A์ ์์ ์ค ํ๋์ B์ ์์ ์ค ํ๋๋ฅผ ์ ํํ์ ๋, A์ ์์๊ฐ B์ ์์๋ณด๋ค ํด ๋ ํด๋น ์์ ์ธ์ด์ผ ํฉ๋๋ค. 3. ๋ฆฌ์คํธ A์ B๋ฅผ ์ ๋ ฌํฉ๋๋ค. 4. A์ ๊ฐ ์์์ ๋ํด B์ ์์๋ค๊ณผ ๋น๊ตํ์ฌ ๋ช ๊ฐ์ ์์๊ฐ ์กฐ๊ฑด์ ๋ง์กฑํ๋์ง ์นด์ดํธํฉ๋๋ค. 5. ํฌ ํฌ์ธํฐ ๊ธฐ๋ฒ์ ์ฌ์ฉํ์ฌ ํจ์จ์ ์ผ๋ก ์์ ๊ฐ์๋ฅผ ์
๋๋ค: • A ๋ฆฌ์คํธ์ B ๋ฆฌ์คํธ์ ํฌ์ธํฐ๋ฅผ ๊ฐ๊ฐ ์์์ ์ ..