アルゴリズム一覧
競プロでこれまでに勉強したアルゴリズムと、これから挑戦したいものをまとめてみました。
勉強した/したいアルゴリズム
ソートアルゴリズム
挿入ソート
バブルソート
シェルソート
マージソート
クイックソート
探索アルゴリズム
二分探索
bit全探索
ニュートン法
半分全列挙
DP
メモ化再帰
最長共通部分列 (LCS)
最大増加部分列 (LIS)
最小コスト弾性マッチング
bitDP
桁DP
木DP
全方位木DP
グラフアルゴリズム
深さ優先探索 (DFS)
幅優先探索 (BFS)
UnionFindによるループ検索
トポロジカルソート
01-BFS
クラスカル法 / 最小全域木
ベルマンフォード法
ダイクストラ法
ワーシャルフロイド法
文字列アルゴリズム
Z-Algorithm
Suffix-Array
ローリングハッシュ
数論/その他
累積和
尺取り法
エラトステネスの篩
比較的高速な素因数分解 / 素数判定
GCD / LCM
繰り返し2乗法 (高速な冪乗計算)
逆ポーランド記法
フェルマーの小定理
MOD逆元
高速な二項係数の剰余
高速な累乗計算 (繰り返し2乗法)
座標圧縮
分割数
高速フーリエ変換 (FFT)
next_permutation関数
カラツバ法 (高速乗算アルゴリズム)
データ構造
配列 / リスト / キュー / スタック
ヒープ
グラフ
UnionFind木
二分探索木
セグメント木
BinaryIndexedTree (BIT)
RangeSumQuery
RangeMinimumQuery
モノイド
遅延評価
平衡二分探索木
Splay木
AVL木
赤黒木