๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
Algorithm/์ธํ”„๋Ÿฐ(inflearn)

[ ๊ฐ•์˜ ํ›„๊ธฐ ] ์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œํ’€์ด(์ฝ”๋”ฉํ…Œ์ŠคํŠธ ๋Œ€๋น„) - ๊น€ํƒœ์› (๋‚ด๋ˆ๋‚ด์‚ฐ)

by YWTechIT 2021. 10. 15.
728x90

๐Ÿ“ [ ๊ฐ•์˜ ํ›„๊ธฐ ] ์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œํ’€์ด(์ฝ”๋”ฉํ…Œ์ŠคํŠธ ๋Œ€๋น„) - ๊น€ํƒœ์›

 

โœ๏ธ ์„œ๋ก 

ํ•™๋ถ€์‹œ์ ˆ JAVA๋ฅผ ์ž ๊น ๋ฐฐ์› ์ง€๋งŒ ํด๋ž˜์Šค๊ฐ€ ๋ญ๊ณ  ์ธ์Šคํ„ด์Šค๊ฐ€ ๋ญ”์ง€ ์ˆ˜์—…์„ ๋“ค์–ด๋„ ์ „ํ˜€ ๊ฐ์„ ์žก์ง€ ๋ชปํ•ด ์†์—์„œ ๋†”๋ฒ„๋ ธ๋‹ค. ๋Œ€ํ•™๊ต ์กธ์—… ํ›„ 2๋…„ 4๊ฐœ์›”์˜ ๊ตฐ ๋ณต๋ฌด๋ฅผ ๋งˆ์น˜๊ณ  ๋‚˜์„œ 5๊ฐœ์›” ๋’ค์ธ 20. 12. 22๋ถ€ํ„ฐ ์ทจ์—…์„ ํ•˜๊ฒ ๋‹ค๋Š” ๋‹ค์ง๊ณผ ํ•จ๊ป˜ ํ”„๋กœ๊ทธ๋ž˜๋ฐ ๊ด€๋ จ ๊ธฐ์–ต์ด ๋ชจ๋‘ ์‚ญ์ œ๋œ ์ฑ„ ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ๋ฅผ ์ค€๋น„ํ–ˆ๋‹ค. ๊ทธ๋กœ๋ถ€ํ„ฐ 3~4๊ฐœ์›”์ด ์ง€๋‚ฌ์„ ๋•Œ ํ”„๋ก ํŠธ์—”๋“œ๋กœ ๊ฐ€๋ ค๋ฉด ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ์˜ ์–ธ์–ด๋กœ๋Š” python ๋ณด๋‹ค ์ด์ œ๋ถ€ํ„ฐ ํ‰์ƒ ๋‹ฌ๊ณ  ์‚ด์•„์•ผ ํ•  javascript๋กœ ํ•ด์•ผ๊ฒ ๋‹ค๋Š” ๋งˆ์Œ์„ ๋จน์—ˆ๋‹ค. python์œผ๋กœ ๊ณต๋ถ€๋ฅผ ํ•˜๋ฉด์„œ 2~3๊ฐœ ์ •๋„ ์Šคํƒ€ํŠธ์—…์˜ ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ๋ฅผ ์น˜๋ €๋Š”๋ฐ ๋ชจ๋‘ python์€ ์ง€์›์ด ๋˜์ง€ ์•Š๊ณ  JS๋กœ๋งŒ ์‘์‹œ๊ฐ€ ๊ฐ€๋Šฅํ–ˆ๋‹ค. JS๋กœ ์ƒˆ๋กœ ์‹œ์ž‘ํ•  ๋•Œ python์—์„œ ์‚ฌ์šฉํ•˜๋˜ ๋ช‡๋ช‡์˜ ๋ฌธ๋ฒ•์€ JS์—์„œ ์ง€์›ํ•˜์ง€ ์•Š์•˜๋‹ค. ํŠนํžˆ, ๋ฐฐ์—ด์ด๋‚˜ ๋ฌธ์ž์—ด์˜ ๊ฐ’์„ ๋’ค์ง‘๋Š” [::-1]์€ ๋งŽ์ด ์‚ฌ์šฉํ–ˆ์—ˆ๋Š”๋ฐ JS๋Š” ์ง€์›์„ ํ•˜์ง€ ์•Š์•„์„œ ์•„์‰ฌ์› ๋‹ค.

 


