History: 라이브러리에 넣으면 좋을거 같은 것들에 관한 리스트

함께 추가해봅시다.

자료구조

  • Range Query/Update Index Tree
    • Quad tree
  • Treap
  • Splay Tree
  • Dynamic Tree
  • Big Integer

그래프

  • Network Flow
    • Stoer-Wagner
  • Min-cost Max-Flow
  • Bipartite Matching
    • Bipartite Weighted Matching
  • BiConnected Component 분해
  • Strongly Connected Component 분해
  • 2-SAT 만족해 찾기
  • Articulation Point, Bridge 찾기
  • Loop 찾기
  • Dijkstra Algorithm
  • Bellman Ford algorithm

트리

  • Lowest Common Ancestors
  • Heavy Light Decomposition

문자열

  • Suffix array/tree
    • with longest common prefix calculation
  • KMP
  • aho-corasic
  • Manacher's algorithm

정수론

  • extended euclidean algorithm
  • chinese remainder theorem
  • Pollard-Rho
  • Miller Rabin Primality Test
  • Legendre Symbol 계산
  • Linear Equation System을 임의의 양수 modular 내에서 풀기(소수 modular는 쉬움)

수학

  • Kirchhoff's Theorem
  • A^n, A^0 + A^1 + ... + A^n의 log n 계산 알고리즘
  • Karatsuba Algorithm
  • Simplex Method
  • Matrix Inversion
  • Gauss Jordan Method
  • Matrix LU Decomposition
  • FFT

기하

  • convex hull
  • rotating calipers
  • plane sweep (line intersection 계산 등)
  • polygon cut
  • 무게중심