E D R , A S I H C RSS

How To Study Data Structure And Algorithms

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


Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:23:26
Processing time 0.0105 sec