[Algorithm] - 2021 ์นด์นด์˜ค ์‹ ์ž… 1์ฐจ ์˜จ๋ผ์ธ ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ (Kakao Newbie Primary Online Coding Test) for Tech Developers ๋ฌธ์ œ ํ’€์ด

๋ฐ˜์‘ํ˜•

์ง€๋‚œ ์ฃผ, 2021๋…„ ์นด์นด์˜ค ์‹ ์ž… ์˜จ๋ผ์ธ ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ ๋ฌธ์ œ ํ’€์ด๊ฐ€ ์นด์นด์˜ค ๊ณต์‹ ๋ธ”๋กœ๊ทธ์— ์˜ฌ๋ผ์˜ค๊ฒŒ ๋˜๋ฉด์„œ ํ’€์ด๋ฅผ ํ•ด๋ณด๊ฒŒ ๋˜์—ˆ์Šต๋‹ˆ๋‹ค. ๊ฐœ์ธ์ ์œผ๋กœ ์ธํ„ด์‹ญ ๋ฌธ์ œ๋‚˜ ์ด๋Ÿฐ ๋ฌธ์ œ๋“ค๋„ ๋งŽ์ด ๋ดค์—ˆ๋Š”๋ฐ, ์‹ ์ž… ๋ฌธ์ œ๋ฅผ ํ’€์ดํ•œ ๊ฒƒ์€ ๊ฑฐ์˜ ์—†์—ˆ๋Š”๋ฐ์š”.

 

๋จผ์ € ์งค๋ง‰ํ•˜๊ฒŒ ์š”์ ์„ ๋ง์”€๋“œ๋ฆฌ์ž๋ฉด ์ธํ„ด์‹ญ ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ์™€ ์‹ ์ž… ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ์˜ ๋ฌธ์ œ ๋‚œ์ด๋„๊ฐ€ ์กฐ๊ธˆ ์ฐจ์ด๊ฐ€ ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค. DFS๋‚˜ BFS ๋ฌธ์ œ๋“ค์ด ๊ฐ€๋” ํ•œ ๋ฌธ์ œ ์ •๋„ ๋‚˜์˜ค๋Š” ์ธํ„ด์‹ญ ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ์— ๋น„ํ•ด ์‹ ์ž… ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ์—์„œ๋Š” ๋ฐฑํŠธ๋ž˜ํ‚น์ด๋‚˜ ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ ๊ฐ™์€ Computer Science์˜ ๊ธฐ๋ณธ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ตฌํ˜„ ๋ฌธ์ œ๋„ ๊ฐ™์ด ์žˆ์–ด์„œ ์ด๋Ÿฌํ•œ ๋ถ€๋ถ„๋„ ์กฐ๊ธˆ ์ค€๋น„๋ฅผ ํ•ด๋‘๋Š” ๊ฒŒ ์ข‹์„ ๊ฒƒ ๊ฐ™๋‹ค๋ผ๋Š” ์ƒ๊ฐ์„ ํ–ˆ์Šต๋‹ˆ๋‹ค.

 

๊ทธ๋Ÿผ ๋ฌธ์ œ ํ’€์ด๋ฅผ ์‹œ์ž‘ํ•ด๋ณด๋„๋ก ํ•˜์ฃ .

 

 

 

 

Question 01. ์•„์ด๋”” ์ถ”์ฒœ

