E-maxx Algorithms 한국어 현지화 프로젝트

본 프로젝트는 e-maxx.ru/algo 의 영문 번역본인 cp-algorithms (e-maxx-eng) 를 한국어로 번역한 것입니다. e-maxx 프로젝트의 저자는 иванов максим 이며, cp-algorithms 프로젝트의 기여자는 여기서 확인하실 수 있습니다. 본 프로젝트는 CC-BY-SA-4.0 License를 따릅니다.

• 본 프로젝트의 오탈자 및 기타 오류에 대한 문의나 프로젝트 참여는 sylvester@ajou.ac.kr로 문의 주시길 바랍니다.
• 추후에 개인 블로그가 아닌 독립적인 웹 사이트에서 호스팅할 예정입니다. 업데이트가 있으면 이곳에 공지하도록 하겠습니다.
• 현재 몇몇의 내부 링크를 사용할 수 없습니다. 빠르게 수정하도록 하겠습니다.

기여자

• cwlo2F - 오일러 피 함수, 모듈러 역원, Number of divisors / sum of divisors, 선형 합동방정식 번역
• akim9905 - 희소테이블 번역

별도의 명시자가 없는 경우 번역자는 권도현입니다.

Articles (번역 후)

대수

• 기초
  • 이진 거듭제곱
  • 최대공약수 계산을 위한 유클리드 호제법
  • 확장 유클리드 호제법
  • 선형 디오판토스 방정식
  • 피보나치 수열
• 소수들
  • 에라토스테네스의 체
• Number-theoretic functions
  • 오일러 피 함수
  • Number of divisors / sum of divisors
• 모듈러 산술
  • 모듈러 역원
  • 선형 합동방정식

자료구조

• 기초
• 희소 테이블 (임시 링크 (notion))

Articles (번역 전)

Algebra

• Fundamentals
  • 번역 완료
• Prime numbers
  • Linear Sieve
  • Primality tests
  • Integer factorization
• Number-theoretic functions
  • 번역완료
• Modular arithmetic
  • Chinese Remainder Theorem
  • Factorial modulo $p$
  • Discrete Log
  • Primitive Root
  • Discrete Root
  • Montgomery Multiplication
• Number systems
  • Balanced Ternary
  • Gray code
• Miscellaneous
  • Enumerating submasks of a bitmask
  • Arbitrary-Precision Arithmetic
  • Fast Fourier transform
  • Operations on polynomials and series

Data Structures

• Fundamentals
  • Minimum Stack / Minimum Queue
  • Sparse Table
• Trees
  • Disjoint Set Union
  • Fenwick Tree
  • Sqrt Decomposition
  • Segment Tree
  • Treap
  • Sqrt Tree
  • Randomized Heap
• Advanced
  • Deleting from a data structure in O(T(n)log n)

Dynamic Programming

• DP optimizations
  • Divide and Conquer DP
• Tasks
  • Dynamic Programming on Broken Profile. Problem "Parquet"
  • Finding the largest zero submatrix

String Processing

• Fundamentals
  • String Hashing
  • Rabin-Karp for String Matching
  • Prefix function - Knuth-Morris-Pratt
  • Z-function
  • Suffix Array
  • Aho-Corasick algorithm
• Advanced
  • Suffix Tree
  • Suffix Automaton
  • Lyndon factorization
• Tasks
  • Expression parsing
  • Manacher's Algorithm - Finding all sub-palindromes in O(N)
  • Finding repetitions

Linear Algebra

• Matrices
  • Gauss & System of Linear Equations
  • Gauss & Determinant
  • Kraut & Determinant
  • Rank of a matrix

Combinatorics

• Fundamentals
  • Finding Power of Factorial Divisor
  • Binomial Coefficients
  • Catalan Numbers
• Techniques
  • The Inclusion-Exclusion Principle
  • Burnside's lemma / Pólya enumeration theorem
  • Stars and bars
  • Generating all $K$-combinations
• Tasks
  • Placing Bishops on a Chessboard
  • Balanced bracket sequences
  • Counting labeled graphs

