Algo / DS
Data structures & Algorithms
What is This?
μ§κΈκΉμ§ μΈ λ² μλ£κ΅¬μ‘° / μκ³ λ¦¬μ¦μ κ΄λ ¨ν΄μ κ°λ¨ν μμ μ μ’ ν΄λ³Έμ μ΄ μμ΅λλ€.
- 2019λ λ΄ SNUPSμμ νλ PS-Intro μ€ν°λ
-
2020λ 12-2μ, 2021λ 7-8μ ν΄μ λ λ² κ°μΈμ μΌλ‘ μλ μ¬λκ³Ό μ§μ곡μ μ°¨μμμ. νΉν λ°©ν λ λ² λͺ¨λ μ νν λ°°μ΄ μ¬λλ€μ΄ μν μ 곡μ΄μκ³ κ΅μ₯ν λ°μ΄λ μνμ Baseλ₯Ό κ°μ§κ³ μμκΈ° λλ¬Έμ μ κ° μλ£λ₯Ό λ§λ€λ€κ° λμ€μ κΈλ°μ§μ μ‘°κΈ νμ΅λλ€.
-
κ·Έλ μ¬μ©νλ μλ£λ€μ reformν΄μ 곡κ°ν μμ μ λλ€. μμ§ μμ±λμ§ μμ λΆλΆλ€μ΄ μμ΅λλ€.
-
PS/CP μ λ¬Έμ μν΄ μ νν λ°°μ΄ μ¬λλ μκ³ , 컴곡과 μκ³ λ¦¬μ¦ μμ λ£κΈ° μ μ 미리 곡λΆν΄ λ³΄κ³ μΆλ€κ³ ν΄μ λ°°μ΄ μ¬λλ μλ λ± κ°μ κ°μΈμ λͺ©μ μ΄ μ‘°κΈμ© λ¬λκΈ° λλ¬Έμ μλ£λ μ½κ° λ€μμ¬ μμ΅λλ€. μΈμ κ°λ μ΄ λͺ¨λ μλ£λ₯Ό μ 리ν΄μ μμ±νκ³ μΆμ μκ°λ μκΈ΄ ν©λλ€λ§, μ°μ μμλ κ½€ λ¨μ΄μ§λκ² κ°μ΅λλ€. κ°μΈμ μΌλ‘ λνμμ΄ κ²°μ λκ³ λμκ° κ°μ₯ νκ°νμ§ μμκΉ μΆμ΅λλ€.
- Number Theoretic Algorithms μ€ν°λλ₯Ό μ§ννμ
¨λ kipa00λμ μ€νμΌμ μ λ§ λ§μ μν₯μ λ°μμ΅λλ€.
- νΉν, μ§μ μκ°ν΄ λ³Ό μ μλλ‘ Step-by-StepμΌλ‘ κ°μ΄λνλ μ°μ΅λ¬Έμ μ²λΌ λ§λ€μ΄ λμ μλ£λ κ·ΈλΆμ NTAμμ μ²μ λ³Έ νμμΈλ°, κ°μΈμ μΌλ‘ μλμ μΌλ‘ λ΄μ©μ λ°λΌκ°μ§ μκ³ κ³΅λΆμ λ§μ λμμ΄ λμκΈ° λλ¬Έμ μμΌλ‘ μ€ν°λλ₯Ό μ§ννκ±°λ λκ°λ₯Ό κ°λ₯΄μΉκ² λλ©΄ κΌ κ·Έλ κ² λ§λ€κ² λ€κ³ μκ°ν λ©΄μ΄ μ’ μμ΅λλ€.
- κ·Έλ κΈ° λλ¬Έμ, μ΄λ¦μ βAdditional Topics and Exerciseβ μ§λ§, μ€μ λ‘λ λ³Έλ¬Έμ μΌλΆμ λλ€. μ¦, $x$μ₯μ μ°μ΅λ¬Έμ μ λ€μ΄μλ λ΄μ©μ $y (x > y)$μ₯μμ νΉλ³ν μΈκΈ μμ΄ κ°μ Έλ€ μ°λ©°, λ μκ° μ΄μ μ±ν°μ μ°μ΅λ¬Έμ λ₯Ό λͺ¨λ μ΅νλ€κ³ κ°μ ν©λλ€.
- μ¬μ€ μκ°ν΄λ³΄λ©΄ κ·Έλ° μ΄μ λλ¬Έμ λ νμΌλ‘ λ΄μ©μ μ΅νκΈ°μ λ§€μ° μ΄λ €μ΄ μ¬μ ν μλ£μ λλ€. μ κ° μμμ νλμ© μλ €μ€ λλ μ λ΄μ©λ€μ΄ λ³Έλ¬Έμ μΌλΆμ¬λ μκ΄μ΄ μμ§λ§, μλ£λ§ 보면 ν΅μ¬λ΄μ©μ λν μ€λͺ μ μ°μ΅λ¬Έμ μ²λΌ λμλμ λ©΄μ΄ μκΈ° λλ¬Έμ λλ€. κ·Έλμ, μΈμ κ° μ΄ μλ£λ₯Ό μμ±ν λλ κ·Έ λΆλΆλ κ°μνμ¬ μμ ν μκ°μ λλ€.
μ΄ν΄κ° μκ°λ λΆλΆμ λν μ§λ¬Έ, μλ£μ μ€λ₯, μ€ν λ±μ λν μ§μ μ μΈμ λ μ§ μ¬κΈ° λκΈμ΄λ μ κ°μΈ λ©μΌ (gratus907@snu.ac.kr) μ ν¬ν¨νμ¬ μ΄λ€ κ²½λ‘λ‘λ νμν©λλ€. :)
λͺ©μ°¨
- λ§ν¬ μκ° λ³΅μ‘λ, Big-O notation
- λ§ν¬ 리μ€νΈ, μ€ν, ν, λ± λ±μ κΈ°λ³Έ μλ£κ΅¬μ‘°
- λ§ν¬ μ λ ¬κ³Ό νμ (Quick sort, Quick select, Linear Select)
-
λ§ν¬ Binary Search
- 첫λ²μ§Έ κΈλ°μ§μΌλ‘, Ternary Searchλ₯Ό λ€λ£¨μμ΅λλ€.
-
λ§ν¬ Graph basics
- μλμ μΌλ‘ BFS/DFS λ±μ λ°°μ°λ μμ μ λ―Έλ€μ΅λλ€. μ¬κΈ°μλ νκ³Ό κ°λ¨ν μ΄μ§ νΈλ¦¬ λ±μ λ€λ£Ήλλ€.
- μ΄λ κ² λ§λ μ΄μ λ μ ν¬ νκ΅ μλ£κ΅¬μ‘° μμ λͺ©μ°¨λ λΉμ·νκ² λ§μΆκΈ° μν΄μμμ΅λλ€.
- λ§ν¬ Binary Search Trees, Union Find
- Balanced Binary Search Tree
- μλ£ μμ΄ κ·Έλ₯ μ§ννλ μ£Όμ μ λλ€.
- μ΄κ±° μλ£λ λ§λ€κΈ° λ무 μ΄λ €μμ μλ§ λ§λ€μ§ μμ μμ μ λλ€.
- λ§ν¬ Divide and Conquer / Dynamic Programming
-
λ§ν¬ More on DnC / DP
- PSμ©μΌλ‘ λ§λ€μλ μλ£κ° λ무 μκΉμ κ³ , κ²°μ μ μΌλ‘ λ©μ§ μμ΄λμ΄λ€μ μκ°ν΄ μ£Όκ³ μΆμμ΅λλ€.
- Segment Tree, Merge sort Tree, LCA λ± λλΌμ΄ λ΄μ©λ€μ βλΆν μ 볡 λ° λ€μ΄λλ―Ή νλ‘κ·Έλλ°β μ΄λΌλ μ§λμΉκ² μΌλ°μ μΈ μ΄λ¦ μλμ λλ €λ£μλ€λ λΉνμ κ²Ένν λ°μλ€μ λλ€. γ γ !
- μ²μ μ΄ λ΄μ©μ μ½λ λΆμ΄ 곡λΆνκΈ°μλ λ무 μ΄λ €μΈ μλ μμ΅λλ€. ν΅μ§Έλ‘ μ€ν΅ν΄λ λ©λλ€.
- Greedy Algorithms
- Graph (1) : DFS/BFS
- Graph (2) : Shortest Path / MST
- Graph (3) : SCC
- String Algorithms : KMP, Hashing, Trie
- λͺ©μ°¨μλ κ³ννμΌλ νλ²λ String algorithmsλ₯Ό λ€λ€λ³Έμ μ μμ΅λλ€.
- μ΄μ λ κ° μ€ν°λλ₯Ό μ§νν λλ§λ€ 13κΉμ§ λκ° λ€μ Additional topicμ λ¬λ ΈκΈ° λλ¬Έμ λλ€.
- PS λͺ©μ μΌ λλ μΈκ·ΈνΈλ¦¬λ₯Ό, κ·Έλ μ§ μμ λͺ©μ μΌ λλ NP-Completeness κ°μ μ£Όμ λ₯Ό λ€λ£¨μμ΅λλ€.
- μλ§λ μλ£λ§ λ§λ λ€λ©΄ KMP, Hashing, Trie μ΄ μΈ κ°μ§λ₯Ό λ€λ£° λ― ν©λλ€.