알고리즘 정리
이것저것 공부한 내용 또는 혼자 알아낸 내용들을 나중에 쉽게 다시 찾아볼 수 있도록 간단히 정리해 두는 것이 가장 큰 목표.
책이나 인터넷에서 쉽게 찾을 수 있는 내용을 굳이 다시 적을 필요는 없다. 그냥 링크만 걸어두자.
내용에 대한 핵심 요약, 적용되는 문제 유형에 따라 재분류, 알고리즘을 실제로 구현하면서 알게된 사실 등을 추가하도록 하자.
목록
완전 탐색
백트래킹
Meet in the middle
이진 검색 (Binary search)
파라메트릭 서치
선택 알고리즘
투 포인터
그리디 알고리즘
시뮬레이션 (Simulation)
애드혹
동적 계획법 (Dynamic Programming)
구간 분할 방식에 관한 DP
선형 점화식
볼록 껍질을 이용한 최적화
배낭 문제 (Knapsack problem)
유명한 문제
최대 부분합 (Maximum subarray problem)
가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence / LIS)
정렬
선형 자료 구조
연결 리스트 (Linked List)
스택 (Stack)
Monotone stack
덱 (Deque)
Monotone deque
비선형 자료구조
Disjoint Set
Order Statistic Tree
Inversion Counting
우선순위 큐 (Priority Queue)
Monotonic Priority Queue
피보나치 힙
이진 탐색 트리 (Binary search tree)
세그먼트 트리
Stern-Brocot Tree
그래프
그래프 탐색
BFS
깊이 우선 탐색 (Depth-first search; DFS)
최단 경로 (Shortest Path Problem)
단일 출발지 최단 경로 (Single Source Shortest Path)
데이크스트라 알고리즘 (Dijkstra's algorithm)
Shortest Path Faster Algorithm (SPFA)
전체쌍 최단 경로 문제 (All-pairs shortest paths; APSP)
최소 신장 트리 (Minimum Spanning Tree / MST)
방향 비순환 그래프 (Directed Acyclic Graph; DAG)
위상 정렬 (Topological Sorting)
사이클 유무 판별
Transitive closure
연결 요소 (Connected Component)
강한 연결 요소 (Strongly Connected Component / SCC)
2-SAT
이중 연결 요소 (Bi-connected Component)
동적 연결성
매칭
이분 매칭 (Bipartite Matching)
그래프 색칠
2색 색칠
네트워크 플로우 (Network Flow)
최대 유량 (Maximum Flow)
최소 비용 최대 유량 (MCMF, Minimum Cost Maximum Flow)
최소 컷 (Minimum Cut)
트리 (Tree)
트리의 지름
최소 공통 조상 (Lowest Common Ancestor / LCA)
HLD
센트로이드 분할 (Centroid Decomposition)
경로 쿼리
수학
계산
거듭제곱의 빠른 계산 (Exponentiation by squaring)
큰 수의 빠른 곱셈
행렬의 빠른 곱셈
정수론
최대 공약수 (GCD; Greatest Common Divisor)
소수 (Prime number)
소수 목록 구하기
소수 판별 (Primality Test)
소인수분해 (Prime Factorization)
모듈러 연산 (Modular arithmetic)
모듈러 역원 (Modular Multiplicative Inverse)
연립 선형 합동식
팩토리얼
곱셈적 함수 (Multiplicative Function)
뫼비우스 함수 (Mobius function)
제곱수의 합
조합론
이항 계수 (Binomial Coefficient)
카탈랑 수 (Catalan number)
피보나치 수 (Fibonacci numbers)
영 타블로 (Young tableau)
확률론
기댓값
계산기하
선분 교차
여러가지 수학 정리
게임 이론 (Game theory)
문자열
문자열 매칭
라빈-카프 알고리즘 (Rabin-Karp Algorithm)
KMP 알고리즘
Z 알고리즘
트라이 (Trie)
접미사 배열 (Suffix Array)
팰린드롬
가장 긴 팰린드롬 부분문자열 (Longest Palindromic Substring)
EERTREE
쿼리
구간 쿼리
Maximum overlapping intervals
경로 쿼리
오프라인 쿼리
병렬 이분 탐색 (Parallel Binary Search; PBS)
합성곱 (Convolution)
고속 푸리에 변환 (Fast Fourier Transform, FFT)
Fast Walsh Hadamard Transform (FWHT)
Zeta / Mobius transform
기타 등등
요세푸스 문제
체스 기물 배치 문제 (N-Queen, Rook, Bishop, ...)
통계학 / 기계학습
k-means clustering
구현 관련
2D 그리드
비트 연산