๐Ÿ“ algorithm

๐Ÿ’™ ๋ฌธ์ œ ์„ค๋ช… ์ž‘๋…„์— ์ด์–ด ์ƒˆ๋กœ์šด ๋ฌธ์ž์—ด ๊ฒŒ์ž„์ด ์žˆ๋‹ค. ๊ฒŒ์ž„์˜ ์ง„ํ–‰ ๋ฐฉ์‹์€ ์•„๋ž˜์™€ ๊ฐ™๋‹ค.์•ŒํŒŒ๋ฒณ ์†Œ๋ฌธ์ž๋กœ ์ด๋ฃจ์–ด์ง„ ๋ฌธ์ž์—ด W๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.์–‘์˜ ์ •์ˆ˜ K๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.์–ด๋–ค ๋ฌธ์ž๋ฅผ ์ •ํ™•ํžˆ K๊ฐœ๋ฅผ ํฌํ•จํ•˜๋Š” ๊ฐ€์žฅ ์งง์€ ์—ฐ์† ๋ฌธ์ž์—ด์˜ ๊ธธ์ด๋ฅผ ๊ตฌํ•œ๋‹ค.์–ด๋–ค ๋ฌธ์ž๋ฅผ ์ •ํ™•ํžˆ K๊ฐœ๋ฅผ ํฌํ•จํ•˜๊ณ , ๋ฌธ์ž์—ด์˜ ์ฒซ ๋ฒˆ์งธ์™€ ๋งˆ์ง€๋ง‰ ๊ธ€์ž๊ฐ€ ํ•ด๋‹น ๋ฌธ์ž๋กœ ๊ฐ™์€ ๊ฐ€์žฅ ๊ธด ์—ฐ์† ๋ฌธ์ž์—ด์˜ ๊ธธ์ด๋ฅผ ๊ตฌํ•œ๋‹ค.์œ„์™€ ๊ฐ™์€ ๋ฐฉ์‹์œผ๋กœ ๊ฒŒ์ž„์„ TํšŒ ์ง„ํ–‰ํ•œ๋‹ค. ๐Ÿ’› ์ž…๋ ฅ ๋ฌธ์ž์—ด ๊ฒŒ์ž„์˜ ์ˆ˜ T๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (1 โ‰ค T โ‰ค 100)๋‹ค์Œ ์ค„๋ถ€ํ„ฐ 2๊ฐœ์˜ ์ค„ ๋™์•ˆ ๋ฌธ์ž์—ด W์™€ ์ •์ˆ˜ K๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (1 โ‰ค K โ‰ค |W| โ‰ค 10,000)  ๐Ÿ’š ์ถœ๋ ฅ T๊ฐœ์˜ ์ค„ ๋™์•ˆ ๋ฌธ์ž์—ด ๊ฒŒ์ž„์˜ 3๋ฒˆ๊ณผ 4๋ฒˆ์—์„œ ๊ตฌํ•œ ์—ฐ์† ๋ฌธ์ž์—ด์˜ ๊ธธ์ด๋ฅผ ๊ณต๋ฐฑ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ถœ๋ ฅํ•œ๋‹ค.๋งŒ์•ฝ ๋งŒ์กฑํ•˜๋Š” ์—ฐ์† ..
๐Ÿ’™ ๋ฌธ์ œ ์„ค๋ช… N๊ฐœ์˜ ๋„์‹œ๊ฐ€ ์žˆ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ํ•œ ๋„์‹œ์—์„œ ์ถœ๋ฐœํ•˜์—ฌ ๋‹ค๋ฅธ ๋„์‹œ์— ๋„์ฐฉํ•˜๋Š” M๊ฐœ์˜ ๋ฒ„์Šค๊ฐ€ ์žˆ๋‹ค. ์šฐ๋ฆฌ๋Š” A๋ฒˆ์งธ ๋„์‹œ์—์„œ B๋ฒˆ์งธ ๋„์‹œ๊นŒ์ง€ ๊ฐ€๋Š”๋ฐ ๋“œ๋Š” ๋ฒ„์Šค ๋น„์šฉ์„ ์ตœ์†Œํ™” ์‹œํ‚ค๋ ค๊ณ  ํ•œ๋‹ค. A๋ฒˆ์งธ ๋„์‹œ์—์„œ B๋ฒˆ์งธ ๋„์‹œ๊นŒ์ง€ ๊ฐ€๋Š”๋ฐ ๋“œ๋Š” ์ตœ์†Œ๋น„์šฉ์„ ์ถœ๋ ฅํ•˜์—ฌ๋ผ. ๋„์‹œ์˜ ๋ฒˆํ˜ธ๋Š” 1๋ถ€ํ„ฐ N๊นŒ์ง€์ด๋‹ค.  ๐Ÿ’› ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ๋„์‹œ์˜ ๊ฐœ์ˆ˜ N(1 โ‰ค N โ‰ค 1,000)์ด ์ฃผ์–ด์ง€๊ณ  ๋‘˜์งธ ์ค„์—๋Š” ๋ฒ„์Šค์˜ ๊ฐœ์ˆ˜ M(1 โ‰ค M โ‰ค 100,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๊ทธ๋ฆฌ๊ณ  ์…‹์งธ ์ค„๋ถ€ํ„ฐ M+2์ค„๊นŒ์ง€ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋ฒ„์Šค์˜ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋จผ์ € ์ฒ˜์Œ์—๋Š” ๊ทธ ๋ฒ„์Šค์˜ ์ถœ๋ฐœ ๋„์‹œ์˜ ๋ฒˆํ˜ธ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๊ทธ ๋‹ค์Œ์—๋Š” ๋„์ฐฉ์ง€์˜ ๋„์‹œ ๋ฒˆํ˜ธ๊ฐ€ ์ฃผ์–ด์ง€๊ณ  ๋˜ ๊ทธ ๋ฒ„์Šค ๋น„์šฉ์ด ์ฃผ์–ด์ง„๋‹ค. ๋ฒ„์Šค ๋น„์šฉ์€ 0๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , 100,000๋ณด๋‹ค ์ž‘์€ ์ •..
๐Ÿ’™ ๋ฌธ์ œ ์„ค๋ช… ํ•œ์ˆ˜๋Š” ํฌ๊ธฐ๊ฐ€ 2N ร— 2N์ธ 2์ฐจ์› ๋ฐฐ์—ด์„ Z๋ชจ์–‘์œผ๋กœ ํƒ์ƒ‰ํ•˜๋ ค๊ณ  ํ•œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, 2ร—2๋ฐฐ์—ด์„ ์™ผ์ชฝ ์œ„์นธ, ์˜ค๋ฅธ์ชฝ ์œ„์นธ, ์™ผ์ชฝ ์•„๋ž˜์นธ, ์˜ค๋ฅธ์ชฝ ์•„๋ž˜์นธ ์ˆœ์„œ๋Œ€๋กœ ๋ฐฉ๋ฌธํ•˜๋ฉด Z๋ชจ์–‘์ด๋‹ค.  N > 1์ธ ๊ฒฝ์šฐ, ๋ฐฐ์—ด์„ ํฌ๊ธฐ๊ฐ€ 2 ^ N-1 ร— 2 ^ N-1๋กœ 4๋“ฑ๋ถ„ ํ•œ ํ›„์— ์žฌ๊ท€์ ์œผ๋กœ ์ˆœ์„œ๋Œ€๋กœ ๋ฐฉ๋ฌธํ•œ๋‹ค.๋‹ค์Œ ์˜ˆ๋Š” 2^2 ร— 2^2 ํฌ๊ธฐ์˜ ๋ฐฐ์—ด์„ ๋ฐฉ๋ฌธํ•œ ์ˆœ์„œ์ด๋‹ค.  N์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, rํ–‰ c์—ด์„ ๋ช‡ ๋ฒˆ์งธ๋กœ ๋ฐฉ๋ฌธํ•˜๋Š”์ง€ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.๋‹ค์Œ์€ N=3์ผ ๋•Œ์˜ ์˜ˆ์ด๋‹ค. ๐Ÿ’› ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ •์ˆ˜ N, r, c๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๐Ÿ’š ์ถœ๋ ฅ rํ–‰ c์—ด์„ ๋ช‡ ๋ฒˆ์งธ๋กœ ๋ฐฉ๋ฌธํ–ˆ๋Š”์ง€ ์ถœ๋ ฅํ•œ๋‹ค.  ๐Ÿšซ ์ œํ•œ์‚ฌํ•ญ1 โ‰ค N โ‰ค 150 โ‰ค r, c ์‹œ๊ฐ„์ œํ•œ : 0.5 sโค๏ธ ๋ฌธ์ œ ํ’€์ด ๋ฐฉ๋ฒ• 1๏ธโƒฃ while ๋ฐ˜..
์˜ค๋žœ๋งŒ์— ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ ํ’€์ด๋ฅผ ๋‹ค์‹œ ๋ธ”๋กœ๊ทธ์— ์˜ฌ๋ฆฌ๊ฒŒ ๋œ ์ด์œ ๊ฐ€ ๋‘๊ฐ€์ง€ ์žˆ๋‹ค.์ฒซ๋ฒˆ์งธ๋กœ, ๋ฌธ์ œ ํ’€๊ณ  ๋” ๋‚˜์€ ์ฝ”๋“œ๋ฅผ ์ฐพ์•„๋ณด๊ฑฐ๋‚˜ ๊ณ ๋ฏผํ•˜๋Š” ์‹œ๊ฐ„์ด ๋ถ€์กฑํ•œ ๊ฒƒ ๊ฐ™์•„์„œ์ด๋‹ค. ๊ณจ๋“œ ๋ฌธ์ œ๋กœ ์˜ฌ๋ผ์˜ค๋‹ˆ๊นŒ ํ•œ ๋ฌธ์ œ ํ’€์ด์—๋„ ์˜ค๋ž˜ ๊ฑธ๋ ค์„œ, ๋ฌธ์ œ๋ฅผ ํ’€๊ณ  ๋‚œ ๋’ค์— ์‹œ๊ฐ„์„ ๋งŽ์ด ์•ˆ๋“ค์ด๊ฒŒ ๋˜์—ˆ๋‹ค.๊ทธ๋Ÿฌ๋‹ค๋ณด๋‹ˆ ๋ฌธ์ œ ํ’€์ด ๋ฐฉ์‹๋„ ํ•œ์ •์ ์ด๊ณ  ๋” ํ‹ฐ์–ด ๋†’์•„์ง€๋ฉด ๋ชป ํ‘ธ๋Š” ๋ฌธ์ œ๊ฐ€ ๋„ˆ๋ฌด ๋งŽ์•„์งˆ ๊ฒƒ ๊ฐ™์•˜๋‹ค.์—ฌ๋Ÿฌ ๋ฐฉ์‹์˜ ๋ฌธ์ œ ํ’€์ด๋ฅผ ์ง„ํ–‰ํ•˜๊ณ  ๋ธ”๋กœ๊ทธ์— ์˜ฌ๋ฆฌ๋ฉด ๋‚˜๋„ ์ œ๋Œ€๋กœ ์ดํ•ดํ•˜๊ณ  ๋„˜์–ด๊ฐˆ ๊ฒƒ ๊ฐ™๋‹ค๋Š” ๊ฒŒ ์ฒซ๋ฒˆ์งธ ์ด์œ ๋‹ค. ๋‘๋ฒˆ์งธ๋กœ, ๋ณ€์ˆ˜๋ช…์„ ์ข€ ๋” ์‹ ๊ฒฝ ์“ฐ๊ณ  ์‹ถ์–ด์กŒ๋‹ค. ๋ถ€ํŠธ์บ ํ”„ ๋‹ค๋‹ˆ๋ฉด์„œ ๋ฌธ์ œ ํ’€ ๋•Œ๋„ ๊ทธ๋ ‡๊ณ  ํ”„๋กœ์ ํŠธ ํ•  ๋•Œ๋„ ์‚ฌ์‹ค ๋ณ€์ˆ˜๋ช…์— ํฌ๊ฒŒ ์‹ ๊ฒฝ์„ ์•ˆ์ผ๋˜ ๊ฒƒ ๊ฐ™๋‹ค.ํ•œ๋ฒˆ ํ’€๊ณ  ๋ง ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ๋Š” ํŠนํžˆ.๊ทธ๋ฆฌ๊ณ  ๋ณ€์ˆ˜๋ช…์ด ๊ธธ๋ฉด ์•ˆ๋œ๋‹ค๋Š” ๊ฐ•๋ฐ•๊ฐ™์€ ๊ฒŒ ์žˆ์—ˆ๋Š”๋ฐ, ..