$$\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\N}{\mathbb{N}} \newcommand{\R}{\mathbb{R}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\C}{\mathbb{C}} \renewcommand{\L}{\mathcal{L}} \newcommand{\x}{\times} \newcommand{\contra}{\scalebox{1.5}{\lightning}} \newcommand{\inner}[2]{\left\langle #1 , #2 \right\rangle} \newcommand{\st}{\text{ such that }} \newcommand{\for}{\text{ for }} \newcommand{\Setcond}[2]{ \left\{\, #1 \mid #2 \, \right\}} \newcommand{\setcond}[2]{\Setcond{#1}{#2}} \newcommand{\seq}[1]{ \left\langle #1 \right\rangle} \newcommand{\Set}[1]{ \left\{ #1 \right\}} \newcommand{\set}[1]{ \set{#1} } \newcommand{\sgn}{\text{sign}} \newcommand{\halfline}{\vspace{0.5em}} \newcommand{\diag}{\text{diag}} \newcommand{\legn}[2]{\left(\frac{#1}{#2}\right)} \newcommand{\ord}{\text{ord}} \newcommand{\di}{\mathrel{|}} \newcommand{\gen}[1] \newcommand{\irr}{\mathrm{irr }} \renewcommand{\deg}{\mathrm{deg }} \newcommand{\nsgeq}{\trianglelefteq} \newcommand{\nsg}{\triangleleft} \newcommand{\argmin}{\mathrm{argmin}} \newcommand{\argmax}{\mathrm{argmax}} \newcommand{\minimize}{\mathrm{minimize}} \newcommand{\maximize}{\mathrm{maximize}} \newcommand{\subto}{\mathrm{subject\ to}} \newcommand{\DKL}[2]{D_{\mathrm{KL}}\left(#1 \di\di #2\right)} \newcommand{\ReLU}{\mathrm{ReLU}} \newcommand{\E}{\mathsf{E}} \newcommand{\V}{\mathsf{Var}} \newcommand{\Corr}{\mathsf{Corr}} \newcommand{\Cov}{\mathsf{Cov}} \newcommand{\covariance}[1]{\Cov\left(#1\right)} \newcommand{\variance}[1]{\V\left[#1\right]} \newcommand{\variancewith}[1]{\V\left[#1\right]} \newcommand{\expect}[1]{\E\left[#1\right]} \newcommand{\expectwith}[2]{\E_{#1}\left[#2\right]} \renewcommand{\P}{\mathsf{P}} \newcommand{\uniform}[2]{\mathrm{Uniform}\left(#1 \dots #2\right)} \newcommand{\gdist}[2]{\mathcal{N}\left(#1, #2\right)} \DeclarePairedDelimiter{\norm}{\lVert}{\rVert}$$ \everymath{\displaystyle}

Total views

## 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) μ ν¬ν¨νμ¬ μ΄λ€ κ²½λ‘λ‘λ  νμν©λλ€. :)

1. λ§ν¬ μκ° λ³΅μ‘λ, Big-O notation
2. λ§ν¬ λ¦¬μ€νΈ, μ€ν, ν, λ± λ±μ κΈ°λ³Έ μλ£κ΅¬μ‘°
3. λ§ν¬ μ λ ¬κ³Ό νμ (Quick sort, Quick select, Linear Select)
4. λ§ν¬ Binary Search
• μ²«λ²μ§Έ κΈλ°μ§μΌλ‘, Ternary Searchλ₯Ό λ€λ£¨μμ΅λλ€.
5. λ§ν¬ Graph basics
• μλμ μΌλ‘ BFS/DFS λ±μ λ°°μ°λ μμ μ λ―Έλ€μ΅λλ€. μ¬κΈ°μλ νκ³Ό κ°λ¨ν μ΄μ§ νΈλ¦¬ λ±μ λ€λ£Ήλλ€.
• μ΄λ κ² λ§λ  μ΄μ λ μ ν¬ νκ΅ μλ£κ΅¬μ‘° μμ λͺ©μ°¨λ λΉμ·νκ² λ§μΆκΈ° μν΄μμμ΅λλ€.
6. λ§ν¬ Binary Search Trees, Union Find
7. Balanced Binary Search Tree
• μλ£ μμ΄ κ·Έλ₯ μ§ννλ μ£Όμ μλλ€.
• μ΄κ±° μλ£λ λ§λ€κΈ° λλ¬΄ μ΄λ €μμ μλ§ λ§λ€μ§ μμ μμ μλλ€.
8. λ§ν¬ Divide and Conquer / Dynamic Programming
9. λ§ν¬ More on DnC / DP
• PSμ©μΌλ‘ λ§λ€μλ μλ£κ° λλ¬΄ μκΉμ κ³ , κ²°μ μ μΌλ‘ λ©μ§ μμ΄λμ΄λ€μ μκ°ν΄ μ£Όκ³  μΆμμ΅λλ€.
• Segment Tree, Merge sort Tree, LCA λ± λλΌμ΄ λ΄μ©λ€μ βλΆν  μ λ³΅ λ° λ€μ΄λλ―Ή νλ‘κ·Έλλ°β μ΄λΌλ μ§λμΉκ² μΌλ°μ μΈ μ΄λ¦ μλμ λλ €λ£μλ€λ λΉνμ κ²Ένν λ°μλ€μλλ€. γγ!
• μ²μ μ΄ λ΄μ©μ μ½λ λΆμ΄ κ³΅λΆνκΈ°μλ λλ¬΄ μ΄λ €μΈ μλ μμ΅λλ€. ν΅μ§Έλ‘ μ€ν΅ν΄λ λ©λλ€.
10. Greedy Algorithms
11. Graph (1) : DFS/BFS
12. Graph (2) : Shortest Path / MST
13. Graph (3) : SCC
14. String Algorithms : KMP, Hashing, Trie
• λͺ©μ°¨μλ κ³ννμΌλ νλ²λ String algorithmsλ₯Ό λ€λ€λ³Έμ μ μμ΅λλ€.
• μ΄μ λ κ° μ€ν°λλ₯Ό μ§νν  λλ§λ€ 13κΉμ§ λκ° λ€μ Additional topicμ λ¬λ ΈκΈ° λλ¬Έμλλ€.
• PS λͺ©μ μΌ λλ μΈκ·ΈνΈλ¦¬λ₯Ό, κ·Έλ μ§ μμ λͺ©μ μΌ λλ NP-Completeness κ°μ μ£Όμ λ₯Ό λ€λ£¨μμ΅λλ€.
• μλ§λ μλ£λ§ λ§λ λ€λ©΄ KMP, Hashing, Trie μ΄ μΈ κ°μ§λ₯Ό λ€λ£° λ― ν©λλ€.