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