greedy(4)
-
[BOJ] 17615 - ๋ณผ ๋ชจ์ผ๊ธฐ
๐ฌ ๋ฌธ์ ์ค๋ช ๋นจ๊ฐ์(`R`)๊ณผ ํ๋์(`B`)์ผ๋ก ์ด๋ฃจ์ด์ง ๋ณผ์ด ์ผ๋ ฌ๋ก ๋์ด๋์ด ์๋ค. ๋ณผ์ ํ ๋ฒ์ ์ฐ์๋ ๊ฐ์ ์๊น์ ๋ณผ๋ง ์์ง์ผ ์ ์์ผ๋ฉฐ ์์ง์ธ ๋ณผ์ ํ์ชฝ ๋์ผ๋ก๋ง ์ด๋ ๊ฐ๋ฅํ๋ค.๋ชฉํ๋ ๋ณผ์ ๋ชจ๋ ํ์ชฝ ๋(์ผ์ชฝ ๋๋ ์ค๋ฅธ์ชฝ)์ ๋์ผํ ์์ผ๋ก ๋ชจ์ผ๋ ๊ฒ์ด๋ค. ์ด๋ ์์ง์ฌ์ผ ํ๋ ์ต์ ๋ณผ์ ๊ฐ์๋ฅผ ๊ตฌํ๋ผ. ๐ ์ฃผ์ ์ฌํญํ ๋ฒ ์์ง์ผ ๋ ์ฐ์๋ ๋์ผํ ์์ ๋ณผ๋ง ์์ง์ผ ์ ์๋ค.๋ฐ๋ํธ์ ์ด๋ฏธ ๋ชฐ๋ ค ์๋ ๊ฐ์ ์ ๋ณผ์ ์์ง์ผ ํ์๊ฐ ์๋ค.`R`์ ์ผ์ชฝ ๋๋ ์ค๋ฅธ์ชฝ์ผ๋ก ํน์ `B`๋ฅผ ์ผ์ชฝ ๋๋ ์ค๋ฅธ์ชฝ์ผ๋ก ์ด 4๊ฐ์ง ๊ฒฝ์ฐ๋ฅผ ๋ชจ๋ ๊ณ ๋ คํด์ผ ํ๋ค. ๐ ๋ฌธ์ ํ์ด์์(`R` ๋๋ `B`) ํ๋๋ฅผ ์ ํ๋ค.ํด๋น ์์์ ์ผ์ชฝ ๋์ผ๋ก ๋ชจ์ผ๋ ๊ฒฝ์ฐ:๋งจ ์์ ์ฐ์๋ ํด๋น ์์์ ๋ณผ์ ๊ฑด๋๋ฆด ํ์ ์์๊ทธ ๋ค์ ์กด์ฌํ๋ ..
2025.08.05 -
[BOJ] 12764 - ์ธ์ง๋ฐฉ์ ๊ฐ ์คํ
๐ฌ ๋ฌธ์ ์ค๋ช ๊ตฐ๋์ PC๋ฐฉ์ธ ์ธ์ง๋ฐฉ์๋ ์ฌ๋ฌ ๋์ ์ปดํจํฐ๊ฐ ์์ผ๋ฉฐ ๋ณ์ฌ๋ค์ ์ ํด์ง ์๊ฐ ๋์ ์ปดํจํฐ๋ฅผ ์ฌ์ฉํ๋ค.์คํ๋ ์ปดํจํฐ๋ฅผ ํจ์จ์ ์ผ๋ก ๊ด๋ฆฌํ๊ธฐ ์ํด ๋ค์ ๊ท์น์ ๋ฐ๋ผ ๋ณ์ฌ์๊ฒ ์ปดํจํฐ๋ฅผ ๋ฐฐ์ ํด์ผ ํ๋ค.ํ์ฌ ์ฌ์ฉ ๊ฐ๋ฅํ ์ปดํจํฐ๊ฐ ์๋ค๋ฉด ๋ฒํธ๊ฐ ๊ฐ์ฅ ์์ ์ปดํจํฐ๋ฅผ ๋ฐฐ์ ์ฌ์ฉ ๊ฐ๋ฅํ ์ปดํจํฐ๊ฐ ์๋ค๋ฉด ์๋ก์ด ์ปดํจํฐ๋ฅผ ์ถ๊ฐํด์ ๋ฐฐ์ ๋ชจ๋ ๋ณ์ฌ์ ์์ ์๊ฐ๊ณผ ์ข ๋ฃ ์๊ฐ์ด ์ฃผ์ด์ก์ ๋ ์คํ๊ฐ ์ฌ์ฉํ๋ ์ปดํจํฐ์ ์์ ๊ฐ ์ปดํจํฐ๊ฐ ์ฌ์ฉ๋ ํ์๋ฅผ ์ถ๋ ฅํ๋ผ. ๐ ์ฃผ์ ์ฌํญ์ข ๋ฃ๋ ์ปดํจํฐ๋ ๋ค์ ์ฌ์ฉํ ์ ์์ด์ผ ํจํญ์ ๋ฒํธ๊ฐ ๊ฐ์ฅ ์์ ์ปดํจํฐ๋ฅผ ์ฐ์ ๋ฐฐ์ ์ข ๋ฃ ์๊ฐ๊ณผ ์์ ์๊ฐ์ด ๊ฒน์น์ง ์์ผ๋ฉด ์ฌ์ฌ์ฉ ๊ฐ๋ฅ (์ข ๋ฃ์๊ฐ โค ์์์๊ฐ)์ถ๋ ฅ ์ ์ปดํจํฐ ๋ฒํธ ์ค๋ฆ์ฐจ์์ผ๋ก ์ฌ์ฉ ํ์๋ฅผ ์ถ๋ ฅํด์ผ ํจ ๐ ๋ฌธ์ ํ์ด ๋ ๊ฐ์ Priorit..
2025.07.31 -
[BOJ] 1931 - ํ์์ค ๋ฐฐ์
๐ฌ ๋ฌธ์ ์ค๋ช ํ ๊ฐ์ ํ์์ค์ด ์๊ณ `N`๊ฐ์ ํ์๊ฐ ์ฃผ์ด์ง ๋ ํ์๋ค์ด ๊ฒน์น์ง ์๊ฒ ํ๋ฉด์ ๊ฐ์ฅ ๋ง์ ํ์๋ฅผ ์งํํ๋ ค ํ๋ค.๊ฐ ํ์๋ ์์ ์๊ฐ๊ณผ ๋๋๋ ์๊ฐ์ด ์ฃผ์ด์ง๋ค.ํ ํ์๊ฐ ๋๋๋ ๊ฒ๊ณผ ๋์์ ๋ค๋ฅธ ํ์๋ฅผ ์์ํ ์ ์๋ค.ํ์์ ์ `N` (1 โค `N` โค 100,000) ๐ ์ฃผ์ ์ฌํญํ์ ๋๋๋ ์๊ฐ ๊ธฐ์ค์ผ๋ก ์ค๋ฆ์ฐจ์ ์ ๋ ฌํด์ผ ํ๋ค.๋จ ๋๋๋ ์๊ฐ์ด ๊ฐ์ ๊ฒฝ์ฐ ์์ ์๊ฐ์ด ๋น ๋ฅธ ์์ผ๋ก ์ ๋ ฌํด์ผ ํ๋ค.ํ์ ์๊ฐ์ ๊ธฐ์ค์ผ๋ก ์ ๋ ฌํ๋ฉด ์ ๋๋ค! ๐ ๋ฌธ์ ํ์ดํ์ ์ ๋ณด๋ฅผ `(์์์๊ฐ, ๋์๊ฐ)`์ผ๋ก ์ ๋ ฅ๋ฐ๋๋ค.๋๋๋ ์๊ฐ ๊ธฐ์ค ์ค๋ฆ์ฐจ์ ์ ๋ ฌ์ ํ๋ ๋๋๋ ์๊ฐ์ด ๊ฐ๋ค๋ฉด ์์ ์๊ฐ์ด ๋น ๋ฅธ ์์ผ๋ก ์ ๋ ฌ์์์๋ถํฐ ํ์๋ฅผ ์ ํํ๋ฉฐ `ํ์ฌ ํ์ ์์์๊ฐ โฅ ์ด์ ํ์ ๋์๊ฐ`์ผ ๊ฒฝ์ฐ ์ ํ์ ํํ ํ์ ์..
2025.07.28 -
[์๊ณ ๋ฆฌ์ฆ] ํ์(Greedy) ์๊ณ ๋ฆฌ์ฆ
ํ์ ์๊ณ ๋ฆฌ์ฆ(Greedy algorithm)ํ์ ์๊ณ ๋ฆฌ์ฆ์ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ๋๋ง๋ค ๊ทธ ์๊ฐ ๊ฐ์ฅ ์ต์ ์ธ(๊ฐ์ฅ ์ข์ ๋ณด์ด๋) ์ ํ์ ํ๋ ์๊ณ ๋ฆฌ์ฆ ์ ๋ต์ ์ฒด์ ์ธ ์ต์ ์ ํด๋ฅผ ๋ณด์ฅํ์ง ์์ง๋ง ๊ณ์ฐ๋์ ์ค์ด๋ฉด์ ๊ทผ์ฟ๊ฐ ๋๋ ๊ตญ์ ์ต์ ํด(local optimum)๋ฅผ ๋น ๋ฅด๊ฒ ๊ตฌํ ์ ์์ ํ์ ์๊ณ ๋ฆฌ์ฆ์ ํต์ฌ ์์นGreedy Choice Property (ํ์ ์ ํ ์์ฑ)๋งค ์๊ฐ ๊ฐ์ฅ ์ข์ ๋ณด์ด๋ ์ ํ์ด ์ ์ญ ์ต์ ํด(global optimum)๋ฅผ ๋ง๋ ๋ค.Optimal Substructure (์ต์ ๋ถ๋ถ ๊ตฌ์กฐ)์ ์ฒด ๋ฌธ์ ์ ์ต์ ํด๊ฒฐ์ฑ ์ ํ์ ๋ฌธ์ ์ ์ต์ ํด๊ฒฐ์ฑ ์ผ๋ก ๊ตฌ์ฑ๋๋ค.์์ 1: ๋์ ๋ฌธ์ (Coin Change Problem)๋ฌธ์ ์ค๋ช 4720์์ 500์, 100์, 50์, 1์ ๋์ ์ผ๋ก ๊ฐ์ฅ ์ ์ ์๋ก ์ง๋ถ..
2021.06.05