December 22, 2021
๋ฌธ์ 0๋ถํฐ N๊น์ง์ ์ ์ K๊ฐ๋ฅผ ๋ํด์ ๊ทธ ํฉ์ด N์ด ๋๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ๋ง์ ์ ์์๊ฐ ๋ฐ๋ ๊ฒฝ์ฐ๋ ๋ค๋ฅธ ๊ฒฝ์ฐ๋ก ์ผ๋ค(1+2์ 2+1์ ์๋ก ๋ค๋ฅธ ๊ฒฝ์ฐ). ๋ํ ํ ๊ฐ์ ์๋ฅผ ์ฌ๋ฌ ๋ฒ ์ธ ์๋ ์๋ค. ์ ๋ ฅ ์ฒซ์งธ ์ค์ ๋ ์ ์ N(1 โค N โค 200), K(1 โค K โค 200)๊ฐ ์ฃผ์ด์ง๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ๋ต์ 1,000,โฆ
December 28, 2021
๋ฌธ์ ์ฐจ์ธ๋ ์๋์ธ ํ๋๋ ๊ฐ์๋ ๊ณ ๋ญ์ง์์ ์ ๊ธฐ๋ ๋ฐฐ์ถ๋ฅผ ์ฌ๋ฐฐํ๊ธฐ๋ก ํ์๋ค. ๋์ฝ์ ์ฐ์ง ์๊ณ ๋ฐฐ์ถ๋ฅผ ์ฌ๋ฐฐํ๋ ค๋ฉด ๋ฐฐ์ถ๋ฅผ ํด์ถฉ์ผ๋ก๋ถํฐ ๋ณดํธํ๋ ๊ฒ์ด ์ค์ํ๊ธฐ ๋๋ฌธ์, ํ๋๋ ํด์ถฉ ๋ฐฉ์ง์ ํจ๊ณผ์ ์ธ ๋ฐฐ์ถํฐ์ง๋ ์ด๋ฅผ ๊ตฌ์ ํ๊ธฐ๋ก ๊ฒฐ์ฌํ๋ค. ์ด ์ง๋ ์ด๋ ๋ฐฐ์ถ๊ทผ์ฒ์ ์์ํ๋ฉฐ ํด์ถฉ์ ์ก์ ๋จน์์ผ๋ก์จ ๋ฐฐ์ถ๋ฅผ ๋ณดํธํ๋ค. ํนํ, ์ด๋ค ๋ฐฐ์ถ์ ๋ฐฐ์ถํฐ์ง๋ ์ด๊ฐ ํ ๋ง๋ฆฌ๋ผ๋ ์ด๊ณ โฆ
December 29, 2021
๋ฌธ์ ๊ทธ๋ํ๋ฅผ DFS๋ก ํ์ํ ๊ฒฐ๊ณผ์ BFS๋ก ํ์ํ ๊ฒฐ๊ณผ๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ๋จ, ๋ฐฉ๋ฌธํ ์ ์๋ ์ ์ ์ด ์ฌ๋ฌ ๊ฐ์ธ ๊ฒฝ์ฐ์๋ ์ ์ ๋ฒํธ๊ฐ ์์ ๊ฒ์ ๋จผ์ ๋ฐฉ๋ฌธํ๊ณ , ๋ ์ด์ ๋ฐฉ๋ฌธํ ์ ์๋ ์ ์ด ์๋ ๊ฒฝ์ฐ ์ข ๋ฃํ๋ค. ์ ์ ๋ฒํธ๋ 1๋ฒ๋ถํฐ N๋ฒ๊น์ง์ด๋ค. ์ ๋ ฅ ์ฒซ์งธ ์ค์ ์ ์ ์ ๊ฐ์ N(1 โค N โค 1,000), ๊ฐ์ ์ ๊ฐ์ M(1 โค M โฆ
January 12, 2022
๋ฌธ์ ๊ทธ๋ํ์ ์ ์ ์ ์งํฉ์ ๋๋ก ๋ถํ ํ์ฌ, ๊ฐ ์งํฉ์ ์ํ ์ ์ ๋ผ๋ฆฌ๋ ์๋ก ์ธ์ ํ์ง ์๋๋ก ๋ถํ ํ ์ ์์ ๋, ๊ทธ๋ฌํ ๊ทธ๋ํ๋ฅผ ํน๋ณํ ์ด๋ถ ๊ทธ๋ํ (Bipartite Graph) ๋ผ ๋ถ๋ฅธ๋ค. ๊ทธ๋ํ๊ฐ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ก์ ๋, ์ด ๊ทธ๋ํ๊ฐ ์ด๋ถ ๊ทธ๋ํ์ธ์ง ์๋์ง ํ๋ณํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์ ๋ ฅ ์ ๋ ฅ์ ์ฌ๋ฌ ๊ฐ์ ํ ์คํธ ์ผ์ด์ค๋ก ๊ตฌ์ฑ๋์ด ์๋๋ฐ, ์ฒซ์งธโฆ
January 13, 2022
๋ฌธ์ ์ธ๋ก ๋ ์ค, ๊ฐ๋ก๋ก N๊ฐ์ ์นธ์ผ๋ก ์ด๋ฃจ์ด์ง ํ๊ฐ ์๋ค. ์ฒซ์งธ ์ค์ ๊ฐ ์นธ์๋ ์ ์ 1, 2, โฆ, N์ด ์ฐจ๋ก๋๋ก ๋ค์ด ์๊ณ ๋์งธ ์ค์ ๊ฐ ์นธ์๋ 1์ด์ N์ดํ์ธ ์ ์๊ฐ ๋ค์ด ์๋ค. ์ฒซ์งธ ์ค์์ ์ซ์๋ฅผ ์ ์ ํ ๋ฝ์ผ๋ฉด, ๊ทธ ๋ฝํ ์ ์๋ค์ด ์ด๋ฃจ๋ ์งํฉ๊ณผ, ๋ฝํ ์ ์๋ค์ ๋ฐ๋ก ๋ฐ์ ๋์งธ ์ค์ ๋ค์ด์๋ ์ ์๋ค์ด ์ด๋ฃจ๋ ์งํฉ์ด ์ผ์นํ๋ค. ์ด๋ฌํ ์กฐ๊ฑด์ ๋ง์กฑ์โฆ
January 22, 2022
๋ฌธ์ ์ด๋ฒ ๊ฐ์ํ๊ธฐ์ '๋ฌธ์ ํด๊ฒฐ' ๊ฐ์๋ฅผ ์ ์ฒญํ ํ์๋ค์ ํ ํ๋ก์ ํธ๋ฅผ ์ํํด์ผ ํ๋ค. ํ๋ก์ ํธ ํ์ ์์๋ ์ ํ์ด ์๋ค. ์ฌ์ง์ด ๋ชจ๋ ํ์๋ค์ด ๋์ผํ ํ์ ํ์์ธ ๊ฒฝ์ฐ์ ๊ฐ์ด ํ ํ๋ง ์์ ์๋ ์๋ค. ํ๋ก์ ํธ ํ์ ๊ตฌ์ฑํ๊ธฐ ์ํด, ๋ชจ๋ ํ์๋ค์ ํ๋ก์ ํธ๋ฅผ ํจ๊ปํ๊ณ ์ถ์ ํ์์ ์ ํํด์ผ ํ๋ค. (๋จ, ๋จ ํ ๋ช ๋ง ์ ํํ ์ ์๋ค.) ํผ์ ํ๊ณ ์ถ์ดํ๋โฆ
February 10, 2022
๋ฌธ์ ์ฌ๋ฌ ์ฌ์ผ๋ก ์ด๋ฃจ์ด์ง ๋๋ผ๊ฐ ์๋ค. ์ด ๋๋ผ์ ๋ํต๋ น์ ์ฌ์ ์๋ ๋ค๋ฆฌ๋ฅผ ๋ง๋ค๊ฒ ๋ค๋ ๊ณต์ฝ์ผ๋ก ์ธ๊ธฐ๋ชฐ์ด๋ฅผ ํด ๋น์ ๋ ์ ์์๋ค. ํ์ง๋ง ๋ง์ ๋ํต๋ น์ ์ทจ์ํ์, ๋ค๋ฆฌ๋ฅผ ๋๋๋ค๋ ๊ฒ์ด ์๊น๋ค๋ ์๊ฐ์ ํ๊ฒ ๋์๋ค. ๊ทธ๋์ ๊ทธ๋, ์์๋ด๋ ์์ผ๋ก ํ ์ฌ๊ณผ ๋ค๋ฅธ ์ฌ์ ์๋ ๋ค๋ฆฌ ํ๋๋ง์ ๋ง๋ค๊ธฐ๋ก ํ์๊ณ , ๊ทธ ๋ํ ๋ค๋ฆฌ๋ฅผ ๊ฐ์ฅ ์งง๊ฒ ํ์ฌ ๋์ ์๋ผ๋ ค ํ์๋ค.โฆ
February 21, 2022
๋ฌธ์ ๊ฐํธ๋ ์ฝ๋ฉ ๊ต์ก์ ํ๋ ์คํํธ์ ์คํํธ๋งํฌ์ ์ง์ํ๋ค. ์ค๋์ ๊ฐํธ์ ๋ฉด์ ๋ ์ด๋ค. ํ์ง๋ง, ๋ฆ์ ์ ์ ๊ฐํธ๋ ์คํํธ๋งํฌ๊ฐ ์๋ ๊ฑด๋ฌผ์ ๋ฆ๊ฒ ๋์ฐฉํ๊ณ ๋ง์๋ค. ์คํํธ๋งํฌ๋ ์ด F์ธต์ผ๋ก ์ด๋ฃจ์ด์ง ๊ณ ์ธต ๊ฑด๋ฌผ์ ์ฌ๋ฌด์ค์ด ์๊ณ , ์คํํธ๋งํฌ๊ฐ ์๋ ๊ณณ์ ์์น๋ G์ธต์ด๋ค. ๊ฐํธ๊ฐ ์ง๊ธ ์๋ ๊ณณ์ S์ธต์ด๊ณ , ์ด์ ์๋ฆฌ๋ฒ ์ดํฐ๋ฅผ ํ๊ณ G์ธต์ผ๋ก ์ด๋ํ๋ ค๊ณ ํ๋ค. ๋ณดํตโฆ
March 02, 2022
๋ฌธ์ ๋ฟ์๋ฟ์์ ๋ฃฐ์ ๋ค์๊ณผ ๊ฐ๋ค. ํ๋์ ์ฌ๋ฌ ๊ฐ์ง ์๊น์ ๋ฟ์๋ฅผ ๋๋๋ค. ๋ฟ์๋ ์ค๋ ฅ์ ์ํฅ์ ๋ฐ์ ์๋์ ๋ฐ๋ฅ์ด๋ ๋ค๋ฅธ ๋ฟ์๊ฐ ๋์ฌ ๋๊น์ง ์๋๋ก ๋จ์ด์ง๋ค. ๋ฟ์๋ฅผ ๋๊ณ ๋ ํ, ๊ฐ์ ์ ๋ฟ์๊ฐ 4๊ฐ ์ด์ ์ํ์ข์ฐ๋ก ์ฐ๊ฒฐ๋์ด ์์ผ๋ฉด ์ฐ๊ฒฐ๋ ๊ฐ์ ์ ๋ฟ์๋ค์ด ํ๊บผ๋ฒ์ ์์ด์ง๋ค. ์ด๋ 1์ฐ์๊ฐ ์์๋๋ค. ๋ฟ์๋ค์ด ์์ด์ง๊ณ ๋์ ์์ ๋ค๋ฅธ ๋ฟ์๋ค์ด ์๋ค๋ฉดโฆ
March 03, 2022
๋ฌธ์ ๋ฐฑ์ค์์ ์์ฅ ์ต๋ฐฑ์ค์ ์ง๋ ๋ช ๋ ๊ฐ ๊ฒ๋ฆฌ๋งจ๋๋ง์ ํตํด์ ์์ ์ ๋น์๊ฒ ์ ๋ฆฌํ๊ฒ ์ ๊ฑฐ๊ตฌ๋ฅผ ํ์ ํ๋ค. ๊ฒฌ์ ํ ๊ถ๋ ฅ์ด ์์ด์ง ์ต๋ฐฑ์ค์ ๊ถ๋ ฅ์ ๋งค์ฐ ๋ถ๋นํ๊ฒ ํ์ฌํ๊ณ , ์ฌ์ง์ด๋ ์์ ์ด๋ฆ๋ ๋ฐฑ์ค์๋ก ๋ณ๊ฒฝํ๋ค. ์ด๋ฒ ์ ๊ฑฐ์์๋ ์ต๋ํ ๊ณตํํ๊ฒ ์ ๊ฑฐ๊ตฌ๋ฅผ ํ์ ํ๋ ค๊ณ ํ๋ค. ๋ฐฑ์ค์๋ N๊ฐ์ ๊ตฌ์ญ์ผ๋ก ๋๋์ด์ ธ ์๊ณ , ๊ตฌ์ญ์ 1๋ฒ๋ถํฐ N๋ฒ๊น์ง ๋ฒํธ๊ฐ ๋งค๊ฒจ์ ธ ์๋ค. โฆ