PS 알고리즘 정리(Last Edit : 2023/04/17)

아래 분류는 계속해서 수정되고 추가될 예정이다. 내가 공부한 거를 정리하고 있다.

알고리즘 분류
00_Complete Search
Backtracking : Pruning

01_Math
Number Theory
=Prime Number
==Sieve of Eratosthenes
=Extended Euclidean Algorithm
=Chinese Remainder Theorem
FFT - DFT

02_Geometry
=Convex Hull
==Rotating Calipers

03_Greedy

04_DP
==Convex Hull Trick

05_String
=KMP Algorithm
=Rabin-Karp Algorithm
=Trie(Radix Tree, Prefix Tree)
=Aho-Corasick

Suffix Array?

06_Graphs & Tree
Graphs
=Searching
==DFS(Depth-First Search)
==BFS(Breadth-First Search)
=Topological Sort

=MST (Minimun Spanning Tree)
==Kruskal Algorithm
==Prim Algorithm

=Shortest Path
==Dijkstra Algorithm
==Bellman-Ford Algorithm
==Floyd-Warshall Algorithm

=Strongly Connected Component
==압축 DAG
==2-Sat Problem

=BiConnected Component
==Block-Cut Tree

=Articulation Point & Bridge(단절점과 단절선)

=Network Flow
==Ford-Fulkerson Algorithm
==Edmonds-Karp Algorithm
===Binary Matching
===Minimum Cut : Maximun Flow
===MCMF : Minimun-Cost Maximum-Flow
==Dinic's Algorithm
==Hopcroft-Karp Algorithm
===Circulation

Tree
=LCA(Lowest Common Ancestor)

07_Data Structure (Without 4.)
=C++ Standard Library
==Stack, Queue, List, Vector, Deque
==Heap -> Priority_Queue
==Set, Map => Binary Search Tree
==Unordered Set, Unordered Map => Hashing
==PBDS

=BST

=Disjoint Set : Union-Find Forest
==UF union by rank : 랭크가 작은 쪽으로 합치기
==UF Path Compression : 경로 압축
==LCA + UF (Making Root) : https://rebro.kr/149의 온라인 풀이

=Sparse Table
==LCA!

Range Query
=Square Root Decomposition

=Segment Tree
==ST with lazy propagation
==PST(Persistent Segment Tree)
===k번째 작은 수 찾기 ; 값과 인덱스 반전 / Merge Sort Tree
https://seastar105.tistory.com/47
https://nicotina04.tistory.com/121
https://justicehui.github.io/icpc/2018/11/24/BOJ7469/
==머지 소트 트리
https://justicehui.github.io/medium-algorithm/2020/02/25/merge-sort-tree/
==Heavy-Light Decomposition : Segment Tree in Tree
==세그먼트 트리 비츠
https://justicehui.github.io/hard-algorithm/2019/10/10/segment-tree-beats/

08_String & Search
Sorting
=기본 정렬(O(N^2))
==Insertion, Bubble, Selection
===Bubble 횟수 : Number Of Inversion => O(NlogN) 가능

Search
=Binary search : 오름차순/내림차순 정렬된 상태
==Lower bound / Upper Bound
==LIS(Longest Increasing Subsequence)
==PBS(Parallel Binary Search) : 병렬 이분 탐색
https://justicehui.github.io/hard-algorithm/2020/02/24/pbs/
==Parametric Search : 실수 범위의 이분탐색 / 최적화 문제 -> 결정 문제!! (결정 문제 시간복잡도 * logN)

=Trinary search : 위로 볼록 / 아래로 볼록 상태 (일정한 구간은 Only 정상에서만)

09_Technic
=좌표 압축 : by map
=Two Pointer & Sliding Window
=Sweeping Technic
=Meet in the Middle
=Bitmasking
==기법 정리 要

=Query Technic
==Offline Query
===Mo's Algorithm