๐ [ ๊ฐ์ ํ๊ธฐ ] ์๋ฐ์คํฌ๋ฆฝํธ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํ์ด(์ฝ๋ฉํ ์คํธ ๋๋น) - ๊นํ์
โ๏ธ ์๋ก
ํ๋ถ์์ 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` ๊ธฐ์ด์ ์ธ ๋ฌธ๋ฒ์ ๋ฐฐ์ฐ๊ณ ์ถ์ผ์ ๋ถ)์๊ฒ๋ ๊ผญ ์ถ์ฒํด์ฃผ๊ณ ์ถ์ ๊ฐ์๋ค. (๋๋ฌด ์ข๋ค๊ณ ๋ง ์์ฑํด์ ์ธํ๋ฐ์์ ํ์๋ฐ๊ณ ์์ฑํ ๊ธ ๊ฐ์๋ฐ ์ง๊ทนํ ๋ด ๋ ๋ด์ฐ์ด๋ค) ์ง ์ข์ ๊ฐ์, ์ง๋ฌธ๊ธ์ ๋จ๊ธฐ๋ฉด ๋ฐ๋ก๋ฐ๋ก ๋๋ตํด์ฃผ์๋ ๊นํ์ ์ ์๋๊ป ๊ฐ์ฌ์ ๋ง์์ ์ ํ๊ณ ์ถ๋ค. (์ปจํธ๋ด ~ ์ํ ์ค!๋ ๋จธ๋ฆฟ์์ ์๊พธ ๋จ๋๋ค.)
๋์ผ๋ก ๊ฐ์ธ์ ์ธ ๊ฒฌํด๋ก ์๋ง์ ์๊ณ ๋ฆฌ์ฆ ๊ฐ์๋ฅผ ๋ฃ๋๋ค๊ณ ํด๋ ์ง์ ๋ค์ํ ๋ฌธ์ ๋ฅผ ํ์ด๋ด์ผ ํ๋ค๊ณ ์๊ฐํ๋ค. ๋์๊ฒ๋ ์์ง ๋์ด์ผ ํ ์ฐ์ด ๋ง๋ค. ํ์ง๋ง ์ฌ๊ธฐ์์ ํฌ๊ธฐํ์ง ์๊ณ ์ ์ฐจ ์งํฅ์ ์ธ ์ฌ๊ณ , ๋ ผ๋ฆฌ์ ์ธ ์ฌ๊ณ ์ ๊ฐ์ ์์ง ์๊ณ ๋งค์ผ๋งค์ผ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ๋ฅผ ํ๋ฉด ๋๊ธฐ์ ์ฝ๋ฉ ํ ์คํธ๋ ๊ฑฐ๋ฌํ๊ฒ ํต๊ณผํ ์ ์์ ๊ฑฐ๋ผ ๋ฏฟ๋๋ค.
๋๊ธ