2022 ์ƒ๋ฐ˜๊ธฐ ์‚ผ์„ฑSDS ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ํ›„๊ธฐ

์ฝ”๋”ฉํ…Œ์ŠคํŠธ ํ›„๊ธฐ

์ข€ ๋งŽ์ด ์ง€๋‚˜๊ธด ํ–ˆ์ง€๋งŒ 2022๋…„ 5์›” 1์ผ์— ์žˆ์—ˆ๋˜ ์‚ผ์„ฑSDS ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ํ›„๊ธฐ๋ฅผ ์ž‘์„ฑํ•ด๋ณด๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

 

ํ›„๊ธฐ๋ผ๊ธฐ๋ณด๋‹ค๋Š” ์–ด๋–ป๊ฒŒ ์ค€๋น„ํ–ˆ์—ˆ๋Š”์ง€๊ฐ€ ๋” ๋งž๋Š” ๊ฒƒ ๊ฐ™์ง€๋งŒ ์ผ๋‹จ ๊ธฐ๋กํ•ด๋‘๋ฉด ๋ฆฌ๋งˆ์ธ๋“œํ•˜๋ฉด์„œ ๋‹ค์‹œ ๊ณต๋ถ€ํ•  ๋งˆ์Œ์„ ์žก์„ ์ˆ˜ ์žˆ์„ ๊ฒƒ ๊ฐ™์•„์„œ์š” :)

 

์ž˜ ์•Œ๋ ค์ง„ ๋Œ€๋กœ ์‚ผ์„ฑ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ๋Š” 3์‹œ๊ฐ„ ๋™์•ˆ 2๋ฌธ์ œ๊ฐ€ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค!

์ €๋Š” 1๋ฌธ์ œ๋งŒ ํŒฌ๋‹ค...๋ผ๋Š” ๋งˆ์Œ๊ฐ€์ง์œผ๋กœ 3์‹œ๊ฐ„ ๋™์•ˆ 1๋ฌธ์ œ๋ฅผ ์—ด์‹ฌํžˆ ํ’€์—ˆ์Šต๋‹ˆ๋‹ค.

์ €๋Š” ์˜คํ›„ ์‹œ๊ฐ„์ด์—ˆ๋Š”๋ฐ ๋‹น์—ฐํžˆ ์ฒซ ๋ฒˆ์งธ ๋ฌธ์ œ๊ฐ€ ๋” ์‰ฝ๊ฒ ์ง€ ์ƒ๊ฐํ•ด์„œ ๋จผ์ € ์—ด์–ด์„œ ํ’€์—ˆ์–ด์š”.

๊ทผ๋ฐ ๋‹ค ํ’€๊ณ  ๋‘ ๋ฒˆ์งธ ๋ฌธ์ œ ์—ด์–ด๋ณด๋‹ˆ ๋‘๋ฒˆ์งธ ๋ฌธ์ œ๊ฐ€ ๋” ์‰ฌ์› ๋˜...

๋ฌธ์ œ ์˜คํ”ˆ ์‹œ๊ฐ„์— ๋”ฐ๋ผ์„œ๋„ ํ•ฉ๊ฒฉ ์—ฌ๋ถ€๊ฐ€ ๋‹ฌ๋ผ์ง„๋‹ค๋Š” ๋ง์ด ์žˆ์–ด์„œ ์‰ฝ์‚ฌ๋ฆฌ ๋‘๋ฒˆ์งธ ๋ฌธ์ œ๋ฅผ ์—ด์–ด๋ณด์ง€ ๋ชปํ–ˆ์–ด์š”.

์ฒซ ๋ฒˆ์งธ ๋ฌธ์ œ๋ฅผ ์ญ‰ ์ฝ์–ด๋ณด๋Š”๋ฐ ๋ฌธ์ œ ์ดํ•ด๋Š” ๋ฐ”๋กœ ๋‹ค ํ•  ์ˆ˜ ์žˆ์—ˆ๊ณ , ๊ตฌํ˜„๋„ ์นจ์ฐฉํ•˜๊ฒŒ ๊ตฌํ˜„ํ•˜๋ฉด ํ•  ์ˆ˜ ์žˆ์„ ๊ฒƒ ๊ฐ™๋‹ค๋Š” ์ƒ๊ฐ์— ํ’€์ด๋ฅผ ์ง„ํ–‰ํ–ˆ์Šต๋‹ˆ๋‹ค!

 

