SERIES

๐Ÿ‘ฉโ€๐Ÿ’ป BOJ

25 PostsยทLast updated on May 28, 2022

๐Ÿ‘ฉโ€๐Ÿ’ป 2225. ํ•ฉ๋ถ„ํ•ด

December 22, 2021

๋ฌธ์ œ 0๋ถ€ํ„ฐ N๊นŒ์ง€์˜ ์ •์ˆ˜ K๊ฐœ๋ฅผ ๋”ํ•ด์„œ ๊ทธ ํ•ฉ์ด N์ด ๋˜๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ๋ง์…ˆ์˜ ์ˆœ์„œ๊ฐ€ ๋ฐ”๋€ ๊ฒฝ์šฐ๋Š” ๋‹ค๋ฅธ ๊ฒฝ์šฐ๋กœ ์„ผ๋‹ค(1+2์™€ 2+1์€ ์„œ๋กœ ๋‹ค๋ฅธ ๊ฒฝ์šฐ). ๋˜ํ•œ ํ•œ ๊ฐœ์˜ ์ˆ˜๋ฅผ ์—ฌ๋Ÿฌ ๋ฒˆ ์“ธ ์ˆ˜๋„ ์žˆ๋‹ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ๋‘ ์ •์ˆ˜ N(1 โ‰ค N โ‰ค 200), K(1 โ‰ค K โ‰ค 200)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— ๋‹ต์„ 1,000,โ€ฆ


๐Ÿ‘ฉโ€๐Ÿ’ป 1012. ์œ ๊ธฐ๋† ๋ฐฐ์ถ”

December 28, 2021

๋ฌธ์ œ ์ฐจ์„ธ๋Œ€ ์˜๋†์ธ ํ•œ๋‚˜๋Š” ๊ฐ•์›๋„ ๊ณ ๋žญ์ง€์—์„œ ์œ ๊ธฐ๋† ๋ฐฐ์ถ”๋ฅผ ์žฌ๋ฐฐํ•˜๊ธฐ๋กœ ํ•˜์˜€๋‹ค. ๋†์•ฝ์„ ์“ฐ์ง€ ์•Š๊ณ  ๋ฐฐ์ถ”๋ฅผ ์žฌ๋ฐฐํ•˜๋ ค๋ฉด ๋ฐฐ์ถ”๋ฅผ ํ•ด์ถฉ์œผ๋กœ๋ถ€ํ„ฐ ๋ณดํ˜ธํ•˜๋Š” ๊ฒƒ์ด ์ค‘์š”ํ•˜๊ธฐ ๋•Œ๋ฌธ์—, ํ•œ๋‚˜๋Š” ํ•ด์ถฉ ๋ฐฉ์ง€์— ํšจ๊ณผ์ ์ธ ๋ฐฐ์ถ”ํฐ์ง€๋ ์ด๋ฅผ ๊ตฌ์ž…ํ•˜๊ธฐ๋กœ ๊ฒฐ์‹ฌํ•œ๋‹ค. ์ด ์ง€๋ ์ด๋Š” ๋ฐฐ์ถ”๊ทผ์ฒ˜์— ์„œ์‹ํ•˜๋ฉฐ ํ•ด์ถฉ์„ ์žก์•„ ๋จน์Œ์œผ๋กœ์จ ๋ฐฐ์ถ”๋ฅผ ๋ณดํ˜ธํ•œ๋‹ค. ํŠนํžˆ, ์–ด๋–ค ๋ฐฐ์ถ”์— ๋ฐฐ์ถ”ํฐ์ง€๋ ์ด๊ฐ€ ํ•œ ๋งˆ๋ฆฌ๋ผ๋„ ์‚ด๊ณ  โ€ฆ


๐Ÿ‘ฉโ€๐Ÿ’ป 1260. DFS์™€ BFS

December 29, 2021

