アルゴリズム
アルゴリズムは実装しないとすぐに忘れてしまうので、一日ひとつのアルゴリズムを実装する。繰り返し実装することで定着させる。
データ構造
- Union Find Tree
- ヒープ(プライオリティキュー)
- 二分探索木
- 平衡二分探索木
- AVL木
- 赤黒木
- セグメント木
- Range Minimum Query/Range Maximum Query
- Partial Sum Problem(区間更新なし)
- Partial Sum Problem(区間更新あり)
- Stary Sky 木
- Binary Indexed Tree
- Partial Sum Problem(区間更新なし)
- Partial Sum Problem(区間更新あり)
- ハッシュ
- スタック
- キュー
- 双方向リスト
- デキュー
グラフ
- 二分木
- 走査(Traverse)
- 最短路
- 単一始点最短路
- 全点対最短路
- Floyd-Warshall:O(N^3)
- Johnson
- k-最短路
- 全域木
- 最小全域木
- Prim
- Kruskal
- 最小直径全域木(Cuninghame-Green)
- 最小全域有向木(Chu-Liu/Edmonds)
- 最小シュタイナー木(Dreyfus-Wagner)
- 最小全域木
- フロー・カット
- 最大流
- Ford-Fulkerson:O(F E)
- Edmonds-Karp
- Dinic:O(EV^2)
- Goldberg-Tarjan
- 最小点カット
- 無向グラフの全域最小カット(Nagamochi-Ibaraki/Stoer-Wagner)
- Gomory-Hu木
- 最小費用流
- 最大流
- マッチング
- 二部グラフの最大マッチング
- 二部グラフの最小重み最大マッチング
- 二部グラフの辺彩色
- 最小重み最大マッチング
高速化
- 繰り返し二乗法
- 行列の繰り返し二乗法
- しゃくとり法
- 反転
- 半分全列挙
- 座標圧縮
ソート
探索
- A*
文字列
- Rope