$$ \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}{\mathbb{E}} \newcommand{\expect}[1]{\E\left[#1\right]} \newcommand{\expectwith}[2]{\E_{#1}\left[#2\right]} \renewcommand{\P}{\mathbb{P}} \newcommand{\uniform}[2]{\mathrm{Uniform}\left(#1 \dots #2\right)} \newcommand{\gdist}[2]{\mathcal{N}\left(#1, #2\right)} $$

Algo / DS

Data structures & Algorithms

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 이 μ„Έ 가지λ₯Ό λ‹€λ£° λ“― ν•©λ‹ˆλ‹€.