โœ๏ธ ๋ณธ๋ก 

5๊ฐœ์›” ์ •๋„ ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ๋ฅผ ๋…ํ•™์œผ๋กœ ๊ณต๋ถ€ํ•˜๋‹ค ๋ณด๋‹ˆ ๋ง‰ํžˆ๋Š” ๋ถ€๋ถ„๋„ ๋งŽ์•˜๋‹ค. ์ด๋Ÿฐ ๋ฌธ์ œ๋Š” ์–ด๋–ป๊ฒŒ ๋…ผ๋ฆฌ์ ์œผ๋กœ ์ ‘๊ทผํ•ด์•ผ ํ•˜์ง€?๋ผ๋Š” ์ƒ๊ฐ์ด ๋งŽ์ด ๋“ค์—ˆ๊ณ , ๊ฒฐ๋ก ์ ์œผ๋กœ ๊ณ„์† ๊ฐ™์€ ๋‚œ์ด๋„์˜ ๋ฌธ์ œ๋งŒ ๊ณจ๋ผ ํ’€๊ณ  ์žˆ๋Š” ๋‚ด๊ฐ€ ์ •์ฒด๋˜์–ด ์žˆ๋Š” ๋“ฏํ•œ ๋Š๋‚Œ์„ ๋ฐ›์•˜๋‹ค. ๊ทธ๋ž˜์„œ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ฐ•์˜๋ฅผ ๋“ฃ๊ณ  ์‹ถ๋‹ค๋Š” ์ƒ๊ฐ์„ ํ–ˆ๊ณ  ๋ช‡๋ช‡์˜ ์‚ฌ์ดํŠธ๋ฅผ ์ฐพ์•„๋ดค์ง€๋งŒ ๋Œ€๋ถ€๋ถ„์˜ ๊ฐ•์˜๋Š” c++, python, java๋กœ๋งŒ ์ง„ํ–‰ํ–ˆ๋‹ค. (JS๋„ ํฌํ•จ์‹œ์ผœ์ฃผ์„ธ์š” ๐Ÿฅฒ ๐Ÿฅฒ ) ์šฐ์—ฐํžˆ ์ธํ”„๋Ÿฐ์—์„œ ๊ฐ•์˜๋ฅผ ์ฐพ์•„๋ณด๋Š”๋ฐ JS๋กœ ์ง„ํ–‰ํ•˜๋Š” ๊ฐ•์˜๊ฐ€ ์žˆ์—ˆ๋Š”๋ฐ ๊น€ํƒœ์› ์„ ์ƒ๋‹˜์˜ ์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œํ’€์ด(์ฝ”๋”ฉํ…Œ์ŠคํŠธ ๋Œ€๋น„)๋ผ๋Š” ๊ฐ•์˜์˜€๋‹ค. ๋ฌด๋ฃŒ๋Š” ์•„๋‹ˆ์—ˆ๊ณ  ๊ฐ€๊ฒฉ์€ ์•ฝ 6๋งŒ ์›์ธ๋ฐ ํ• ์ธ๋ฐ›์•„ ์น˜ํ‚จ 3๋ฒˆ๋งŒ ์ฐธ์œผ๋ฉด ๋˜๋Š” ๊ฐ€๊ฒฉ์ธ 4๋งŒ 8์ฒœ ์› ์ •๋„์— ๊ตฌ๋งคํ–ˆ๋‹ค. (4๋งŒ 8์ฒœ ์›์ด๋ฉด ๋‚˜๋งŒ์˜ ๋ฐฑ์ˆ˜ ํ™˜์œจ ์ ์šฉ ์‹œ 48๋งŒ ์›์ด๋‹ค. (๋ฐฑ์ˆ˜ ํ™˜์œจ = ๊ธฐ์กด ๊ธˆ์•ก * 10)) ์ดˆ๋ฐ˜์—๋Š” ๋ฐฑ์ค€์—์„œ ๋ช‡๋ช‡ ํ’€์–ด๋ณธ ๋ฌธ์ œ๋“ค์ด ๋‚˜์™€์„œ ํ’€ ๋งŒ ํ–ˆ๋Š”๋ฐ ๋‚˜์ค‘์—๋Š” ๋‚œ์ด๋„๊ฐ€ ์กฐ๊ธˆ์”ฉ ์˜ฌ๋ผ๊ฐ€์„œ ์–ด๋ ค์› ๋‹ค. ๊ฐ•์˜์—์„œ ๊ฐ€์žฅ ๋งˆ์Œ์— ๋“ค์—ˆ๋˜ ๋ถ€๋ถ„์€ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ๋Œ€๋žต์ ์ธ ๊ฐœ๋…๋งŒ ์•Œ๊ณ  ์‹ค์ œ ๋ฌธ์ œ์—๋Š” ์ ์šฉํ•˜์ง€ ๋ชปํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜๋“ค parametricSearch, twoPointer, slidingWindow, LIS, knapsack ๋“ฑ์„ ๋ฌธ์ œ๋ฅผ ํ†ตํ•ด ๋ฐฐ์šฐ๋‹ˆ๊นŒ ๊ฐœ๋…๊ณผ ์ดํ•ด๊ฐ€ ๋ฌด์ฒ™ ์ž˜๋๋‹ค. (์ด์ „์— ํ˜„๋Œ€์นด๋“œ ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ ๋ดค์„ ๋•Œ LIS๋ฅผ ์‚ฌ์šฉํ•˜๋Š” ๋ฌธ์ œ๊ฐ€ ๋‚˜์™”๋Š”๋ฐ ๊ทธ๋•Œ๋Š” ๊ตฌํ˜„ํ•  ์ค„ ๋ชฐ๋ผ ๋‚ด ๋งˆ์Œ์†์œผ๋กœ๋งŒ ํ’€์—ˆ๋‹ค..) ์—ฌํ•˜ํŠผ ํ‰์ผ ํ•˜๋ฃจ์— 2~3๋ฌธ์ œ์”ฉ ์ด 84๋ฌธ์ œ๋ฅผ ๊พธ์ค€ํžˆ ํ‘ผ ๊ฒฐ๊ณผ 2๊ฐœ์›”์ •๋„ ๊ฑธ๋ ธ๋‹ค. (๋ฐฑ์ค€์—์„œ 227๋ฌธ์ œ๋ฅผ ํ’€์—ˆ๋Š”๋ฐ ์ด๊ฒƒ๊นŒ์ง€ ํ•ฉํ•˜๋ฉด ์•ฝ 300๋ฌธ์ œ ๋„˜๊ฒŒ ํ’€์—ˆ๋‹ค.) ๋ฌด์—‡๋ณด๋‹ค ๋ฌธ์ œ๋ฅผ ํ’€๊ณ  ๋‚˜์„œ ๊ทธ๋ƒฅ ๋„˜์–ด๊ฐ€๋Š” ๊ฒƒ์ด ์•„๋‹ˆ๋ผ ๋ธ”๋กœ๊ทธ์— ๋ฌธ์ œ๋“ค์„ ํฌ์ŠคํŒ…ํ•˜๊ณ  ๋…ธ์…˜์—๋„ ๊ด€๋ จ๋œ ๋‚ด์šฉ๋“ค์„ ๊ธฐ๋กํ•˜๋‹ˆ๊นŒ ๊ธฐ์–ต์— ์ž˜ ๋‚จ๋Š”๋‹ค. ๊ทธ๋ฆฌ๊ณ  ์–ด์ฉŒ๋‹ค ๋ณด๋‹ˆ ์•จ๋ฆฌ์Šค SW ์—”์ง€๋‹ˆ์–ด ํŠธ๋ž™์—๋„ ์šด์ด ์ข‹๊ฒŒ ํ•ฉ๊ฒฉํ–ˆ๋Š”๋ฐ ์ด ๊ฐ•์˜๋ฅผ ๋“ค์—ˆ๊ธฐ ๋•Œ๋ฌธ์—๋ผ๋Š” ์ƒ๊ฐ์ด ๊ฐ•ํ•˜๊ฒŒ ๋‚จ๋Š”๋‹ค.


โœ๏ธ ๊ฒฐ๋ก 

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

 

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

๋ฐ˜์‘ํ˜•

๋Œ“๊ธ€