DataStructure์ ์๊ณ ๋ฆฌ์ฆ์ ์ด๋ป๊ฒ ๊ณต๋ถํด์ผ ํ ๊น..
์ฒ์์ ํ๋ ๊ฒ์ด๋ผ๋ฉด ๋ฐฐ์ด -> ์คํ -> ํ -> ๋ฆฌ์คํธ -> ํธ๋ฆฌ ์์๋ก ๋๊ฐ๋ ๊ฒ์ด ์ข์๋ฏ. ์ ๋ ฌ๊ณผ ํด์ฑ ์ดํ ๋ค์ ๊บผ๋ ์๋ง ์ด๋ฒ๋ฌ๋ด๋ก ๋๊ฐ๊ธฐ ํ๋ค๊ฒ ๊ฐ์๋ฐ. ํธ๋ฆฌ๋ ๊ทธ๋ํ๊น์ง๋ง ๋ชฉํ๋ก ์ก์๋ ์ฑ๊ณต์ด๋ผ๊ณ ์๊ฐํจ.
๊ทธ๋ฆฌ๊ณ , ์๋ฃ๊ตฌ์กฐ ๋ ํฌํธ ์ ๋ฐฐ๋ค์ด ํ ๊ฒ์ด ์์ผ๋๊น, ๊ทธ ๋ฌธ์ ๋ค ๊ตฌํ์ ๋ชฉํ๋ก ์ก์๋ ์ข๊ณ . (์ํ๋ค๋ฉด ๋ณด๋ด์ค๊ป.) ex) ์คํ:์คํ ๊ตฌํ, postfix ์ ๊ตฌํ, ๊ณ์ฐ๊ธฐ ๊ตฌํ. ํ:ํ ๊ตฌํ. ๋ฆฌ์คํธ:๋คํญ์ ๋ง,๋บ์
& ๊ณฑ์
๊ตฌํ (polynomial) ํธ๋ฆฌ:2์งํธ๋ฆฌ๊ตฌํ
์๋ฃ๊ตฌ์กฐ๋ ์ผ๋จ 1. ๊ฐ๊ฐ์ ์๋ฃ๊ตฌ์กฐ๋ค์ ํน์ง์ ์ดํดํ๊ณ . 2. ์ค์ ์ ๊ตฌํ๋ฒ์ ์ตํ๋ฉฐ (๋ญ.์์๋ collection library๋ค์ ์ ๊ณตํ๋ฏ๋ก ์ง์ ๊ตฌํํ ์ผ์ด ์ค์ด๋ค์๊ธด ํ์ง๋ง. ๊ทธ๋๋ ์ฌ์ ํ ๊ธฐ์ด๊ฐ ๋จ) 3. ํด๋น ๋ฌธ์ ์ํฉ์ ์ ์ ํ ์๋ฃ๊ตฌ์กฐ๋ฅผ ์ ํํ ์ ์๋ ๋์ ๋ค๋ฌ์ด์ผ ํจ. --์์ฒ
์ ๊ฐ ์๊ฐ์ปจ๋ฐ, ๊ต์ก์ ์ธ ๋ชฉ์ ์์๋, ์๋ฃ๊ตฌ์กฐ๋ ์๊ณ ๋ฆฌ์ฆ์ ์ฒ์ ๊ณต๋ถํ ๋๋ ์ฐ์ ์ ํน์ ์ธ์ด๋ก ๊ตฌํ๋ ๊ฒ์ ๋ณด์ง ์๋ ๊ฒ์ด ์ข์ ๊ฒฝ์ฐ๊ฐ ๋ง์ต๋๋ค -- ๋์ pseudo-code ๋ฑ์ผ๋ก ๊ทธ ๊ฐ๋
๊น์ง๋ง ์ดํดํ๋ ๊ฒ์ด์ฃ . ๊ทธ ์์ด๋์ด๋ฅผ Procedural(C, ์ด์
๋ธ๋ฆฌ์ด)์ด๋ Functional(LISP,Scheme,Haskel), OOP(Java,Smalltalk) ์ธ์ด ๋ฑ์ผ๋ก ์ง์ ๊ตฌํํด ๋ณด๋ ๊ฒ๋๋ค. ์ด ๋ค์์๋ ๋ค๋ฅธ ์ฌ๋(์ฑ
)์ ์ฝ๋์ ๋น๊ต๋ฅผ ํฉ๋๋ค. ์ด ๊ฒฝํ์ ์ ์ด์ ๋ฐํ ๋นํ ์ฌ๋์ ๊ท์คํ ๋ฐฐ์๊ณผ ๊นจ๋ฌ์์ ๊ธฐํ๋ฅผ ์์ ์
์
๋๋ค. ์ฐธ๊ณ ๋ก ์๊ณ ๋ฆฌ์ฆ ๊ต์ฌ๋ก๋ 10๋
์ ํ ๋ฒ ๋์ฌ๊น ๋ง๊นํ CLR(Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest)์ ์ ๊ทน ์ถ์ฒํฉ๋๋ค(์ด์ ํจ๊ป ํน์ ์ด์ ์ Jon Bentley์ Programming Pearls๋ ๊ฐ๋ ฅ ์ถ์ฒํฉ๋๋ค. ์ ์ธ๊ณ์ ์งฑ์งฑํ ํ๋ก๊ทธ๋๋จธ/์ ์ฐํ์๋ค์ด ํจ๊ป ๊ผฝ์ "์๋ํ ์ฑ
" ๋ฆฌ์คํธ์์ ๋ช ์๊ฐ๋ฝ ์์ ๋๋ ์ฑ
์
๋๋ค. ์๋ง ์ฐ๋ฆฌ ํ๊ต ๋์๊ด์ ์์ ๊ฒ์ธ๋ฐ, ์์ง ์ด ์ฑ
์ ๋ณธ ์ ์๋ ์ฌ๋์ ์ถํ๋๋ฆฝ๋๋ค. ์๋ง ๋ช ์ฃผ ๊ฐ์ ๊ฐ๋ ์์ ํ๋ฃจํ๋ฃจ๋ฅผ ๋ณด๋ด๊ฒ ๋ ๊ฒ๋๋ค.). ๋ง์ฝ ํจ๊ป ์คํฐ๋๋ฅผ ํ๋ค๋ฉด, ๊ฐ์ ๋์ผํ ์์ด๋์ด๋ฅผ (๊ฐ์ ์ธ์ด๋ก ํน์ ๋ค๋ฅธ ์ธ์ด๋ก) ์ด๋ป๊ฒ ๋ค๋ฅด๊ฒ ํํํ๋์ง๋ฅผ ์๋ก ๋น๊ตํด ๋ณด๋ฉด ๋ ๋ฐฐ์ฐ๋ ๊ฒ์ด ๋งค์ฐ ๋ง์ต๋๋ค. ์ฐ๋ฆฌ๊ฐ ์๋ฃ๊ตฌ์กฐ๋ ์๊ณ ๋ฆฌ์ฆ์ ๊ณต๋ถํ๋ ์ด์ ๋, ํน์ "์ค์ธ๊ณ์ ๋ฌธ์ "๋ฅผ ์ด๋ ํ "์ํ์ ์์ด๋์ด"๋ก ๋งคํ์ ์์ผ์ ํด๊ฒฐํ๋ ๊ฒ์ด ๊ฐ๋ฅํ๊ณ ๋ ํจ์จ์ ์ด๊ณ , ๋ ์ด๋ฅผ ์ปดํจํฐ์ ์ด๋ป๊ฒ ๊ตฌํํ๋ ๊ฒ์ด ๊ฐ๋ฅํ๊ณ ํจ์จ์ ์ธ์ง๋ฅผ ๋ฐ์ง๊ธฐ ์ํด์์ด๋ฉฐ, ์ด ๊ณผ์ ์ ์์ด ์ํ์ ๊ฐ๋
์ ํ๋ก๊ทธ๋๋ฐ ์ธ์ด๋ก ํํํด ๋ด๋ ๊ฒ์ ์์ฃผ ์ค์ํ ๋ฅ๋ ฅ์ด ๋ฉ๋๋ค. ๊ฐ๋ณ ์๊ณ ๋ฆฌ์ฆ์ ์นดํ๋ก๊ทธ๋ฅผ ์ดํด, ์๊ธฐํ๋ฉฐ ์ตํ๋ ๊ฒ๋ ์ค์ํ์ง๋ง ๋ ์ค์ํ ๊ฒ์ ์๊ณ ๋ฆฌ์ฆ์ ์๊ฐํด ๋ผ ์ ์๋ ๋ฅ๋ ฅ๊ณผ ์ด ์๊ณ ๋ฆฌ์ฆ์ ํจ์จ์ ๋น๊ตํ ์ ์๋ ๋ฅ๋ ฅ, ๊ทธ๋ฆฌ๊ณ ์ด๋ฅผ ํํํ ์ ์๋ ๋ฅ๋ ฅ์
๋๋ค.
์ฒซ๋ฒ์งธ๊ฐ ์ ๋๋ก ํ๋ จ๋์ง ๋ชปํ ์ฌ๋์ ์๊ณ ๋ฆฌ์ฆ ๋ชฉ๋ก์ ์คํ
๋ ์ค ํ์
์๋ง ๊ธธ๋ค์ฌ์ ธ ์์ด์ ๋ชจ๋ ๋ฌธ์ ๋ฅผ ์์ ์ด ๊ฐ์ง ์๊ณ ๋ฆฌ์ฆ ๋ชฉ๋ก์ ๋ผ์๋ง์ถ๋ ค๊ณ ํฉ๋๋ค. DesignPatterns๋ฅผ ์ ๋ชป ๊ณต๋ถํ ์ฌ๋๊ณผ ๋น์ทํฉ๋๋ค. ์ด ์ฌ๋๋ค์ ๋ง์น ๊ณผ๊ฑฐ ์ํ ์ ์์ ์์ญ๋ฒ์ ๊ณต๋ถํด์ ๋ฌธ์ ๋ฅผ ํ๋ ๋์ ธ์ฃผ๊ธฐ๋ง ํ๋ฉด, ์๊ฐํด๋ณด์ง๋ ์๊ณ ์์ ์ด ํ์๋ ๋ฌธ์ ๋ค์ ํจํด ์ค ๊ฐ์ฅ ๋น์ทํ ๊ฒ ํ๋๋ฅผ ๊ธฐ๊ณ์ , ๋ฌด์์์ ์ผ๋ก ํ์ด์ ๋ผ๋ "๋ฌธ์ ํ์ด๊ธฐ๊ณ"์ ๋น์ทํฉ๋๋ค. ๊ทธ๋ค์๊ฒ ๋์ค์ ๋ฌผ์ด๋ณด์ญ์์ค. "๋ ์ง๊ธ ๋ฌด์จ ๋ฌธ์ ํ๊ณ ์๋๊ฑฐ๋?" ์ด์ฌํ ์ฐ์ต์ฅ์ ๋ญ๊ฐ ํ์ด๋๊ฐ๊ณ ๋ ์์ง๋ง ๊ทธ๋ค์ ์์ ์ด ๋ญ ํ๊ณ ์๋์ง๋ ์ ์ธ์ํ์ง ๋ชปํ๋ ๊ฒฝ์ฐ๊ฐ ๋ง์ต๋๋ค. ๋จธ๋ฆฌ๊ฐ ํธ๋ ๊ฒ ์๋๊ณ ์์ด ํธ๋ ๊ฒ์ด์ฃ .
๋๋ฒ์งธ๊ฐ ์ ๋๋ก ํ๋ จ๋์ง ๋ชปํ ์ฌ๋์ ์ผ์ผ์ด ๊ตฌํ์ ํด๋ณด๊ณ ์คํ์ ํด๋ด์ผ๋ง ์๊ณ ๋ฆฌ์ฆ๊ฐ์ ๋น๊ต๋ฅผ ํ ์ ์์ต๋๋ค. ํนํ ์์ ์ด ๊ฐ์ง ์นดํ๋ก๊ทธ๋ฅผ ๋ฒ์ด๋ ์๊ณ ๋ฆฌ์ฆ์ ๋ง๋๋ฉด ์ด ๋ฌธ์ ๊ฐ ์๊น๋๋ค. ์ด๊ฑด ์๋นํ ๋๊ฐ๋ฅผ ์น๋ฃจ๊ฒ ํฉ๋๋ค.
์ธ๋ฒ์งธ๊ฐ ์ ๋๋ก ํ๋ จ๋์ง ๋ชปํ ์ฌ๋์, ๋ฌธ์ ๋ฅผ ๋ณด๋ฉด "์, ์ด๊ฑด ์ด๋ ๊ฒ ์ด๋ ๊ฒ ํด๊ฒฐํ๋ฉด ๋ฉ๋๋ค"๋ผ๋ ๋ง์ ๊ณง์ ํ ์ ์์ง๋ง ๋ง์ ์ปดํจํฐ์์ ์ํ ๋์ผ๋ฉด ์๋ฌด ๊ฒ๋ ํ์ง ๋ชปํฉ๋๋ค. ์ฌ์ง์ด ์์ ์ด ์๊ฐํด๋ธ ๊ทธ ๊ตฌ์ฒด์ ์๊ณ ๋ฆฌ์ฆ์ ๋จ์๊ฒ ์ค๋ช
ํด ์ค ์ ์๊ธฐ๊น์ง ํ์ง๋ง, ๊ทธ๋ค์ ๊ทธ๊ฑธ "์ปดํจํฐ์๊ฒ" ์ค๋ช
ํด ์ฃผ๋ ๋ฐ์๋ ์คํจํฉ๋๋ค. ๋ญ๊ฐ ์๊ฐํด ๋ผ ์ ์๋ค๋ ๊ฒ๊ณผ, ๊ทธ๊ฑธ ์ปดํจํฐ๊ฐ ์ดํดํ ์ ์๊ฒ ์ค๋ช
ํ ์ ์๋ค๋ ๊ฒ์ ๋ค๋ฅธ ์ฐจ์์ ๋ฅ๋ ฅ์ ํ์๋ก ํฉ๋๋ค.
๊ทธ๋ฆฌ๊ณ ๋ง์ง๋ง์ผ๋ก, ์๋ฃ๊ตฌ์กฐ/์๊ณ ๋ฆฌ์ฆ ๊ณต๋ถ๋ฅผ ํ ๋์๋ ๊ฐ๋ฅํ๋ฉด ์ค์ง์ ์ด๊ณ ๊ตฌ์ฒด์ ์ธ ์ค์ธ๊ณ์ ๋ฌธ์ ๋ฅผ ํจ๊ป ๋ค๋ฃจ๋ ๊ฒ์ด ํฐ ๋์์ด ๋ฉ๋๋ค. ๋ชจ๋ ํ์ต์ ์์ด ์ด๋ ๋๊ฐ์ด ์ ์ฉ๋ฉ๋๋ค. ์ธ๋ฅ์ ์ง์ฑ์ฌ๋ฅผ ๋ด๋, ๊ตฌ์(concrete) ๋ค์์ ์ถ์(abstract)๊ฐ ์ค๊ณ , ์ธ๊ฐ ๊ฐ์ฒด ํ๋์ ์ฑ์ฅ์ ๋ด๋ ๊ทธ๋ฌํฉ๋๋ค. be ๋์ฌ ๋ํ๊ธฐ to ๋ถ์ ์ฌ๊ฐ ์์ ์ผ๋ก ํด์๋ ์ ์๋ค๋ ๋ฃฐ๋ง ์ธ์ฐ๋ ๊ฒ๋ณด๋ค, ๊ทธ๋ฌํ ๋ค์ํ ์๋ฌธ์ ์ค์ ๋ฌธ๋งฅ ์์์ ์ฌ๋ฌ๋ฒ ๋ณด๋ ๊ฒ์ด ํจ์ฌ ๋์ ๊ฒ์ ์๋ช
ํฉ๋๋ค. ์๊ณ ๋ฆฌ์ฆ/์๋ฃ๊ตฌ์กฐ ๊ณต๋ถ๋ฅผ ํ ๋ ์ฌ๋ฌ ์น๊ตฌ๋ค๊ณผ ํจ๊ป ์ฐ์ต๋ฌธ์ (ํนํ ์ค์ธ๊ณ์ ๋์๋ค๊ณผ ๊ด๋ จ์ด ์๋ ๊ฒ)๋ฅผ ํ์ด๋ณด๊ธฐ๋ ํ๊ณ , ACM์ ICPC ๋ฑ์ ํ๋ก๊ทธ๋๋ฐ ๊ฒฝ์ง ๋ํ์ ๋ฌธ์ ์ค ํด๋น ์๊ณ ๋ฆฌ์ฆ/์๋ฃ๊ตฌ์กฐ๊ฐ ์ฌ์ฉ๋๋ ๋ฌธ์ ๋ฅผ -- ์ด๊ฒ ๊ฐ๋ฅํ๋ ค๋ฉด "์ด ์๊ณ ๋ฆฌ์ฆ์ด ์ฐ์ด๋ ๋ฌธ์ ๋ ์ด๊ฑฐ๋ค"๋ผ๋ ๊ฐ์ด๋๋ฅผ ํด์ค ์ฌ๋์ด ์์ผ๋ฉด ์ข๊ฒ ์ฃ -- ๊ฐ์ด ํ์ด๋ณด๋ ๊ฒ๋ ์์ฃผ ์ข์ต๋๋ค.
--๊น์ฐฝ์ค
์๊ณ ๋ฆฌ์ฆ/์๋ฃ๊ตฌ์กฐ ๊ต์ก์ ๋ํ ๋ถ๋ง
์ฐ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ ์นดํ๋ก๊ทธ๋ฅผ ๋ฐฐ์ด๋ค. ์ด๋ฏธ ๊ทธ๋ฌํ ํด๋ฒ์ด ์กด์ฌํ๊ณ , ๊ทธ๊ฒ์ด ์ต๊ณ ์ด๋ฉฐ, ๋ฐ๋ผ์ ๊ทธ๊ฒ์ ๋ฌ๋ฌ ์ธ์ฐ๊ณ ์ดํดํด์ผ ํ๋ค. ์ข ๋๋ํ ์น๊ตฌ๋ค์ ์ข
์ข
, "์ด์ผ ์ด๊ฑฐ ์ ๋ง ๊ธฐ๊ฐ๋งํ ํด๋ฒ์ด๊ตฐ!"ํ๋ ๊ฐํ์ ์ธ์น ์ง๋ ๋ชจ๋ฅธ๋ค. ๋๋ถ๋ถ์ ๋๋จธ์ง ํ์๋ค์ ๊ทธ ํด๋ฒ์ ์ดํดํ๋ ค๊ณ ๋จธ๋ฆฌ๋ฅผ ์ฅ์ด์ง๊ณ ํ์ฐธ์ ์จ๋ฆํ ํ์์ผ ์ด๋ ดํ์ด ์ ์ด ํด๋ฒ์ด ๊ทธ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋์ง ๋ฉ๋ํ๊ฒ ๋๋ค. ๊ทธ๋ฆฌ๊ณ ๋ ๊ทธ "์ฆ๋ช
"์ ์ฑ
์์ ๋ฎ์ด๋๊ณ ๊น๋งฃ๊ฒ ์ฌ๋ผ์ ธ๋ฒ๋ฆฐ๋ค. ์์ผ๋ก๋ ๊ทธ๋ฅ "์ฌ์ฉ"ํ๋ฉด ๋๋ ๊ฒ์ด๋ค. ๋ ๋ง์ ๋๋ค์์ ํ์์ ์ด ๊ณผ์ ์ด ๋ฌด์๋ฏธํ๋ค๋ ๊ฒ์ ์๊ธฐ ๋๋ฌธ์ ์ ์ด ํด๋ฒ์ด ์ด ๋ฌธ์ ๋ฅผ ๋ฌธ์ ์์ด ํด๊ฒฐํ๋์ง์ ์ฆ๋ช
์ ๊ฐ๋จํ ๊ฑด๋๋ฐ๊ธฐ๋ฅผ ํ๋ค.
์ด๋ฐ ํ์๋ค์ด ์ฃผ์ด์ง ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ๋ ์์ "๊ฐ๊ด์" ํน์ "๋ฌธ์ ์ถ์ ์"๊ฐ ์กด์ฌํ๋ ์ํ์ฅ ์ํฉ ํ์์๋ ๋ฐ์ด๋ ์ฑ์ ์ ๋ณด์ผ๊ฒ์์ ์๋ช
ํ๋ค. ํ์ง๋ง ์ค์ค๋ก๊ฐ ๋ฌธ์ ์ ํด๋ต์ ๋ชจ๋ ๋ง๋ค์ด๋ด์ผ ํ๋ ์ํฉ์ด๋ผ๋ฉด, ์๊ณ ๋ฆฌ์ฆ์ ์์ ํ ์๋ก ๊ณ ์ํด๋ด์ผ ํ๋, ๋๋ ๊ธฐ์กด ์๊ณ ๋ฆฌ์ฆ์ ๋ณํํด์ผ ํ๋ ๋๋ค์์ ์ํฉ์ด๋ผ๋ฉด ์ด๋จ๊น?
๊ต์ก์ ๋ฌผ๊ณ ๊ธฐ๋ฅผ ์ก๋ ๋ฐฉ๋ฒ์ ๊ฐ๋ฅด์ณ์ฃผ์ด์ผ ํ๋ค. ์ด๋ค ์๊ณ ๋ฆฌ์ฆ์ ๋ฐฐ์ด๋ค๋ฉด, ๊ทธ ์๊ณ ๋ฆฌ์ฆ์ ๊ณ ์ํด ๋ธ ์ฌ๋์ด ์ด๋ค ์ฌ๊ณ ์ ๊ณผ์ ์ ๊ฑฐ์ณ์ ๊ทธ ํด๋ฒ์ ๋๋ฌํ๋์ง๋ฅผ ๊ตฌ๊ฒฝํ ์ ์์ด์ผ ํ๊ณ , ํ์์ ๊ฐ์ ์ค์ค๋ก๋ง์ ํด๋ฒ์ ์ฐจ๊ทผ ์ฐจ๊ทผ "๊ตฌ์ฑ"(construct)ํ ์ ์์ด์ผ ํ๋ค(์ด๋ฅผ ๊ต์ก์ฒ ํ์์ ๊ตฌ์ฑ์ฃผ์๋ผ๊ณ ํ๋๋ฐ, ๋ ๊ณ ์ ์๋ฒ์ง์ด๊ณ ๋ง๋น ๋ฏผ์คํค์ ํจ๊ป MIT ๋ฏธ๋์ด๋ฉ์ ์ ๊ตฌ์์ธ ์ธ์ด๋จธ ํํผํธ ๋ฐ์ฌ๊ฐ ์ฃผ์ฐฝํ๋ค). ์ ๋ฌธ๊ฐ๊ฐ ํ๋ ๊ฒ์ ๋ฐฐ์ฐ์ง ๋ง๊ณ , ๊ทธ๋ค์ด ์ด๋ป๊ฒ ์ ๋ฌธ๊ฐ๊ฐ ๋์๋๊ฐ๋ฅผ ๋ฐฐ์ฐ๊ณ ํ๋ด๋ด๋ผ.
๊ฒฐ๊ตญ์ ์ํฌ๋ผํ
์ค์ ์ธ ๋ํ๋ฒ์ด๋ค. ํด๋ต๋ฅผ ๊ฐ๋ฅด์ณ ์ฃผ์ง ์์ผ๋ฉด์๋, ์ด๋ฑํ๊ต ํ์์ด ์์ ์ด ๊ฐ์ง ์ง์๋ง์ผ๋ก ์ค์ค๋ก ํต์ํธ๋ฅผ ์ ๋ํด ๋ผ ์ ์๋๋ก ์์์ ๋์์ค ์ ์๋๊ฐ? ์ด๊ฒ์ด ์ฐ๋ฆฌ ์ค์ค๋ก์ ๊ต์ฌ๋ค์๊ฒ ๋ฌผ์ด์ผ ํ ์ง๋ฌธ์ด๋ค.
--๊น์ฐฝ์ค
๊ณ ๋ฑํ๊ต๋๋ถํฐ ํ๋ฌ์จ ๊ต์ก๋ฐฉ์์ ํํด๊ฐ ์๋๊น ํ๋ค์. '๋ฌด์์, ์' ๋ผ๋ ์ง๋ฌธ ์ด์ ์ '์ด๋ป๊ฒ' ๊ฐ ๋จธ๋ฆฟ์์ ๋ค์ด์๋ฒ๋ฆฌ๋. --์์ฒ
์ ์ฐ๋ฆฌ๋ ํ๊ต์์ "ํ๋ก๊ทธ๋๋ฐ์ ํ๋ ๊ณผ์ "์ด๋ "๋์์ธ ๊ณผ์ "์ ๋ฐฐ์ด ์ ์ด ์์๊น? ์ ํด๋ต์ ์ด๋ฅด๋ ๊ณผ์ ์ ๊ฐ๋ฅด์ณ์ฃผ๋ ์ฌ๋์ด ์๋? ์ฐ๋ฆฌ๊ฐ ๋ณด๋ ๊ฒ์ ๋ชจ์กฐ๋ฆฌ ์ข
์ ์ํ์ ๊ฒฐ๊ณผ๋ฌผ๋ก์์ ํ๋ก๊ทธ๋จ ๋ฟ์ด๋ค. ๊ต์๊ฐ ์ด๋ค ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ์ ํด๋ต์ ๊ฐ๋ฅด์น ๋, "๊ต์๋, ๊ต์๋๊ป์๋ ์ด๋ค ์ฌ๊ณ ์ ๊ณผ์ ์ ๊ฑฐ์ณ, ๊ทธ๋ฆฌ๊ณ ์ด๋ค ๋์์ธ ๊ณผ์ ๊ณผ ํ๋ก๊ทธ๋๋ฐ ๊ณผ์ ์ ๊ฑฐ์ณ์ ๊ทธ ํ๋ก๊ทธ๋จ์ ๋ง๋์
จ์ต๋๊น?"๋ผ๊ณ ๋ฌผ์ด๋ณด์. ๋ง์ฝ ์ฌ๊ธฐ์ ์ด๋ค ์ฒด๊ณ์ ์ธ ๋ต๋ณ๋ ํ ์ ์๋ ์ฌ๋์ด๋ผ๋ฉด, ๊ทธ ์ฌ๋์ ์์ ์ ์ฌ๊ณ ์ ๋ํด ์ฌ๊ณ ํด ๋ณธ ์ ์ด ์๊ฑฐ๋, ๋ฌธ์ ํด๊ฒฐ์ ์ด๋ค ํจ์จ์ ์ฒด๊ณ๋ฅผ ๊ฐ์ถ์ง ๋ชปํ ์ฌ๋์ด๋ฉฐ, ๋ฐ๋ผ์ ์์ง ๋จ์ ๊ฐ๋ฅด์น ์ค๋น๊ฐ ๋์ด์์ง ์์ ์ฌ๋์ด๋ค. --๊น์ฐฝ์ค
์๊ณ ๋ฆฌ์ฆ์ ๊ณต๋ถํ๋ฉด ํฐ ์ค๊ธฐ๋ค์ ์์์ผ ํฉ๋๋ค. ๊ฐ๋ณ ํ
ํฌ๋๋ค๋ ์ค์ํ์ง๋ง "ํจ๋ฌ๋ค์"์ด๋ผ๊ณ ํ ๋งํ ๊ฒ๋ค์ ์์์ผ ํฉ๋๋ค. ๊ทธ๋์ผ ์๊ณ ๋ฆฌ์ฆ์ ์ํฉ์ ๋ง๊ฒ ๋ง์๋๋ก ์์ฉํ ์ ์์ต๋๋ค. ๋, ์์ ๋ง์ ๋ถ๋ฅ๋ฒ์ ๋ง๋ค์ด์ผ ํฉ๋๋ค. (see also HowToReadIt Build Your Own Taxonomy) ๊ตฌ์ฒด์ ์ธ ๋ฌธ์ ๋ค์ ์ผ์ด์ค ๋ฐ์ด ์ผ์ด์ค๋ก ์ฌ๋ฟ ์ ํ๋ ๋์ ๊ทธ๋ฅ ์ง๋์ณ ๋ฒ๋ฆฌ๋ฉด ๊ฐ๋ณ์๋ ์์ํ ๊ฐ๋ณ์๋ก ๋จ์ ๋ฟ์
๋๋ค. ๋น์ทํ ๋ฌธ์ ๋ค์ ์๋ก ๋ฌถ์ด์ ์ผ๋ฐํ๋ฅผ ํด์ผ ํฉ๋๋ค. (see also DoItAgainToLearn)
์ด์ ๊ด๋ จํด์ Anany Levitin์ A NEW ROAD MAP OF ALGORITHM DESIGN TECHNIQUES(DDJ, 2000 Apr)๋ฅผ ๊ถํฉ๋๋ค. ๊ทธ๋ ์๊ณ ๋ฆฌ์ฆ ๋์์ธ ํ
ํฌ๋์ ๋ค์ ๋ค๊ฐ์ง๋ก ํฌ๊ฒ ๋๋๋๋ค:
- brute force
- divide-and-conquer
- decrease-and-conquer
- transform-and-conquer
์๋ฃ๊ตฌ์กฐ์ ์๊ณ ๋ฆฌ์ฆ์ ํ๋ก๊ทธ๋จ์ ๋ง๋๋ ๋ฐ ์์ด์ ์ค์ํ๋ค๊ณ ์๊ฐํฉ๋๋ค. ๋จ์ด ๋ง๋ ์๋ฃ๊ตฌ์กฐ์ ์๊ณ ๋ฆฌ์ฆ์ ์ด์ฉํ๋๋ฐ ๊ทธ์น์ง ๋ง๊ณ ์ค์ค๋ก ์๊ฐํ์ฌ ๋ง๋๋ ๊ฒฝ์ง์ ์ค๋ฅด๋ฉด ์ข๊ฒ ์ต๋๋ค. -๊ฐํฌ๊ฒฝ
DeleteMe) 1ํ๊ธฐ๋๋๊ฐ๋ ๋ง๋น์ ํํ ๋ง๊ธ์. ๋ชจ๋ ๊ฒ๋ค์ ํ๋ฒ์ฉ ๊ตฌํํด๋ณด๊ณ ๊ฐ์ด์ผํ๋๋ฐ... ์๋ก ๋ค์ผ์๋ ๋ถ๋ค ๊ผญ ํ๋ฒ์ฉ ๊ตฌํํด๋ณด์ธ์. ์ง๊ธ ์๊ฐํด๋ณด๋ ์ ์ ์ค์ํ ๊ฒ์ ๋ฑํ์ํ ๋๋์
๋๋ค - eternalbleu
see also HowToStudyDesignPatterns