$$ \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?

  • PS์—์„œ ์“ฐ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜๋“ค ์™ธ์—๋„ ๋” theoreticalํ•œ ์ž๋ฃŒ๊ตฌ์กฐ/์•Œ๊ณ ๋ฆฌ์ฆ˜๋“ค์— ๋Œ€ํ•œ ์ดํ•ด๊ฐ€ ๋ถ€์กฑํ•œ ๊ฒƒ ๊ฐ™์•„์„œ ๊ณต๋ถ€ํ•ด ๋ณด๊ธฐ๋กœ ํ–ˆ์Šต๋‹ˆ๋‹ค. PS์—์„œ๋„ ์š”์ฆ˜์€ ๋” ๋†’์€ ๋ ˆ๋ฒจ๋กœ ๊ฐ€๋ฉด splay tree / link cut tree ๊ฐ™์€๊ฑด ์ข€ ๋‚˜์˜ค๋Š”๊ฒƒ ๊ฐ™๊ธฐ๋„ ํ•˜๊ตฌ์š”. PSํ‹ฑํ•œ ๋‚ด์šฉ๋“ค (DP-optimization์ด ๋Œ€ํ‘œ์ ) ๋„ ์„ž์ผ ์˜ˆ์ •์ž…๋‹ˆ๋‹ค.
  • ๊ณ„ํš : ๊ณ ๊ธ‰ ์ž๋ฃŒ๊ตฌ์กฐ / ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋‚ด์šฉ๋“ค, CLRS์—์„œ ์•„์ง ์ œ๋Œ€๋กœ ๊ณต๋ถ€ํ•˜์ง€ ์•Š์€ ๋ถ€๋ถ„ ๋ช‡๊ฐ€์ง€, ๊ณ„์‚ฐ์ด๋ก  ์ˆ˜์—… MIT ๊ณ ๊ธ‰ ์ž๋ฃŒ๊ตฌ์กฐ 6.851 ๋งํฌ ์ด๋‚˜ ๊ณ ๊ธ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋งํฌ 1 ๋งํฌ 2 ๊ฐ™์€ ๋‚ด์šฉ๋“ค ์ค‘ ๋ช‡๊ฐ€์ง€ ์žฌ๋ฐŒ์–ด ๋ณด์ด๊ฑฐ๋‚˜ ์ด๊ฑด ์•Œ์•„์•ผ ํ•œ๋‹ค๊ณ  ์ถ”์ฒœ๋ฐ›์€ ๋‚ด์šฉ๋“ค์„ ๋ณผ ๊ณ„ํš์ž…๋‹ˆ๋‹ค.
  • ์–ธ์  ๊ฐ€ ๋‹ค๋ฃฐ ๋‚ด์šฉ๋“คโ€ฆ

Various topics

Topic Link
Amortized Analysis Link
Hashing ย 
Network Flows ย 
Linear Programming ย 
Divide and conquer optimization Link
Pollardโ€™s Rho Algorithm Link

Advanced Data Structures

Topic Link
Fibonacci Heaps Link
Splay trees ย 

Randomized Algorithms

Topic Link
Karger-Stein Min Cut Link

Graph Algorithms

Topic Link
Fixed Subgraph Isomorphism Link
Pagerank & Random walk with Restart Link

String Algorithms

Mainly from : SNU 2021 Fall Theory of computation

Topic Link
Aho-Corasick Algorithm Link
Boyer-Moore Algorithm Link
Baker-Bird Algorithm ย 
Wu-Manber Algorithm ย 
Suffix Tree ย 
Suffix Array ย