๋ฌธ์ œ ๊ทธ๋ž˜ํ”„๋ฅผ DFS๋กœ ํƒ์ƒ‰ํ•œ ๊ฒฐ๊ณผ์™€ BFS๋กœ ํƒ์ƒ‰ํ•œ ๊ฒฐ๊ณผ๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ๋‹จ, ๋ฐฉ๋ฌธํ•  ์ˆ˜ ์žˆ๋Š” ์ •์ ์ด ์—ฌ๋Ÿฌ ๊ฐœ์ธ ๊ฒฝ์šฐ์—๋Š” ์ •์  ๋ฒˆํ˜ธ๊ฐ€ ์ž‘์€ ๊ฒƒ์„ ๋จผ์ € ๋ฐฉ๋ฌธํ•˜๊ณ , ๋” ์ด์ƒ ๋ฐฉ๋ฌธํ•  ์ˆ˜ ์žˆ๋Š” ์ ์ด ์—†๋Š” ๊ฒฝ์šฐ ์ข…๋ฃŒํ•œ๋‹ค. ์ •์  ๋ฒˆํ˜ธ๋Š” 1๋ฒˆ๋ถ€ํ„ฐ N๋ฒˆ๊นŒ์ง€์ด๋‹ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ •์ ์˜ ๊ฐœ์ˆ˜ N(1 โ‰ค N โ‰ค 1,000), ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ M(1 โ‰ค M โ€ฆ


๐Ÿ‘ฉโ€๐Ÿ’ป 1707. ์ด๋ถ„๊ทธ๋ž˜ํ”„

January 12, 2022

๋ฌธ์ œ ๊ทธ๋ž˜ํ”„์˜ ์ •์ ์˜ ์ง‘ํ•ฉ์„ ๋‘˜๋กœ ๋ถ„ํ• ํ•˜์—ฌ, ๊ฐ ์ง‘ํ•ฉ์— ์†ํ•œ ์ •์ ๋ผ๋ฆฌ๋Š” ์„œ๋กœ ์ธ์ ‘ํ•˜์ง€ ์•Š๋„๋ก ๋ถ„ํ• ํ•  ์ˆ˜ ์žˆ์„ ๋•Œ, ๊ทธ๋Ÿฌํ•œ ๊ทธ๋ž˜ํ”„๋ฅผ ํŠน๋ณ„ํžˆ ์ด๋ถ„ ๊ทธ๋ž˜ํ”„ (Bipartite Graph) ๋ผ ๋ถ€๋ฅธ๋‹ค. ๊ทธ๋ž˜ํ”„๊ฐ€ ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ด ๊ทธ๋ž˜ํ”„๊ฐ€ ์ด๋ถ„ ๊ทธ๋ž˜ํ”„์ธ์ง€ ์•„๋‹Œ์ง€ ํŒ๋ณ„ํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ ์ž…๋ ฅ์€ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ๋Š”๋ฐ, ์ฒซ์งธโ€ฆ


๐Ÿ‘ฉโ€๐Ÿ’ป 2668. ์ˆซ์ž ๊ณ ๋ฅด๊ธฐ

January 13, 2022

๋ฌธ์ œ ์„ธ๋กœ ๋‘ ์ค„, ๊ฐ€๋กœ๋กœ N๊ฐœ์˜ ์นธ์œผ๋กœ ์ด๋ฃจ์–ด์ง„ ํ‘œ๊ฐ€ ์žˆ๋‹ค. ์ฒซ์งธ ์ค„์˜ ๊ฐ ์นธ์—๋Š” ์ •์ˆ˜ 1, 2, โ€ฆ, N์ด ์ฐจ๋ก€๋Œ€๋กœ ๋“ค์–ด ์žˆ๊ณ  ๋‘˜์งธ ์ค„์˜ ๊ฐ ์นธ์—๋Š” 1์ด์ƒ N์ดํ•˜์ธ ์ •์ˆ˜๊ฐ€ ๋“ค์–ด ์žˆ๋‹ค. ์ฒซ์งธ ์ค„์—์„œ ์ˆซ์ž๋ฅผ ์ ์ ˆํžˆ ๋ฝ‘์œผ๋ฉด, ๊ทธ ๋ฝ‘ํžŒ ์ •์ˆ˜๋“ค์ด ์ด๋ฃจ๋Š” ์ง‘ํ•ฉ๊ณผ, ๋ฝ‘ํžŒ ์ •์ˆ˜๋“ค์˜ ๋ฐ”๋กœ ๋ฐ‘์˜ ๋‘˜์งธ ์ค„์— ๋“ค์–ด์žˆ๋Š” ์ •์ˆ˜๋“ค์ด ์ด๋ฃจ๋Š” ์ง‘ํ•ฉ์ด ์ผ์น˜ํ•œ๋‹ค. ์ด๋Ÿฌํ•œ ์กฐ๊ฑด์„ ๋งŒ์กฑ์‹œโ€ฆ


๐Ÿ‘ฉโ€๐Ÿ’ป 9466. ํ…€ ํ”„๋กœ์ ํŠธ

January 22, 2022

๋ฌธ์ œ ์ด๋ฒˆ ๊ฐ€์„ํ•™๊ธฐ์— '๋ฌธ์ œ ํ•ด๊ฒฐ' ๊ฐ•์˜๋ฅผ ์‹ ์ฒญํ•œ ํ•™์ƒ๋“ค์€ ํ…€ ํ”„๋กœ์ ํŠธ๋ฅผ ์ˆ˜ํ–‰ํ•ด์•ผ ํ•œ๋‹ค. ํ”„๋กœ์ ํŠธ ํŒ€์› ์ˆ˜์—๋Š” ์ œํ•œ์ด ์—†๋‹ค. ์‹ฌ์ง€์–ด ๋ชจ๋“  ํ•™์ƒ๋“ค์ด ๋™์ผํ•œ ํŒ€์˜ ํŒ€์›์ธ ๊ฒฝ์šฐ์™€ ๊ฐ™์ด ํ•œ ํŒ€๋งŒ ์žˆ์„ ์ˆ˜๋„ ์žˆ๋‹ค. ํ”„๋กœ์ ํŠธ ํŒ€์„ ๊ตฌ์„ฑํ•˜๊ธฐ ์œ„ํ•ด, ๋ชจ๋“  ํ•™์ƒ๋“ค์€ ํ”„๋กœ์ ํŠธ๋ฅผ ํ•จ๊ป˜ํ•˜๊ณ  ์‹ถ์€ ํ•™์ƒ์„ ์„ ํƒํ•ด์•ผ ํ•œ๋‹ค. (๋‹จ, ๋‹จ ํ•œ ๋ช…๋งŒ ์„ ํƒํ•  ์ˆ˜ ์žˆ๋‹ค.) ํ˜ผ์ž ํ•˜๊ณ  ์‹ถ์–ดํ•˜๋Š”โ€ฆ


๐Ÿ‘ฉโ€๐Ÿ’ป 2146. ๋‹ค๋ฆฌ ๋งŒ๋“ค๊ธฐ

February 10, 2022

๋ฌธ์ œ ์—ฌ๋Ÿฌ ์„ฌ์œผ๋กœ ์ด๋ฃจ์–ด์ง„ ๋‚˜๋ผ๊ฐ€ ์žˆ๋‹ค. ์ด ๋‚˜๋ผ์˜ ๋Œ€ํ†ต๋ น์€ ์„ฌ์„ ์ž‡๋Š” ๋‹ค๋ฆฌ๋ฅผ ๋งŒ๋“ค๊ฒ ๋‹ค๋Š” ๊ณต์•ฝ์œผ๋กœ ์ธ๊ธฐ๋ชฐ์ด๋ฅผ ํ•ด ๋‹น์„ ๋  ์ˆ˜ ์žˆ์—ˆ๋‹ค. ํ•˜์ง€๋งŒ ๋ง‰์ƒ ๋Œ€ํ†ต๋ น์— ์ทจ์ž„ํ•˜์ž, ๋‹ค๋ฆฌ๋ฅผ ๋†“๋Š”๋‹ค๋Š” ๊ฒƒ์ด ์•„๊น๋‹ค๋Š” ์ƒ๊ฐ์„ ํ•˜๊ฒŒ ๋˜์—ˆ๋‹ค. ๊ทธ๋ž˜์„œ ๊ทธ๋Š”, ์ƒ์ƒ‰๋‚ด๋Š” ์‹์œผ๋กœ ํ•œ ์„ฌ๊ณผ ๋‹ค๋ฅธ ์„ฌ์„ ์ž‡๋Š” ๋‹ค๋ฆฌ ํ•˜๋‚˜๋งŒ์„ ๋งŒ๋“ค๊ธฐ๋กœ ํ•˜์˜€๊ณ , ๊ทธ ๋˜ํ•œ ๋‹ค๋ฆฌ๋ฅผ ๊ฐ€์žฅ ์งง๊ฒŒ ํ•˜์—ฌ ๋ˆ์„ ์•„๋ผ๋ ค ํ•˜์˜€๋‹ค.โ€ฆ


๐Ÿ‘ฉโ€๐Ÿ’ป 5014. ์Šคํƒ€ํŠธ ๋งํฌ

February 21, 2022

๋ฌธ์ œ ๊ฐ•ํ˜ธ๋Š” ์ฝ”๋”ฉ ๊ต์œก์„ ํ•˜๋Š” ์Šคํƒ€ํŠธ์—… ์Šคํƒ€ํŠธ๋งํฌ์— ์ง€์›ํ–ˆ๋‹ค. ์˜ค๋Š˜์€ ๊ฐ•ํ˜ธ์˜ ๋ฉด์ ‘๋‚ ์ด๋‹ค. ํ•˜์ง€๋งŒ, ๋Šฆ์ž ์„ ์ž” ๊ฐ•ํ˜ธ๋Š” ์Šคํƒ€ํŠธ๋งํฌ๊ฐ€ ์žˆ๋Š” ๊ฑด๋ฌผ์— ๋Šฆ๊ฒŒ ๋„์ฐฉํ•˜๊ณ  ๋ง์•˜๋‹ค. ์Šคํƒ€ํŠธ๋งํฌ๋Š” ์ด F์ธต์œผ๋กœ ์ด๋ฃจ์–ด์ง„ ๊ณ ์ธต ๊ฑด๋ฌผ์— ์‚ฌ๋ฌด์‹ค์ด ์žˆ๊ณ , ์Šคํƒ€ํŠธ๋งํฌ๊ฐ€ ์žˆ๋Š” ๊ณณ์˜ ์œ„์น˜๋Š” G์ธต์ด๋‹ค. ๊ฐ•ํ˜ธ๊ฐ€ ์ง€๊ธˆ ์žˆ๋Š” ๊ณณ์€ S์ธต์ด๊ณ , ์ด์ œ ์—˜๋ฆฌ๋ฒ ์ดํ„ฐ๋ฅผ ํƒ€๊ณ  G์ธต์œผ๋กœ ์ด๋™ํ•˜๋ ค๊ณ  ํ•œ๋‹ค. ๋ณดํ†ตโ€ฆ


๐Ÿ‘ฉโ€๐Ÿ’ป 11559. Puyo Puyo

March 02, 2022

๋ฌธ์ œ ๋ฟŒ์š”๋ฟŒ์š”์˜ ๋ฃฐ์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. ํ•„๋“œ์— ์—ฌ๋Ÿฌ ๊ฐ€์ง€ ์ƒ‰๊น”์˜ ๋ฟŒ์š”๋ฅผ ๋†“๋Š”๋‹ค. ๋ฟŒ์š”๋Š” ์ค‘๋ ฅ์˜ ์˜ํ–ฅ์„ ๋ฐ›์•„ ์•„๋ž˜์— ๋ฐ”๋‹ฅ์ด๋‚˜ ๋‹ค๋ฅธ ๋ฟŒ์š”๊ฐ€ ๋‚˜์˜ฌ ๋•Œ๊นŒ์ง€ ์•„๋ž˜๋กœ ๋–จ์–ด์ง„๋‹ค. ๋ฟŒ์š”๋ฅผ ๋†“๊ณ  ๋‚œ ํ›„, ๊ฐ™์€ ์ƒ‰ ๋ฟŒ์š”๊ฐ€ 4๊ฐœ ์ด์ƒ ์ƒํ•˜์ขŒ์šฐ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์œผ๋ฉด ์—ฐ๊ฒฐ๋œ ๊ฐ™์€ ์ƒ‰ ๋ฟŒ์š”๋“ค์ด ํ•œ๊บผ๋ฒˆ์— ์—†์–ด์ง„๋‹ค. ์ด๋•Œ 1์—ฐ์‡„๊ฐ€ ์‹œ์ž‘๋œ๋‹ค. ๋ฟŒ์š”๋“ค์ด ์—†์–ด์ง€๊ณ  ๋‚˜์„œ ์œ„์— ๋‹ค๋ฅธ ๋ฟŒ์š”๋“ค์ด ์žˆ๋‹ค๋ฉดโ€ฆ


๐Ÿ‘ฉโ€๐Ÿ’ป 17471. ๊ฒŒ๋ฆฌ๋งจ๋”๋ง

March 03, 2022

๋ฌธ์ œ ๋ฐฑ์ค€์‹œ์˜ ์‹œ์žฅ ์ตœ๋ฐฑ์ค€์€ ์ง€๋‚œ ๋ช‡ ๋…„๊ฐ„ ๊ฒŒ๋ฆฌ๋งจ๋”๋ง์„ ํ†ตํ•ด์„œ ์ž์‹ ์˜ ๋‹น์—๊ฒŒ ์œ ๋ฆฌํ•˜๊ฒŒ ์„ ๊ฑฐ๊ตฌ๋ฅผ ํš์ •ํ–ˆ๋‹ค. ๊ฒฌ์ œํ•  ๊ถŒ๋ ฅ์ด ์—†์–ด์ง„ ์ตœ๋ฐฑ์ค€์€ ๊ถŒ๋ ฅ์„ ๋งค์šฐ ๋ถ€๋‹นํ•˜๊ฒŒ ํ–‰์‚ฌํ–ˆ๊ณ , ์‹ฌ์ง€์–ด๋Š” ์‹œ์˜ ์ด๋ฆ„๋„ ๋ฐฑ์ค€์‹œ๋กœ ๋ณ€๊ฒฝํ–ˆ๋‹ค. ์ด๋ฒˆ ์„ ๊ฑฐ์—์„œ๋Š” ์ตœ๋Œ€ํ•œ ๊ณตํ‰ํ•˜๊ฒŒ ์„ ๊ฑฐ๊ตฌ๋ฅผ ํš์ •ํ•˜๋ ค๊ณ  ํ•œ๋‹ค. ๋ฐฑ์ค€์‹œ๋Š” N๊ฐœ์˜ ๊ตฌ์—ญ์œผ๋กœ ๋‚˜๋ˆ„์–ด์ ธ ์žˆ๊ณ , ๊ตฌ์—ญ์€ 1๋ฒˆ๋ถ€ํ„ฐ N๋ฒˆ๊นŒ์ง€ ๋ฒˆํ˜ธ๊ฐ€ ๋งค๊ฒจ์ ธ ์žˆ๋‹ค. โ€ฆ