๋ฌธ์ œ ์›๋ฌธ: (https://programmers.co.kr/learn/courses/30/lessons/72410)

 

์นด์นด์˜ค์— ์ž…์‚ฌํ•œ ์‹ ์ž… ๊ฐœ๋ฐœ์ž ๋„ค์˜ค๋Š” “์นด์นด์˜ค๊ณ„์ •๊ฐœ๋ฐœํŒ€”์— ๋ฐฐ์น˜๋˜์–ด, ์นด์นด์˜ค ์„œ๋น„์Šค์— ๊ฐ€์ž…ํ•˜๋Š” ์œ ์ €๋“ค์˜ ์•„์ด๋””๋ฅผ ์ƒ์„ฑํ•˜๋Š” ์—…๋ฌด๋ฅผ ๋‹ด๋‹นํ•˜๊ฒŒ ๋˜์—ˆ๊ณ , “๋„ค์˜ค”์—๊ฒŒ ์ฃผ์–ด์ง„ ์ฒซ ์—…๋ฌด๋Š” ์ƒˆ๋กœ ๊ฐ€์ž…ํ•˜๋Š” ์œ ์ €๋“ค์ด ์นด์นด์˜ค ์•„์ด๋”” ๊ทœ์น™์— ๋งž์ง€ ์•Š๋Š” ์•„์ด๋””๋ฅผ ์ž…๋ ฅํ–ˆ์„ ๋•Œ, ์ž…๋ ฅ๋œ ์•„์ด๋””์™€ ์œ ์‚ฌํ•˜๋ฉด์„œ ๊ทœ์น™์— ๋งž๋Š” ์•„์ด๋””๋ฅผ ์ถ”์ฒœํ•ด ์ฃผ๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ๊ฐœ๋ฐœํ•˜๋Š” ๋ฌธ์ œ์˜€์Šต๋‹ˆ๋‹ค.

(์ด์ „ ๊ธ€๊ณผ ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ ๋ฌธ์ œ์— ๋Œ€ํ•œ ์ƒ์„ธ ์‚ฌํ•ญ์€ ์ƒ๋žตํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. ์ž์„ธํ•œ ๋ฌธ์ œ๋Š” ๋ฌธ์ œ ์›๋ฌธ์„ ์ฐธ๊ณ ํ•ด์ฃผ์„ธ์š”.)

 

 

Solution for Question 01

1๋ฒˆ ๋ฌธ์ œ๋Š” ๋ฌธ์ œ๋งŒ ์ž˜ ์ฝ์–ด๋ณด์…จ๋‹ค๋ฉด ๋”ฐ๋กœ ๋ฌธ์ œ๋ฅผ ํŒŒ์•…ํ•  ํ•„์š”๋„ ์—†์ด ์ •ํ•ด์ง„ ์ง€์นจ์‚ฌํ•ญ๋Œ€๋กœ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๊ตฌํ˜„ํ•˜๋ฉด ์‰ฝ๊ฒŒ ํ’€ ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ์˜€์Šต๋‹ˆ๋‹ค. ์ •๋‹ต๋ฅ ์ด ๋ฌด๋ ค 57%๊ฐ€ ๋„˜๋Š” ์‰ฌ์šด ๋ฌธ์ œ์˜€์Šต๋‹ˆ๋‹ค.

 

์ฃผ์–ด์ง„ ์กฐ๊ฑด์„ ์ •๊ทœ์‹์œผ๋กœ ํ’€์–ด๋‚ธ๋‹ค๋ฉด ์ข€ ๋” ๊น”๋”ํ•œ ์ฝ”๋“œ๋กœ ํ’€์–ด๋ณผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ •๊ทœ์‹์€ ๋Œ€๋ถ€๋ถ„ ๋ชจ๋“  ํ”„๋กœ๊ทธ๋ž˜๋ฐ ์–ธ์–ด์—์„œ ์ œ๊ณตํ•˜๋ฉฐ ์ •๊ทœ์‹์ด ์•„๋‹ˆ๋”๋ผ๋„ ์กฐ๊ธˆ ๋ฉ”์†Œ๋“œ๋ฅผ ๋ณต์žกํ•˜๊ฒŒ ๊ตฌํ˜„ํ•ด์„œ๋„ ํ’€ ์ˆ˜ ์žˆ๋Š” ๋ฐฉ๋ฒ• ๋“ฑ ์—ฌ๋Ÿฌ ๋ฐฉ๋ฒ•์ด ์žˆ์Šต๋‹ˆ๋‹ค.

 

์‹ฌ์ง€์–ด ์ฃผ์–ด์ง„ ์กฐ๊ฑด์˜ ์ž…๋ ฅ ๋ฌธ์ž์—ด ๊ธธ์ด๊ฐ€ 1,000์ž๋„ ๋˜์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์— ์ž์œ ๋กญ๊ฒŒ ํ’€ ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ๊ธฐ๋„ ํ–ˆ์Šต๋‹ˆ๋‹ค.

 

 

 

 

Question 02. ๋ฉ”๋‰ด ๋ฆฌ๋‰ด์–ผ

๋ฌธ์ œ ์›๋ฌธ; (https://programmers.co.kr/learn/courses/30/lessons/72411)

 

๋ ˆ์Šคํ† ๋ž‘์„ ์šด์˜ํ•˜๋˜ ์Šค์นดํ”ผ๋Š” ์ฝ”๋กœ๋‚˜19๋กœ ์ธํ•œ ๋ถˆ๊ฒฝ๊ธฐ๋ฅผ ๊ทน๋ณตํ•˜๊ณ ์ž ๋ฉ”๋‰ด๋ฅผ ์ƒˆ๋กœ ๊ตฌ์„ฑํ•˜๋ ค๊ณ  ๊ณ ๋ฏผํ•˜๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. ๊ธฐ์กด์—๋Š” ๋‹จํ’ˆ์œผ๋กœ๋งŒ ์ œ๊ณตํ•˜๋˜ ๋ฉ”๋‰ด๋ฅผ ์กฐํ•ฉํ•ด์„œ ์ฝ”์Šค์š”๋ฆฌ ํ˜•ํƒœ๋กœ ์žฌ๊ตฌ์„ฑํ•ด์„œ ์ƒˆ๋กœ์šด ๋ฉ”๋‰ด๋ฅผ ์ œ๊ณตํ•˜๊ธฐ๋กœ ๊ฒฐ์ •ํ–ˆ์Šต๋‹ˆ๋‹ค. ์–ด๋–ค ๋‹จํ’ˆ ๋ฉ”๋‰ด๋“ค์„ ์กฐํ•ฉํ•ด์„œ ์ฝ”์Šค์š”๋ฆฌ ๋ฉ”๋‰ด๋กœ ๊ตฌ์„ฑํ•˜๋ฉด ์ข‹์„์ง€ ๊ณ ๋ฏผํ•˜๋˜ “์Šค์นดํ”ผ”๋Š” ์ด์ „์— ๊ฐ ์†๋‹˜๋“ค์ด ์ฃผ๋ฌธํ•  ๋•Œ ๊ฐ€์žฅ ๋งŽ์ด ํ•จ๊ป˜ ์ฃผ๋ฌธํ•œ ๋‹จํ’ˆ ๋ฉ”๋‰ด๋“ค์„ ์ฝ”์Šค์š”๋ฆฌ ๋ฉ”๋‰ด๋กœ ๊ตฌ์„ฑํ•˜๊ธฐ๋กœ ํ–ˆ์Šต๋‹ˆ๋‹ค.

 

๋‹จ, ์ฝ”์Šค์š”๋ฆฌ ๋ฉ”๋‰ด๋Š” ์ตœ์†Œ 2๊ฐ€์ง€ ์ด์ƒ์˜ ๋‹จํ’ˆ ๋ฉ”๋‰ด๋กœ ๊ตฌ์„ฑํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๋˜ํ•œ, ์ตœ์†Œ 2๋ช… ์ด์ƒ์˜ ์†๋‹˜์œผ๋กœ๋ถ€ํ„ฐ ์ฃผ๋ฌธ๋œ ๋‹จํ’ˆ ๋ฉ”๋‰ด ์กฐํ•ฉ์— ๋Œ€ํ•ด์„œ๋งŒ ์ฝ”์Šค์š”๋ฆฌ ๋ฉ”๋‰ด ํ›„๋ณด์— ํฌํ•จํ•˜๊ธฐ๋กœ ํ–ˆ์œผ๋ฉฐ ์ฃผ๋ฌธํ•œ ๋ฉ”๋‰ด ์กฐํ•ฉ์„ ํ† ๋Œ€๋กœ ๊ฐ€์žฅ ๋งŽ์ด ์ฃผ๋ฌธํ•œ ๋ฉ”๋‰ด๋ฅผ ๊ณจ๋ฆฌ ์ฝ”์Šค์š”๋ฆฌ ๋ฉ”๋‰ด ํ›„๋ณด ๋ฆฌ์ŠคํŠธ๋ฅผ ๋ฝ‘์„ ์ˆ˜ ์žˆ๋„๋ก ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๊ตฌํ˜„ํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

 

 

 

Solution for Question 02

2๋ฒˆ ๋ฌธ์ œ๋ฅผ ํ’€ ๋•Œ ์กฐ๊ธˆ ํ—ท๊ฐˆ๋ ธ๋˜ ์ ์ด ์žˆ์—ˆ๋Š”๋ฐ, ์ฃผ์–ด์ง„ ๋ฐฐ์—ด์—์„œ ๋ฉ”๋‰ด๊ฐ€ ์žˆ์„ ๋•Œ ๋ชจ๋“  ๋ฉ”๋‰ด์— ๋Œ€ํ•ด์„œ ์ค‘๋ณต ์ฃผ๋ฌธ๋œ ๋ฉ”๋‰ด๋ฅผ ํ† ๋Œ€๋กœ ์ฝ”์Šค ์š”๋ฆฌ๋ฅผ ์„ ์ •ํ–ˆ๋‹ค๋ฉด ๋ฌธ์ œ๋ฅผ ํ’€์ง€ ๋ชปํ–ˆ์„ ๊ฐ€๋Šฅ์„ฑ์ด ๋งค์šฐ ๋†’์Šต๋‹ˆ๋‹ค.

 

๋จผ์ € ์ฃผ์–ด์ง€๋Š” ๋ฉ”๋‰ด์—์„œ ๋‚˜์˜ฌ ์ˆ˜ ์žˆ๋Š” ์กฐํ•ฉ์„ ์žฌ๊ท€ ํ•จ์ˆ˜๋ฅผ ํ†ตํ•˜์—ฌ ๊ตฌํ•ด์ค๋‹ˆ๋‹ค. ์ด ๋•Œ ์กฐํ•ฉ์„ ๊ตฌํ•  ๋•Œ๋Š” A, B ์ฃผ๋ฌธ๊ณผ B, A ์ฃผ๋ฌธ์ด ์ค‘๋ณต๋˜์ง€ ์•Š๋„๋ก ์ฃผ์˜ํ•ด์•ผ ํ•˜๋ฉฐ. ์ด ์กฐํ•ฉ์„ ๊ตฌํ•˜๊ณ ๋‚˜์„œ ๊ฐ ์กฐํ•ฉ์˜ ๊ฐฏ์ˆ˜๋ฅผ ์„ธ๊ณ , ์ •๋ ฌํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค.

 

Java๋ฅผ ์‚ฌ์šฉํ•œ๋‹ค๋ฉด TreeSet์„ ์ด์šฉํ•˜์—ฌ ๋ณ„๋„์˜ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•˜์ง€ ์•Š๊ณ  ์•ŒํŒŒ๋ฒณ ์ˆœ์„œ๋ฅผ ๋ณด์žฅ ๋ฐ›์„ ์ˆ˜ ์žˆ๋Š” ๋ฉ”์†Œ๋“œ๋ฅผ ์‚ฌ์šฉํ•˜๋Š” ๊ฒƒ๋„ ์ข‹์€ ๋ฐฉ๋ฒ•์ผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๊ทธ๋Ÿฌ๋‚˜ ์ค‘๋ณต์˜ ์—ฌ๋ถ€๋ฅผ ํ™•์ธํ•˜๊ธฐ ์œ„ํ•ด์„œ ๊ฐ ์ฃผ๋ฌธ ์กฐํ•ฉ์„ ์ •๋ ฌํ•  ํ•„์š”๋Š” ์žˆ์Šต๋‹ˆ๋‹ค.

 

๊ฐ ์กฐํ•ฉ๋ณ„๋กœ ๊ฐฏ์ˆ˜๋ฅผ ์„ธ๊ณ , ์›ํ•˜๋Š” ์กฐํ•ฉ์˜ ๊ฐฏ์ˆ˜๋ฅผ ์ˆ˜์ง‘ํ•œ ๋‹ค์Œ, ์กฐํ•ฉ์˜ ๊ฐฏ์ˆ˜ ๋ชจ์Œ์—์„œ ๊ฐ€์žฅ ๋งŽ์ด ๋‚˜์˜จ ์ฃผ๋ฌธ ๊ฑด์œผ๋กœ ์ถœ๋ ฅํ•ด์ฃผ๋ฉด ์‰ฝ๊ฒŒ ํ’€ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

 

 

 

 

Question 03. ์ˆœ์œ„ ๊ฒ€์ƒ‰

๋ฌธ์ œ ์›๋ฌธ: (https://programmers.co.kr/learn/courses/30/lessons/72412)

 

[๋ณธ ๋ฌธ์ œ๋Š” ์ •ํ™•์„ฑ๊ณผ ํšจ์œจ์„ฑ ํ…Œ์ŠคํŠธ ๊ฐ๊ฐ ์ ์ˆ˜๊ฐ€ ์žˆ๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.]

 

์นด์นด์˜ค๋Š” ํ•˜๋ฐ˜๊ธฐ ๊ฒฝ๋ ฅ ๊ฐœ๋ฐœ์ž ๊ณต๊ฐœ์ฑ„์šฉ์„ ์ง„ํ–‰ ์ค‘์— ์žˆ์œผ๋ฉฐ ํ˜„์žฌ ์ง€์›์„œ ์ ‘์ˆ˜์™€ ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ๊ฐ€ ์ข…๋ฃŒ๋˜์—ˆ์Šต๋‹ˆ๋‹ค. ์ด๋ฒˆ ์ฑ„์šฉ์—์„œ ์ง€์›์ž๋Š” ์ง€์›์„œ ์ž‘์„ฑ ์‹œ ์•„๋ž˜์™€ ๊ฐ™์ด 4๊ฐ€์ง€ ํ•ญ๋ชฉ์„ ๋ฐ˜๋“œ์‹œ ์„ ํƒํ•˜๋„๋ก ํ•˜์˜€์Šต๋‹ˆ๋‹ค.

 

  • ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ ์ฐธ์—ฌ ๊ฐœ๋ฐœ ์–ธ์–ด ํ•ญ๋ชฉ์— cpp, java, python ์ค‘ ํ•˜๋‚˜๋ฅผ ์„ ํƒํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.
  • ์ง€์› ์ง๊ตฐ ํ•ญ๋ชฉ์— backend์™€ frontend ์ค‘ ํ•˜๋‚˜๋ฅผ ์„ ํƒํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.
  • ์ง€์› ๊ฒฝ๋ ฅ ๊ตฌ๋ถ„ ํ•ญ๋ชฉ์— junior์™€ senior ์ค‘ ํ•˜๋‚˜๋ฅผ ์„ ํƒํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.
  • ์„ ํ˜ธํ•˜๋Š” ์†Œ์šธํ‘ธ๋“œ๋กœ chicken๊ณผ pizza ์ค‘ ํ•˜๋‚˜๋ฅผ ์„ ํƒํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.

 

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


์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ์— java๋กœ ์ฐธ์—ฌํ–ˆ์œผ๋ฉฐ, backend ์ง๊ตฐ์„ ์„ ํƒํ–ˆ๊ณ , junior ๊ฒฝ๋ ฅ์ด๋ฉด์„œ, ์†Œ์šธํ‘ธ๋“œ๋กœ pizza๋ฅผ ์„ ํƒํ•œ ์‚ฌ๋žŒ ์ค‘ ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ ์ ์ˆ˜๋ฅผ 50์  ์ด์ƒ ๋ฐ›์€ ์ง€์›์ž๋Š” ๋ช‡ ๋ช…์ธ๊ฐ€?

 

์œ„์™€ ๊ฐ™์€ ์กฐ๊ฑด์„ ๋ฐ”ํƒ•์œผ๋กœ any ์–ธ์–ด, any ์ง๊ตฐ, any ๊ฒฝ๋ ฅ, any ์†Œ์šธ ํ‘ธ๋“œ์˜ ์กฐ๊ฑด ๋“ฑ์œผ๋กœ ์ผ€์ด์Šค๋ฅผ ๊ตฌ๋ถ„ํ•œ๋‹ค๊ณ  ํ–ˆ์„ ๋•Œ ์ด์— ํ•ด๋‹นํ•˜๋Š” ์‚ฌ๋žŒ๋“ค์˜ ์ˆซ์ž๋ฅผ ์ˆœ์„œ๋Œ€๋กœ ๋ฐฐ์—ด์— ๋‹ด์•„ ๋ฐ˜ํ™˜ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๊ตฌํ˜„ํ•˜๋Š” ๋ฌธ์ œ์˜€์Šต๋‹ˆ๋‹ค.

 

 

 

Solution for Question 03

๋“œ๋””์–ด ๋‚˜์™”์Šต๋‹ˆ๋‹ค. ์นด์นด์˜ค ๋ฌธ์ œ์˜ ๋ฒฝ, ํšจ์œจ์„ฑ ํ…Œ์ŠคํŠธ ๋ฌธ์ œ,

์ €๋„ ์ด ๋ฌธ์ œ๋ฅผ ์ฒ˜์Œ ์ ‘ํ–ˆ์„ ๋•Œ๋Š” ๊ฐ ์ฟผ๋ฆฌ๋ฅผ ํŒŒ์‹ฑํ•˜์—ฌ ํ•ด๋‹นํ•˜๋Š” ๋ฐ์ดํ„ฐ์™€ ์ผ์น˜ํ•˜๋Š” ๋ถ€๋ถ„์ด ์žˆ๋‹ค๋ฉด ์ด๋ฅผ ๋ฐ˜ํ™˜ํ•˜๋„๋ก ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๊ตฌํ˜„ํ–ˆ์ง€๋งŒ ํ˜ธ๋ฝํ˜ธ๋ฝํ•˜๊ฒŒ ๋„˜์–ด๊ฐ€์ง€ ์•Š์•˜์Šต๋‹ˆ๋‹ค. ๊ทธ๋ž˜์„œ ํ•ด์„ค์„ ์กฐ๊ธˆ ์ฐธ๊ณ ํ•ด Query์— ํ•ด๋‹นํ•˜๋Š” ๋ชจ๋“  ์กฐํ•ฉ์„ ๊ตฌํ•˜์—ฌ ๊ทธ ์กฐํ•ฉ์— ํฌํ•จ๋˜๋Š” ๋ฐ์ดํ„ฐ๊ฐ€ ์žˆ๋Š”์ง€๋ฅผ ๋ณธ ๋‹ค์Œ ๊ตฌํ˜„ํ•˜์—ฌ ์ž‘์„ฑํ•ด๋ดค์Šต๋‹ˆ๋‹ค.

 

๊ทธ๋Ÿฌ๋‚˜ ๊ธธ์ด๋กœ๋งŒ ๋ดค์„ ๋•Œ ์ฃผ์–ด์ง€๋Š” ๊ธธ์ด๊ฐ€ 100,000์ด ๋„˜๋Š” ์ƒํ™ฉ์—์„œ ํ•ด๋‹น ์กฐํ•ฉ์„ ๊ตฌํ•˜๊ณ , ๋ชจ๋“  Query๋ฅผ ๋น„๊ตํ•˜๋‹ˆ Java์—์„œ๋Š” ์ด ๋ฌธ์ œ์˜ ํšจ์œจ์„ฑ ํ…Œ์ŠคํŠธ๋ฅผ ํ†ต๊ณผํ•˜์ง€ ๋ชปํ–ˆ์Šต๋‹ˆ๋‹ค.

 

๋น„์Šทํ•œ ํ•ด์„ค๋กœ Python์—์„œ ๋ฌธ์ œ ํ’€์ด๋ฅผ ์‹œ๋„ํ•˜์˜€์„ ๋•Œ๋Š” ์ž˜ ํ†ต๊ณผ๊ฐ€ ๋˜์—ˆ์ง€๋งŒ Java์—์„œ ๋ฌธ์ œ ํ’€์ด๋ฅผ ์ง„ํ–‰ํ•  ๋•Œ๋งŒ ์œ ๋… ๊ฐ™์€ ํ•ด์„ค ํ’€์ด๋กœ ๋ฌธ์ œ๋ฅผ ํ†ต๊ณผํ•˜์ง€ ๋ชปํ–ˆ๋˜ ๊ฒƒ์€ ์นด์นด์˜ค ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ ๋ฌธ์ œ ํ’€์ด๋ฅผ ํ•˜๋ฉด์„œ ์ฒ˜์Œ ๊ฒช๋Š” ์ผ์ด์—ˆ์Šต๋‹ˆ๋‹ค. 

 

๊ฒฐ๊ตญ Java์—์„œ ๋ฌธ์ œํ’€์ด๊ฐ€ ์ž˜ ์ง„ํ–‰๋˜์ง€ ์•Š์•„ ์ฝ”๋“œ๊ฐ€ ์กฐ๊ธˆ ์ง€์ €๋ถ„ํ•˜๋”๋ผ๋„ Java์—์„œ ๊ทธ๋‚˜๋งˆ ๋น ๋ฅธ ์ž๋ฃŒ๊ตฌ์กฐ์ธ Map์„ ์‚ฌ์šฉํ•˜์—ฌ ๋ฌธ์ œ ํ’€์ด๋ฅผ ์ง„ํ–‰ํ•ด๋ดค์Šต๋‹ˆ๋‹ค.

 

Map์„ ์ด์šฉํ•˜์—ฌ ์–ธ์–ด๋ฅผ ๋งจ ์œ„์˜ ๋ฃจํŠธ๋กœ ์‚ผ๊ณ , ์–ธ์–ด -> ์ง๊ตฐ -> ๊ฒฝ๋ ฅ -> ์†Œ์šธ ํ‘ธ๋“œ๋ผ๋Š” ํŠธ๋ฆฌ์˜ ๊ตฌ์กฐ๋ฅผ ๊ทธ๋ฆฌ๊ณ , ์•„๊นŒ ์œ„์—์„œ ๋งŒ๋“  ์กฐํ•ฉ์„ 4์ค‘ Map์„ ์ด์šฉํ•˜์—ฌ ํ•˜๋“œ ์ฝ”๋”ฉํ•œ ๊ตฌํ˜„์ฒด์ž…๋‹ˆ๋‹ค. ํ’€์ดํ•˜๊ณ  ๋‚˜์„œ ์ด๋Ÿฐ ํ’€์ด๋ฅผ ์˜ฌ๋ฆฌ๋Š” ๊ฒŒ ๊ฐœ์ธ์ ์œผ๋กœ ๋ฏผ๋งํ•œ ๋ถ€๋ถ„๋„ ์—†์ง€ ์•Š์•„ ์žˆ์—ˆ์ง€๋งŒ ํšจ์œจ์„ฑ ํ…Œ์ŠคํŠธ๋ฅผ ์™„๋ฒฝํ•˜๊ฒŒ ํ†ต๊ณผํ•  ์ˆ˜ ์žˆ๋Š” ๋ฐฉ๋ฒ•์œผ๋กœ ์ด ๋ฐฉ๋ฒ• ๋ฐ–์—๋Š” ๋„์ €ํžˆ ์ƒ๊ฐํ•ด๋‚ด์ง€ ๋ชปํ–ˆ์Šต๋‹ˆ๋‹ค. ๊ฐœ์ธ์ ์œผ๋กœ ์•„์‰ฌ์› ๋˜ ๋ฌธ์ œ์ด๊ธฐ๋„ ํ–ˆ์Šต๋‹ˆ๋‹ค.

 

 

 

 

Question 04. ํ•ฉ์Šน ํƒ์‹œ ์š”๊ธˆ

๋ฌธ์ œ ์›๋ฌธ: (https://programmers.co.kr/learn/courses/30/lessons/72413)

 

๋ฐค๋Šฆ๊ฒŒ ๊ท€๊ฐ€ํ•  ๋•Œ ์•ˆ์ „์„ ์œ„ํ•ด ํ•ญ์ƒ ํƒ์‹œ๋ฅผ ์ด์šฉํ•˜๋˜ ๋ฌด์ง€๋Š” ์ตœ๊ทผ ์•ผ๊ทผ์ด ์žฆ์•„์ ธ ํƒ์‹œ๋ฅผ ๋” ๋งŽ์ด ์ด์šฉํ•˜๊ฒŒ ๋˜์–ด ํƒ์‹œ๋น„๋ฅผ ์•„๋‚„ ์ˆ˜ ์žˆ๋Š” ๋ฐฉ๋ฒ•์„ ๊ณ ๋ฏผํ•˜๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. “๋ฌด์ง€”๋Š” ์ž์‹ ์ด ํƒ์‹œ๋ฅผ ์ด์šฉํ•  ๋•Œ ๋™๋ฃŒ์ธ ์–ดํ”ผ์น˜ ์—ญ์‹œ ์ž์‹ ๊ณผ ๋น„์Šทํ•œ ๋ฐฉํ–ฅ์œผ๋กœ ๊ฐ€๋Š” ํƒ์‹œ๋ฅผ ์ข…์ข… ์ด์šฉํ•˜๋Š” ๊ฒƒ์„ ์•Œ๊ฒŒ ๋˜์—ˆ์Šต๋‹ˆ๋‹ค. “๋ฌด์ง€”๋Š” “์–ดํ”ผ์น˜”์™€ ๊ท€๊ฐ€ ๋ฐฉํ–ฅ์ด ๋น„์Šทํ•˜์—ฌ ํƒ์‹œ ํ•ฉ์Šน์„ ์ ์ ˆํžˆ ์ด์šฉํ•˜๋ฉด ํƒ์‹œ์š”๊ธˆ์„ ์–ผ๋งˆ๋‚˜ ์•„๋‚„ ์ˆ˜ ์žˆ์„์ง€ ๊ณ„์‚ฐํ•ด ๋ณด๊ณ  “์–ดํ”ผ์น˜”์—๊ฒŒ ํ•ฉ์Šน์„ ์ œ์•ˆํ•ด ๋ณด๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

 

์ด๋Ÿฌํ•œ ํƒ์‹œ ๋…ธ์„ ๊ณผ ์˜ˆ์ƒ ์š”๊ธˆ์„ ์ฃผ์–ด์ค„ ๋•Œ ์ตœ์ € ์˜ˆ์ƒ ํƒ์‹œ ์š”๊ธˆ์„ ๊ณ„์‚ฐํ•ด ๋ฐ˜ํ™˜ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ž‘์„ฑํ•˜๋Š” ๋ฌธ์ œ์˜€์Šต๋‹ˆ๋‹ค.

 

 

 

Solution for Question 04

๋‚˜๋ฆ„ ์žฌ๋ฏธ์žˆ๊ฒŒ ํ’€์—ˆ๋˜ ๋ฌธ์ œ๋ผ๊ณ  ์ƒ๊ฐํ•ฉ๋‹ˆ๋‹ค. ๊ฐ€๋” ์ฐจ์—†์ด ์—ฌํ–‰์„ ํ•˜๊ฑฐ๋‚˜ ๋ˆ„๊ตฌ์™€ ๋™ํ–‰์„ ํ–ˆ์„ ๋•Œ ์ด๋Ÿฐ ๊ฒฝ๋กœ๋กœ ์ค‘๊ฐ„์— ์„ธ์›Œ์ฃผ๊ณ , ํƒ์‹œ ์š”๊ธˆ์„ ์–ด๋–ป๊ฒŒ ์ตœ์†Œ๋กœ ์ค„์ผ ์ˆ˜ ์žˆ์„์ง€ ์•Œ๋ ค์ค€๋‹ค๋ฉด ์ •๋ง ์ข‹๊ฒ ๋‹ค๊ณ  ์ƒ๊ฐ์„ ํ–ˆ๊ธฐ๋„ ํ•œ ๋ฌธ์ œ์˜€๋„ค์š”.

 

์ด๋ ‡๊ฒŒ ํƒ์‹œ์˜ ์ตœ์ € ์š”๊ธˆ์„ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ๋Š” ์ตœ์†Œ ๊ฒฝ๋กœ๋ฅผ ๊ตฌํ•ด์„œ ๋น ๋ฅด๊ฒŒ ์ด๋™ํ•˜๋Š” ๊ฒƒ๊ณผ ๊ฐ™๊ธฐ ๋•Œ๋ฌธ์— ์ด๋Ÿฐ ์ข…๋ฅ˜์˜ ๋ฌธ์ œ๋Š” ๋‹ค์ต์ŠคํŠธ๋ผ(Dijkstra) ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ด์šฉํ•˜์—ฌ ์‰ฝ๊ฒŒ ๊ตฌํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋งŒ์•ฝ ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ๋Œ€ํ•ด ์–ด๋ ค์šฐ์…จ๋˜ ๋ถ„๋“ค์ด๋ผ๋ฉด ์ด๋ฒˆ ๊ธฐํšŒ์— ๋ฐฐ์›Œ๋ณด๊ณ  ์ž˜ ์‚ฌ์šฉํ•ด๋ณด์‹œ๋ฉด ์ข‹์„ ๊ฒƒ ๊ฐ™๋„ค์š”.

 

๋‘ ์‚ฌ๋žŒ์ด ๋„์ฐฉํ•˜๋Š” ์ง€์ ์„ ๊ฐ๊ฐ ์ฃผ์–ด์ง€๊ณ , ๊ทธ๊ฒƒ์— ํ•ด๋‹นํ•˜๋Š” ์š”๊ธˆ์ด ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ A ์ง€์ ์— ๋„์ฐฉํ–ˆ์„ ๋•Œ ์ตœ์†Œ ๋น„์šฉ๊ณผ B ์ง€์ ์—์„œ ๋„์ฐฉํ–ˆ์„ ๋•Œ์˜ ์ตœ์†Œ ๋น„์šฉ์„ ๊ทธ๋ž˜ํ”„๋ฅผ ๊ตฌํ˜„ํ•˜์—ฌ ์ €์žฅํ•œ ๋‹ค์Œ, ์šฐ์„  ์ˆœ์œ„ ํ๋ฅผ ์ด์šฉํ•ฉ๋‹ˆ๋‹ค.

 

์ด ๋•Œ ์šฐ์„  ์ˆœ์œ„ ํ๋ฅผ ์ด์šฉํ•  ๋•Œ๋Š” ๋น„์šฉ์ด ์ตœ์†Œ์ธ ๋ถ€๋ถ„์„ ์šฐ์„ ์œผ๋กœ ๋Œ๊ฒŒํ•ฉ๋‹ˆ๋‹ค. ์ง€์ ์ด ๋‘ ๊ณณ์ด ์žˆ๊ธฐ ๋•Œ๋ฌธ์— A ์ง€์ ์—์„œ ์ตœ์†Œ์ผ ๋•Œ B ์ง€์ ์„ ์ˆœํšŒ, B ์ง€์ ์—์„œ ์ตœ์†Œ์ผ ๋•Œ A ์ง€์  ์ˆœํšŒ๋ฅผ ํ•˜์—ฌ ์ตœ์†Œ ๋น„์šฉ์„ ๊ตฌํ•˜๋ฉด ์‰ฝ๊ฒŒ ํ’€ ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

 

๊ณต์‹ ํ•ด์„ค์—์„œ๋Š” Floyd-Warshal ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•ด์„œ๋„ ํ’€ ์ˆ˜ ์žˆ๋‹ค๊ณ  ๋‚˜์™€ ์žˆ๋Š”๋ฐ, ์ €๋„ ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ๋Œ€ํ•ด์„œ๋Š” ์ž˜ ๋ชจ๋ฅด๊ฒ ์–ด์„œ ๊ฐœ์ธ์ ์œผ๋กœ ๊ณต๋ถ€ํ•ด๋ณด๊ณ  ๊ธฐํšŒ๊ฐ€ ๋œ๋‹ค๋ฉด ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ ํ•œ ๋ฒˆ ์žฌํ’€์ดํ•ด๋ณด๋Š” ๊ฒƒ๋„ ์ข‹์„ ๊ฒƒ ๊ฐ™๋„ค์š”.

 

 

 

 

Question 05. ๊ด‘๊ณ  ์‚ฝ์ž…

๋ฌธ์ œ ์›๋ฌธ: (https://programmers.co.kr/learn/courses/30/lessons/72414)

 

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

 

 

 

 

Solution for Question 05

์ด ๋ฌธ์ œ๋„ ๋‚˜๋ฆ„ ํŠน์ดํ•œ ๋ฌธ์ œ์˜€์ง€๋งŒ YouTube๋ฅผ ์ฆ๊ฒจ๋ณด๋Š” ์ €์˜ ์ž…์žฅ์—์„œ ๊ทธ๋“ค์ด ๊ด‘๊ณ ๋ฅผ ์ด๋ ‡๊ฒŒ๋„ ์‚ฝ์ž…ํ•  ์ˆ˜ ์žˆ๊ฒ ๊ตฌ๋‚˜ ๋ผ๋Š” ์ƒ๊ฐ์„ ํ•˜๋ฉฐ ํฅ๋ฏธ๋ฅผ ๊ฐ€์ง€๊ณ  ๋„์ „ํ•ด๋ณธ ๋ฌธ์ œ์˜€์Šต๋‹ˆ๋‹ค. ์ฒ˜์Œ ์ ‘๊ทผํ–ˆ์„ ๋•Œ๋Š” ์‹œ๊ฐ„ ๋ฐ์ดํ„ฐ๋ฅผ Date ๊ฐ์ฒด์— ๋งž์ถฐ ๋ฐ”๊พธ์–ด ์ด๋“ค์˜ ์ค‘๊ฐ„ ์‹œ๊ฐ„์„ ์ฒดํฌํ•˜๋ฉด ๋œ๋‹ค๊ณ  ์ƒ๊ฐํ–ˆ์ง€๋งŒ ํ•ด๋‹น ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์ƒ๊ฐ๋ณด๋‹ค ์ •ํ™•ํ•˜์ง€ ๋ชปํ–ˆ์Šต๋‹ˆ๋‹ค.

 

๋ฌธ์ œ์˜ ํ•ด์„ค์—์„œ ์ฃผ์–ด์ง„ ์‹œ๊ฐ„์˜ ์ตœ๋Œ€ ๊ธธ์ด๋ฅผ ๋ณด๊ณ  ์•ฝ๊ฐ„์˜ ํžŒํŠธ๋ฅผ ์–ป์„ ์ˆ˜ ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค. ์ตœ๋Œ€ 100์‹œ๊ฐ„์œผ๋กœ ์ดฌ์˜๋œ ๋™์˜์ƒ์ด๊ธฐ ๋•Œ๋ฌธ์— ์ด๋ฅผ ์ดˆ๋กœ ๋ฐ”๊ฟ”์„œ ๊ณ„์‚ฐํ•˜๋ฉด 100 * 60 * 60 = 360000์ดˆ์ด๋ฉฐ ์ด๋Š” ๋ฐฐ์—ด๋กœ๋„ ์ถฉ๋ถ„ํžˆ ๊ทธ ๊ณต๊ฐ„์„ ํ• ๋‹นํ•ด์„œ ํ’€ ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ๋ผ๊ณ  ์ƒ๊ฐํ–ˆ์Šต๋‹ˆ๋‹ค. 

 

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

 

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

 

๊ทธ๋Ÿฌ๊ณ  ๋‚œ ๋’ค ๋ฐฐ์—ด์— ํ•ด๋‹นํ•˜๋Š” ์ธ๋ฑ์Šค ๊ตฌ๊ฐ„์„ ์‹œ๊ฐ„๋Œ€๋กœ ๋ฐ”๊ฟ”์ฃผ๋ฉด ๋ฌธ์ œ๋ฅผ ํ’€ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

 

 

 

 

Question 06. ์นด๋“œ ์ง ๋งž์ถ”๊ธฐ

๋ฌธ์ œ ์›๋ฌธ: (https://programmers.co.kr/learn/courses/30/lessons/72415)

 

๊ฒŒ์ž„ ๊ฐœ๋ฐœ์ž์ธ ๋ฒ ๋กœ๋‹ˆ๋Š” ๊ฐœ๋ฐœ ์—ฐ์Šต์„ ์œ„ํ•ด ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ฐ„๋‹จํ•œ ์นด๋“œ ์ง๋งž์ถ”๊ธฐ ๋ณด๋“œ ๊ฒŒ์ž„์„ ๊ฐœ๋ฐœํ•ด ๋ณด๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.
๊ฒŒ์ž„์ด ์‹œ์ž‘๋˜๋ฉด ํ™”๋ฉด์—๋Š” ์นด๋“œ 16์žฅ์ด ๋’ท๋ฉด์„ ์œ„๋กœํ•˜์—ฌ 4 x 4 ํฌ๊ธฐ์˜ ๊ฒฉ์ž ํ˜•ํƒœ๋กœ ํ‘œ์‹œ๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค. ๊ฐ ์นด๋“œ์˜ ์•ž๋ฉด์—๋Š” ์นด์นด์˜คํ”„๋ Œ์ฆˆ ์บ๋ฆญํ„ฐ ๊ทธ๋ฆผ์ด ๊ทธ๋ ค์ ธ ์žˆ์œผ๋ฉฐ, 8๊ฐ€์ง€์˜ ์บ๋ฆญํ„ฐ ๊ทธ๋ฆผ์ด ๊ทธ๋ ค์ง„ ์นด๋“œ๊ฐ€ ๊ฐ๊ธฐ 2์žฅ์”ฉ ํ™”๋ฉด์— ๋ฌด์ž‘์œ„๋กœ ๋ฐฐ์น˜๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค.
์œ ์ €๊ฐ€ ์นด๋“œ๋ฅผ 2์žฅ ์„ ํƒํ•˜์—ฌ ์•ž๋ฉด์œผ๋กœ ๋’ค์ง‘์—ˆ์„ ๋•Œ ๊ฐ™์€ ๊ทธ๋ฆผ์ด ๊ทธ๋ ค์ง„ ์นด๋“œ๋ฉด ํ•ด๋‹น ์นด๋“œ๋Š” ๊ฒŒ์ž„ ํ™”๋ฉด์—์„œ ์‚ฌ๋ผ์ง€๋ฉฐ, ๊ฐ™์€ ๊ทธ๋ฆผ์ด ์•„๋‹ˆ๋ผ๋ฉด ์›๋ž˜ ์ƒํƒœ๋กœ ๋’ท๋ฉด์ด ๋ณด์ด๋„๋ก ๋’ค์ง‘ํž™๋‹ˆ๋‹ค. ์ด์™€ ๊ฐ™์€ ๋ฐฉ๋ฒ•์œผ๋กœ ๋ชจ๋“  ์นด๋“œ๋ฅผ ํ™”๋ฉด์—์„œ ์‚ฌ๋ผ์ง€๊ฒŒ ํ•˜๋ฉด ๊ฒŒ์ž„์ด ์ข…๋ฃŒ๋ฉ๋‹ˆ๋‹ค.

 

์ด๋Ÿฌํ•œ ๊ฒŒ์ž„์—์„œ ๊ฒŒ์ž„ ํ•œํŒ์ด ์ฃผ์–ด์งˆ ๋•Œ ๋ชจ๋“  ์นด๋“œ๋ฅผ ์ œ๊ฑฐํ•˜๊ธฐ ์œ„ํ•œ ํ‚ค ์กฐ์ž‘ ํšŸ์ˆ˜์˜ ์ตœ์†Ÿ๊ฐ’์„ ๊ตฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๊ตฌํ˜„ํ•˜๋Š” ๋ฌธ์ œ์˜€์Šต๋‹ˆ๋‹ค.

 

 

 

Solution for Question 06

์นด์นด์˜ค ๊ฒŒ์ž„ ๋‚ด์ง€ ๋ณด๋“œ ๊ฒŒ์ž„์—์„œ ํ”ํžˆ ๋ณผ ์ˆ˜ ์žˆ๋Š” ๊ธฐ๋Šฅ์„ ๊ตฌํ˜„ํ•˜๋Š” ๋ฌธ์ œ์ธ๋ฐ, ๊ฐ€๋ น ๋น…์ฅฌ์—˜์ด๋‚˜ ์• ๋‹ˆํŒก ๋“ฑ์˜ ๊ฒŒ์ž„์„ ํ•ด๋ณด์…จ๋‹ค๋ฉด ๊ทธ์— ํ•ด๋‹นํ•˜๋Š” ์ตœ์†Œ ์›€์ง์ž„ ํšŸ์ˆ˜๋ฅผ ์‚ฌ์šฉ์ž๊ฒŒ์— ์ฃผ์–ด์ฃผ๊ณ , ๊ทธ๋งŒํผ ๋ชป์›€์ง์ด๋ฉด ๊ฒŒ์ž„์„ ์ข…๋ฃŒ์‹œํ‚ค๋Š” ์•„์ฃผ ์ž”์ธํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๊ธฐ๋„ ํ•œ๋ฐ์š”. ๊ฐœ์ธ์ ์œผ๋กœ ์ด ๋ฌธ์ œ๊ฐ€ ์ •๋ง ์–ด๋ ค์› ์Šต๋‹ˆ๋‹ค.

 

Board์˜ ์ขŒํ‘œ ์ง€์ ์„ ์ด์šฉํ•˜๋Š”๋ฐ, ๊ฒŒ๋‹ค๊ฐ€ ์—ฌ๊ธฐ์— ํ•ด๋‹นํ•˜๋Š” ์ตœ์†Œ ์›€์ง์ด๋Š” ํšŸ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๊ฒƒ์ด๊ธฐ ๋•Œ๋ฌธ์— ์œ„์˜ 4๋ฒˆ ๋ฌธ์ œ์ฒ˜๋Ÿผ ์šฐ์„  ์ˆœ์œ„ ํ๋ฅผ ์ด์šฉํ•˜์—ฌ ์ด๋™ ํšŸ์ˆ˜๊ฐ€ ๊ฐ€์žฅ ์ ์€ ๊ฒƒ์„ ๊ธฐ๋กํ•ด์„œ ํ’€ ์ˆ˜ ์žˆ๋Š” ๋ฐฉ๋ฒ•์ด ์žˆ์Šต๋‹ˆ๋‹ค. ์šฐ์„  ์ˆœ์œ„ ํ์—์„œ ๊ฐ€์žฅ ์ค‘์š”ํ•œ ๊ฒƒ์€ ์–ด๋–ค ๋ณ€์ˆ˜๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์šฐ์„  ์ˆœ์œ„๋ฅผ ๋งค๊ธฐ๋ƒ๋Š” ๊ฒƒ์ธ๋ฐ์š”. ์ด ๋•Œ๋Š” C++์˜ operator๋‚˜ Java์˜ Comparable ์ธํ„ฐํŽ˜์ด์Šค๋ฅผ ์ž˜ ๋‹ค๋ฃจ๋Š” ๊ฒƒ์ด ์ค‘์š”ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.

 

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

 

์—ฌ๊ธฐ์„œ ์ค‘์š”ํ•œ ์ ์€ ์—ฌ๋Ÿฌ ์กฐ๊ฑด์ด ์žˆ๋‹ค๋Š” ๊ฒƒ์ธ๋ฐ, ์นด๋“œ๊ฐ€ ๊ทผ์ฒ˜์— ์žˆ์ง€ ์•Š๋”๋ผ๋„ ์กฐํ•ฉํ‚ค(Ctrl)๋ฅผ ์ด์šฉํ•˜์—ฌ ์ด๋™์ด ๊ฐ€๋Šฅํ•˜๋‹ค๋Š” ์ ์„ ๊ณ ๋ คํ•ด์•ผํ•ฉ๋‹ˆ๋‹ค. 

 

 

 

 

Question 07. ๋งค์ถœ ์ตœ์†Œํ™”

๋ฌธ์ œ ์›๋ฌธ: (https://programmers.co.kr/learn/courses/30/lessons/72416)

 

์œ ํ†ต์ „๋ฌธํšŒ์‚ฌ ์นด์นด์˜ค์ƒ์‚ฌ์˜ ์˜ค๋„ˆ์ธ ์ œ์ด์ง€๋Š” ์ƒˆ๋กœ์šด ์‚ฌ์—… ์•„์ดํ…œ์„ ๊ตฌ์ƒํ•˜๊ธฐ ์œ„ํ•ด ์ „๋ฌธ๊ฒฝ์˜์ธ(CEO)์ธ ํ”„๋กœ๋„์—๊ฒŒ ํšŒ์‚ฌ์˜ ๊ฒฝ์˜์„ ๋ถ€ํƒํ•˜์˜€์Šต๋‹ˆ๋‹ค. ์นด์นด์˜ค์ƒ์‚ฌ๋Š” ์ง์›๋“ค์„ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ํŒ€ ๋‹จ์œ„๋กœ ์กฐ์ง์„ ๊ตฌ์„ฑํ•˜๊ณ  ์žˆ์œผ๋ฉฐ ์•„๋ž˜ ๊ทธ๋ฆผ์€ CEO๋ฅผ ํฌํ•จํ•˜์—ฌ 10๋ช…์˜ ์ง์›๊ณผ 4๊ฐœ์˜ ํŒ€์œผ๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ๋Š” ํšŒ์‚ฌ ์กฐ์ง๋„๋ฅผ ๋ณด์—ฌ์ฃผ๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค.

 

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

 

 

 

 

Solution for Question 07

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

 

์ž๋ฃŒ๋ฅผ ๊ตฌ์„ฑํ•  ๋•Œ ์ง์› ๋ฒˆํ˜ธ์™€ ํ•ด๋‹น ์ง์›์˜ ๋งค์ถœ์•ก์„ ๊ธฐ๋กํ•ด๋†“๊ณ , ๊ทธ ํ•˜์œ„ ์ง์›๋“ค์€ ๋ฐฐ์—ด์ด๋‚˜ ๋ฆฌ์ŠคํŠธ๋ฅผ ์ด์šฉํ•˜์—ฌ ๊ฐ™์€ ํด๋ž˜์Šค๋กœ ๋งž์ถฐ์ฃผ๋ฉด์„œ ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ ๊ธฐ๋ฒ•์„ ์ด์šฉํ•˜๋ฉด ์‰ฝ๊ฒŒ ํ’€ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

 

 

 

 

 

๋งˆ์น˜๋ฉฐ...

์—ฌ๊ธฐ๊นŒ์ง€ 2021 ์นด์นด์˜ค ์‹ ์ž… ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ๋ฌธ์ œ ํ’€์ด๋ฅผ ์ง„ํ–‰ํ•ด ๋ดค์Šต๋‹ˆ๋‹ค. 

 

ํŠน์ดํ•œ ๋ฌธ์ œ๋„ ํ•œ ๋ฌธ์ œ ์žˆ์—ˆ๊ณ , ๋ฌด์—‡๋ณด๋‹ค ์ตœ๊ทผ ๋“ค์–ด ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ ํ’€์ด๋ฅผ ๊พธ์ค€ํžˆ ์•ˆํ•œ ํƒ“์ธ์ง€ ํ‰์†Œ๋ณด๋‹ค ๋ฌธ์ œ ํ’€์ดํ•˜๋Š” ๋ฐ ๋‚œ์ด๋„๋„ ์‹œ๊ฐ„๋„ 2~3๋ฐฐ ์ •๋„ ๋บ๊ธด ๋“ฏํ•œ ๊ธฐ๋ถ„์ด์—ˆ์Šต๋‹ˆ๋‹ค. ์ข€ ๋” ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ๋Œ€ํ•œ ๋ฌธ์ œ ํ’€์ด์— ๋…ธ๋ ฅ์„ ๊ธฐ์šธ์—ฌ์•ผ๊ฒ ๋‹ค๋Š” ์ƒ๊ฐ์ด ๋“ค์—ˆ์Šต๋‹ˆ๋‹ค.

 

์ข‹์€ ์ ์ด ์žˆ์—ˆ๋‹ค๋ฉด ์ด๋ฒˆ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ ํ’€์ด์—์„œ ์‹ค์ƒํ™œ์—์„œ ์ž์ฃผ ์‚ฌ์šฉํ•˜๊ณ  ์žˆ๋Š” ๋ฌธ์ œ๋“ค์— ๋Œ€ํ•œ ํ•ด๊ฒฐ ๊ฒฝํ—˜์„ ๊ฐ€์งˆ ์ˆ˜ ์žˆ์—ˆ๋‹ค๋Š” ๊ฒƒ์— ๋งŒ์กฑ์„ ํ–ˆ๋˜ ๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค. ๊ทธ ๊ตฌํ˜„ ๊ณผ์ •์ด๋‚˜ ํ’€์ด๊ฐ€ ์ƒ๊ฐ๋ณด๋‹ค ๊ณ ํ†ต์Šค๋Ÿฌ์› ์ง€๋งŒ ๊ฐœ๋ฐœ์ž๋ผ๋Š” ์ง์—…์„ ํ•˜๋ฉด์„œ ํ‰์†Œ ๊ณ ๋ฏผํ–ˆ๋˜ ๋ฌธ์ œ๋“ค์ด๋‚˜ ์‚ฌ์šฉํ•˜๋Š” ๊ธฐ๋Šฅ๋“ค์— ๋Œ€ํ•ด ์ข€ ๋” ํƒ๊ตฌํ•ด๋ณด๊ณ  ์—ฐ๊ตฌํ•˜๋Š” ๊ธฐํšŒ๊ฐ€ ์ƒ๊ฒผ๋‹ค๋Š” ์ ์€ ์ •๋ง ์ข‹์•˜๋˜ ๊ฒƒ ๊ฐ™๋„ค์š”.

 

์•ž์œผ๋กœ๋„ ๊ณ„์† ๋ฌธ์ œ ํ’€์ด๋ฅผ ํ•ด๋ณผ ๊ณ„ํš์ด์ง€๋งŒ ์ ์  ๋ฌธ์ œ์˜ ๋‚œ์ด๋„๋ฅผ ๋ณด๋ฉฐ ํ•œ์ˆจ์ด ๋‚˜์˜ค๋Š” ๊ฒƒ์€ ์™œ ์ผ๊นŒ์š”? ใ… ใ… ..

 

 

 

 

 

์ฐธ๊ณ : 2021 ์นด์นด์˜ค ์‹ ์ž…๊ณต์ฑ„ 1์ฐจ ์˜จ๋ผ์ธ ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ for Tech developers ๋ฌธ์ œ ํ•ด์„ค

(https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/)

๋ฐ˜์‘ํ˜•
TAGS.

Tistory Comments