๊ทธ๋ž˜์„œ ๋‹ค ๊ตฌํ˜„ํ–ˆ์„ ๋•Œ๋Š” 1์‹œ๊ฐ„ 30๋ถ„ ์ •๋„ ์†Œ์š”๋˜์—ˆ๊ณ , ์ œ์ถœํ–ˆ๋”๋‹ˆ Runtime Error๊ฐ€ ๋– ์„œ ๋””๋ฒ„๊น…ํ–ˆ์Šต๋‹ˆ๋‹ค.

์ด๊ฑด ๋ฐฐ์—ด ๋ฒ”์œ„ ๋ฌธ์ œ์ธ ๊ฑฐ ๊ฐ™์•„์„œ..!

๋ฌด์กฐ๊ฑด ๋ฐฐ์—ด ์ฒจ๋ถ€ํ„ฐ ๋๊นŒ์ง€ ๋‹ค ํ™•์ธํ•˜๋„๋ก ํ•˜์ง€ ๋ง๊ณ , ๋‚˜๋ฆ„ ์‹œ์ž‘์ ๊ณผ ๋์ ์„ ์ง€์ •ํ•ด์ฃผ์–ด์„œ ํ™•์ธํ•˜๋„๋ก ํ•ด์คฌ๋”๋‹ˆ ํ•ด๊ฒฐ๋์Šต๋‹ˆ๋‹ค.

๊ทธ๋ž˜์„œ ์ €๋Š” ์ฒซ ๋ฒˆ์งธ ๋ฌธ์ œ ํ‘ธ๋Š” ๋ฐ ์ด 2์‹œ๊ฐ„ ๊ฑธ๋ ธ๊ณ , ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋Š” ๋‹ค ํ†ต๊ณผํ•œ ์ƒํƒœ๋กœ ์ œ์ถœํ–ˆ์Šต๋‹ˆ๋‹ค.

 

๊ทธ๋Ÿฌ๊ณ  ๋‘ ๋ฒˆ์งธ ๋ฌธ์ œ ํ‘ธ๋Š” ๋ฐ ์ƒ๊ฐ๋ณด๋‹ค ์‰ฌ์›Œ์„œ ๋น ๋ฅด๊ฒŒ ๊ตฌํ˜„ํ•ด๋ณด์•˜์ง€๋งŒ... ๊ฒฐ๊ตญ ์‹œ๊ฐ„์ด ๋ถ€์กฑํ•ด์„œ ๋‹ค ํ’€์ง€๋Š” ๋ชปํ–ˆ์Šต๋‹ˆ๋‹คใ… 

 

์ฒซ ๋ฒˆ์งธ ๋ฌธ์ œ๋ฅผ ํ‘ธ๋Š” ๋ฐ ์‹œ๊ฐ„์ด ์ข€ ๊ฑธ๋ ธ๊ณ , ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋งŒ ํ†ต๊ณผํ–ˆ์—ˆ๊ธฐ์— ๋ฐœํ‘œ ๋‚˜๊ธฐ ์ „๊นŒ์ง€๋Š” ๊ณ„์† ์กฐ๋งˆ์กฐ๋งˆํ–ˆ์–ด์š”..!

์–ด๋–ค ๋ธ”๋กœ๊ฑฐ ์–˜๊ธฐ๋ฅผ ๋ณด๋ฉด ํ•œ ๋ฌธ์ œ ํ’€์—ˆ๋Š”๋ฐ๋„ ๋นจ๋ฆฌ ๋ชป ํ’€์–ด์„œ ํ†ต๊ณผ๋ฅผ ๋ชปํ–ˆ๋˜ ๊ฒƒ ๊ฐ™๋‹ค๋Š” ๋ถ„๋„ ์žˆ์—ˆ๊ณ ,