Numerical Methods

• Search
  • Ternary Search
  • Newton's method for finding roots
• Integration
  • Integration by Simpson's formula

Geometry

• Elementary operations
  • Basic Geometry
  • Finding the equation of a line for a segment
  • Intersection Point of Lines
  • Check if two segments intersect
  • Intersection of Segments
  • Circle-Line Intersection
  • Circle-Circle Intersection
  • Common tangents to two circles
  • Length of the union of segments
• Polygons
  • Oriented area of a triangle
  • Area of simple polygon
  • Check if points belong to the convex polygon in O(log N)
  • Minkowski sum of convex polygons
  • Pick's Theorem - area of lattice polygons
  • Lattice points of non-lattice polygon
• Convex hull
  • Convex hull construction
  • Convex hull trick and Li Chao tree
• Sweep-line
  • Search for a pair of intersecting segments
  • Point location in O(log N)
• Miscellaneous
  • Finding the nearest pair of points
  • Delaunay triangulation and Voronoi diagram
  • Vertical decomposition
  • Half-plane intersection - S&I Algorithm in O(Nlog N)

Graphs

• Graph traversal
  • Breadth First Search
  • Depth First Search
• Connected components, bridges, articulations points
  • Finding Connected Components
  • Finding Bridges in O(N+M)
  • Finding Bridges Online
  • Finding Articulation Points in O(N+M)
  • Strongly Connected Components and Condensation Graph
  • Strong Orientation
• Single-source shortest paths
  • Dijkstra - finding shortest paths from given vertex
  • Dijkstra on sparse graphs
  • Bellman-Ford - finding shortest paths with negative weights
  • 0-1 BFS
  • D´Esopo-Pape algorithm
• All-pairs shortest paths
  • Floyd-Warshall - finding all shortest paths
  • Number of paths of fixed length / Shortest paths of fixed length
• Spanning trees
  • Minimum Spanning Tree - Prim's Algorithm
  • Minimum Spanning Tree - Kruskal
  • Minimum Spanning Tree - Kruskal with Disjoint Set Union
  • Second best Minimum Spanning Tree - Using Kruskal and Lowest Common Ancestor
  • Kirchhoff Theorem
  • Prüfer code
• Cycles
  • Checking a graph for acyclicity and finding a cycle in O(M)
  • Finding a Negative Cycle in the Graph
  • Eulerian Path
• Lowest common ancestor
  • Lowest Common Ancestor
  • Lowest Common Ancestor - Binary Lifting
  • Lowest Common Ancestor - Farach-Colton and Bender algorithm
  • Solve RMQ by finding LCA
  • Lowest Common Ancestor - Tarjan's off-line algorithm
• Flows and related problems
  • Maximum flow - Ford-Fulkerson and Edmonds-Karp
  • Maximum flow - Push-relabel algorithm
  • Maximum flow - Push-relabel algorithm improved
  • Maximum flow - Dinic's algorithm
  • Maximum flow - MPM algorithm
  • Flows with demands
  • Minimum-cost flow
  • Assignment problem. Solution using min-cost-flow in O (N^5)
• Matchings and related problems
  • Bipartite Graph Check
  • Kuhn' Algorithm - Maximum Bipartite Matching
• Miscellaneous
  • Topological Sorting
  • Edge connectivity / Vertex connectivity
  • Tree painting
  • 2-SAT
  • Heavy-light decomposition

Miscellaneous

• Sequences
  • RMQ task (Range Minimum Query - the smallest element in an interval)
  • Longest increasing subsequence
  • Search the subsegment with the maximum/minimum sum
  • K-th order statistic in O(N)
• Game Theory
  • Games on arbitrary graphs
  • Sprague-Grundy theorem. Nim
• Schedules
  • Scheduling jobs on one machine
  • Scheduling jobs on two machines
  • Optimal schedule of jobs given their deadlines and durations
• Miscellaneous
  • Josephus problem
  • 15 Puzzle Game: Existence Of The Solution
  • The Stern-Brocot Tree and Farey Sequences

감사합니다.