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

• PS์์ ์ฐ๋ ์๊ณ ๋ฆฌ์ฆ๋ค ์ธ์๋ ๋ theoreticalํ ์๋ฃ๊ตฌ์กฐ/์๊ณ ๋ฆฌ์ฆ๋ค์ ๋ํ ์ดํด๊ฐ ๋ถ์กฑํ ๊ฒ ๊ฐ์์ ๊ณต๋ถํด ๋ณด๊ธฐ๋ก ํ์ต๋๋ค. PS์์๋ ์์ฆ์ ๋ ๋์ ๋ ๋ฒจ๋ก ๊ฐ๋ฉด splay tree / link cut tree ๊ฐ์๊ฑด ์ข ๋์ค๋๊ฒ ๊ฐ๊ธฐ๋ ํ๊ตฌ์. PSํฑํ ๋ด์ฉ๋ค (DP-optimization์ด ๋ํ์ ) ๋ ์์ผ ์์ ์๋๋ค.
• ๊ณํ : ๊ณ ๊ธ ์๋ฃ๊ตฌ์กฐ / ์๊ณ ๋ฆฌ์ฆ ๋ด์ฉ๋ค, CLRS์์ ์์ง ์ ๋๋ก ๊ณต๋ถํ์ง ์์ ๋ถ๋ถ ๋ช๊ฐ์ง, ๊ณ์ฐ์ด๋ก  ์์ MIT ๊ณ ๊ธ ์๋ฃ๊ตฌ์กฐ 6.851 ๋งํฌ ์ด๋ ๊ณ ๊ธ ์๊ณ ๋ฆฌ์ฆ ๋งํฌ 1 ๋งํฌ 2 ๊ฐ์ ๋ด์ฉ๋ค ์ค ๋ช๊ฐ์ง ์ฌ๋ฐ์ด ๋ณด์ด๊ฑฐ๋ ์ด๊ฑด ์์์ผ ํ๋ค๊ณ  ์ถ์ฒ๋ฐ์ ๋ด์ฉ๋ค์ ๋ณผ ๊ณํ์๋๋ค.
• ์ธ์  ๊ฐ ๋ค๋ฃฐ ๋ด์ฉ๋คโฆ

### Various topics

Topic TLDR
Amortized Analysis Framework of analyzing more complex algorithms consisting multiple operations
Hashing ย
Network Flows ย
Linear Programming ย
Divide and conquer optimization Method of DP optimization
Pollardโs Rho Algorithm Fast probabilistic prime factorization

### Advanced Data Structures

Topic TLDR
Fibonacci Heaps Heap with decrease-key operation
Splay trees ย

### Randomized Algorithms

Karger-Stein Min Cut Fast randomized algorithm for min-cut problem