๋นจ๋ฆฌ ํ’€์—ˆ๋Š”๋ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค ์™ธ์˜ ์ผ€์ด์Šค๋„ ๋” ๋Œ๋ ค๋ณด๊ธฐ ๋•Œ๋ฌธ์— ๊ฑฐ๊ธฐ์„œ ๋ง‰ํ˜”๋˜ ๊ฒƒ ๊ฐ™๋‹ค๋Š” ๋ถ„๋„ ์žˆ์–ด์„œ์š”..ใ… 

๋ถˆํ•ฉ๊ฒฉํ•˜๋Š” ๊ฟˆ๋„ ๊ฟจ์–ด์„œ ๋ฐœํ‘œ๋‚  ๋•Œ๊นŒ์ง€ ์•ฝ 3~4์ฃผ๊ฐ„์€ ๋ถˆ์•ˆ๋ถˆ์•ˆํ–ˆ์Šต๋‹ˆ๋‹ค.

๋‹คํ–‰ํžˆ๋„ ๊ฒฐ๊ณผ๋Š” ํ•ฉ๊ฒฉ! ๊ทธ ์ดํ›„ ์‹œ๊ฐ„ ๋‚  ๋•Œ๋งˆ๋‹ค ์—ด์‹ฌํžˆ ๋†€์•„์คฌ์Šต๋‹ˆ๋‹คใ…‹ใ…‹ใ…‹ใ…‹ใ…‹

 

 

์ค€๋น„ ๊ณผ์ •

๋ถ€ํŠธ์บ ํ”„ ๋•Œ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์ค€๋น„๋ฅผ ๊ฑฐ์˜ ํ•˜์ง€ ์•Š์•˜์—ˆ๊ณ , ์˜ฌํ•ด ์ง„ํ–‰ํ–ˆ๋˜ ๊ต์œก๊ณผ์ •์—์„œ ํ•œ 3์›”๋ถ€ํ„ฐ ๋ณธ๊ฒฉ์ ์œผ๋กœ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์ค€๋น„๋ฅผ ํ–ˆ์—ˆ๋Š”๋ฐ์š”!

 

9์‹œ๋ถ€ํ„ฐ 18์‹œ๊นŒ์ง€ ์•ฝ 3์ฃผ๊ฐ„ ๋งค์ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ˆ˜์—…์„ ๋“ค์—ˆ์Šต๋‹ˆ๋‹ค.

์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ˆ˜์—… ๊ณผ์ •์ด ๋๋‚˜๊ณ  ๋‚˜์„œ๋Š” ๋ฐ”๋กœ ๋‹ค๋ฅธ ์ˆ˜์—… ๊ณผ์ •์ด ์ง„ํ–‰๋˜๋Š”๋ฐ ๊ฐ์„ ์žƒ์ง€ ์•Š๊ธฐ ์œ„ํ•ด ์‹œํ—˜ ๋ณผ ๋•Œ๊นŒ์ง€

ํ‰์ผ์—๋Š” 19์‹œ๋ถ€ํ„ฐ ์ ์œผ๋ฉด 3์‹œ๊ฐ„ ๋งŽ์œผ๋ฉด 5์‹œ๊ฐ„ ์ •๋„ ๊ณต๋ถ€ํ–ˆ๊ณ 

์ฃผ๋ง์—๋Š” ์•ฝ์†์ด ์—†์„ ๋•Œ๋Š” ๊ฑฐ์˜ ๋‹ค ๊ณต๋ถ€ํ–ˆ์—ˆ๋˜ ๋“ฏํ•ฉ๋‹ˆ๋‹ค..ใ…Žใ…Žใ…Ž

 

๋ฌธ์ œ ํ‘ธ๋А๋ผ ์ •์‹ ์—†์–ด์„œ ๋ธ”๋กœ๊น…์„ ๊พธ์ค€ํžˆ ํ•˜์ง€๋Š” ๋ชปํ–ˆ์ง€๋งŒ.. ์ €๋Š” ๋ฐฑ์ค€์— ์‚ผ์„ฑ SW ์—ญ๋Ÿ‰ ํ…Œ์ŠคํŠธ ๊ธฐ์ถœ ๋ฌธ์ œ๋ฅผ ๋‹ค ํ’€์—ˆ์Šต๋‹ˆ๋‹ค!

์‹œํ—˜ ์ง์ „์—๋Š” ์ตœ๊ทผ ๊ธฐ์ถœ ๋ฌธ์ œ๋Š” 2๋ฒˆ์”ฉ ํ’€์–ด๋ณด๋ฉด์„œ ์ตœ๊ทผ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ๊ฒฝํ–ฅ์„ ํŒŒ์•…ํ•˜๋ ค๊ณ  ํ–ˆ์Šต๋‹ˆ๋‹ค.

 

๊ทธ๋ฆฌ๊ณ  ๊ฐœ์ธ์ ์œผ๋กœ ์ €๋Š” ๋ฐฐ์—ด์„ ๋น ๋ฅธ ์‹œ๊ฐ„ ๋‚ด์— ๋Œ๋ฆฌ๊ณ  ์ž๋ฅด๋Š” ๋“ฑ ๋ณ€ํ˜•ํ•˜๋Š” ๊ฑธ ์ž˜ํ•˜์ง€ ๋ชปํ–ˆ๋Š”๋ฐ์š”.

๊ทธ ๋ถ€๋ถ„์„ ์ตœ๋Œ€ํ•œ ๋ณด์™„ํ•˜๋ ค๊ณ  ํ–ˆ์Šต๋‹ˆ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด ๋ฐฑ์ค€์—์„œ ์–ดํ•ญ ์ •๋ฆฌ ๋ฌธ์ œ๊ฐ€ ๋ฐฐ์—ด์„ ๋Œ๋ฆฌ๊ณ  ๊ฒน์น˜๊ฒŒ ํ•˜๋Š” ๊ตฌํ˜„์ด ๋งŽ์•˜๋Š”๋ฐ ๊ทธ ๋ถ€๋ถ„๋งŒ ์ œํ•œ์‹œ๊ฐ„์„ ๋‘๊ณ  ๋น ๋ฅด๊ฒŒ ๊ตฌํ˜„ํ•ด๋ณด๋ ค๊ณ  ํ–ˆ์Šต๋‹ˆ๋‹ค.

์ค€๋น„ํ•˜์‹œ๋Š” ๋ถ„๋“ค๋„ ๋ถ€์กฑํ•œ ๋ถ€๋ถ„์„ ๋ฐ˜๋ณต์ ์œผ๋กœ ์—ฐ์Šตํ•ด๋ณด๋Š” ๊ฒƒ๋„ ์ข‹์„ ๊ฒƒ ๊ฐ™์•„์š”!

https://www.acmicpc.net/workbook/view/1152

 

๋ฌธ์ œ์ง‘: ์‚ผ์„ฑ SW ์—ญ๋Ÿ‰ ํ…Œ์ŠคํŠธ ๊ธฐ์ถœ ๋ฌธ์ œ (baekjoon)

 

www.acmicpc.net

 

๋งˆ์ง€๋ง‰์œผ๋กœ ์•„๋ฌด๋ž˜๋„ ์ฒด๋ ฅ๊ณผ ๋ฉ˜ํƒˆ ๊ด€๋ฆฌ๊ฐ€ ์ œ์ผ ์ค‘์š”ํ•œ ๋“ฏํ•ฉ๋‹ˆ๋‹ค.

3์‹œ๊ฐ„ ์•ˆ์— ๋ฌธ์ œ๋ฅผ ํ’€์ง€ ๋ชปํ•˜๊ฑฐ๋‚˜ ๋” ์ด์ƒ ์–ด๋–ป๊ฒŒ ํ’€์–ด์•ผ ํ• ์ง€ ๊ฐ์ด ์•ˆ ์žกํž ๋•Œ ๋‹ค๋ฅธ ๋ถ„๋“ค์˜ ์ฝ”๋“œ๋ฅผ ์ฐธ๊ณ ํ•ด๊ฐ€๋ฉด์„œ ํ’€์—ˆ๋Š”๋ฐ์š”.

๊ทธ๋Ÿด ๋•Œ๋งˆ๋‹ค ์ž์‹ ๊ฐ์ด ๋–จ์–ด์ง€๋ฉด์„œ '๊ณผ์—ฐ ๋‚ด๊ฐ€ ํ•ฉ๊ฒฉํ•  ์ˆ˜ ์žˆ์„๊นŒ'๋ผ๋Š” ์ƒ๊ฐ์ด ๋งŽ์ด ๋‚ฌ๋˜ ๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค.

์ฃผ๋ณ€ ์นœ๊ตฌ๋“ค์ด๋‚˜ ๊ฐ€์กฑ๋“คํ•œํ…Œ ์–˜๊ธฐํ•˜๋ฉด ์‘์›ํ•ด์ฃผ๊ณ , ์„ฑ์‹คํžˆ ์ค€๋น„ํ•˜๋ฉด ๋ถ™์„ ์ˆ˜ ์žˆ์„ ๊ฑฐ๋‹ค!๋ผ๋Š” ๋ง๋„ ๋งŽ์ด ๋“ค์—ˆ์–ด์š”.

๊ทธ๋Ÿผ ๋˜๋‹ค์‹œ ํž˜๋‚ด์„œ ๋ฌธ์ œ ํ’€๋ฉด์„œ ๋ฉ˜ํƒˆ ๊ด€๋ฆฌ๋ฅผ ํ•ด๋‚˜๊ฐ”์Šต๋‹ˆ๋‹ค. 

๋˜ ์ผ์ฃผ์ผ์— ์„œ๋„ˆ ๋ฒˆ ์ •๋„๋Š” ํ•œ ์‹œ๊ฐ„ ์ด์ƒ ์šด๋™ํ–ˆ์Šต๋‹ˆ๋‹ค.

์•ˆ ํ•˜๋ฉด ์˜คํžˆ๋ ค ๋จธ๋ฆฌ๊ฐ€ ๋ฉํ•ด์ง€๋Š” ๋А๋‚Œ์ด ๋“ค์–ด์„œ ์–ต์ง€๋กœ๋ผ๋„ ์งฌ์„ ๋‚ด์–ด์„œ ์šด๋™ํ–ˆ์Šต๋‹ˆ๋‹ค!

 

 

 

 

์‹œํ—˜ ๋ณด๊ณ  ๋‚œ ํ›„ ๋‹ค๋ฅธ ๊ณผ๋ชฉ ๊ณต๋ถ€ํ•˜๊ณ  ๊ทธ๋™์•ˆ ๋ชป ๋ดค๋˜ ์นœ๊ตฌ๋“ค ๋งŒ๋‚˜๋А๋ผ ์„ธ ๋‹ฌ ๋™์•ˆ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ณต๋ถ€๋ฅผ ๋†“๊ณ  ์žˆ์—ˆ๋„ค์š”ใ…Žใ…Žใ…Ž

์ด์ œ ๋‹ค์‹œ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ณต๋ถ€๋ฅผ ์กฐ๊ธˆ์”ฉ ํ•ด๋ณด๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค!

์ด๋ ‡๊ฒŒ ๋งํ–ˆ์œผ๋‹ˆ ๊ณต๋ถ€ํ•˜๊ฒ ์ง€...

 

'Coding Test' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

BOJ 1717: ์ง‘ํ•ฉ์˜ ํ‘œํ˜„  (0) 2022.07.22
Union-Find (ํ•ฉ์ง‘ํ•ฉ ์ฐพ๊ธฐ)  (0) 2022.07.22
<C/C++> BOJ 15683 ๊ฐ์‹œ  (0) 2022.05.06
<C/C++> BOJ 12100 2048(Easy)  (0) 2022.05.04
<C/C++> BOJ 14501: ํ‡ด์‚ฌ  (0) 2022.05.03