| 名前 | 概要や用例や用途など |
| 難易度(低) | |
| 総当り(ブルートフォース) | その名の通り、全ての解の候補を調べる手法。全探索とも呼ぶ。 |
| キュー(FIFO) | 先入れ先出しのデータ構造。幅優先探索などに使われる。 |
| スタック(LIFO) | 後入れ先出しのデータ構造。深さ優先探索などに使われる。 |
| 両端キュー(deque) | |
| ハッシュテーブル | |
| 二分木 | |
| バブルソート | 隣り合う２つの要素を比較してスワップを繰り返していくソートアルゴリズム。計算量はO(N^2)と遅いが直感的には分かりやすい。 |
| マージソート | ソートしたい配列を半分に区切り、それらを別々に再帰的にソートしてマージするアルゴリズム。計算量は比較ソートの理想値であるO(NlogN)。安定ソートでもある。 |
| 挿入ソート | |
| 選択ソート | |
| クイックソート | |
| バケットソート | |
| 幅優先探索(BFS) | スタートからゴールまでの最短距離を計算するとか |
| 深さ優先探索(DFS) | スタートからゴールまでのルートを見つけ出すとか |
| 二分探索 | ソートされた配列から目的の値を探すときに、探索範囲を半分、半分、・・・と削っていくアルゴリズム。計算量はO(logN)と高速。探索以外にも最小値や最大値を求める問題にも応用できる。 |
| 累積和 | 配列のある区間の和を高速に求めたいというときに使われる。配列の先頭からi番目までの和を計算した配列を別に持っておくことで、ある区間の和がO(1)で求められるというテクニック。 |
| しゃくとり法 | |
| 最小二乗法 | |
| 二分法 | |
| ニュートン法 | |
| ヒープ木 | |
| 分割統治法 | |
| 木の直径 | 木構造の２頂点間の距離で最も距離の長いペアを１つ見つけるアルゴリズム |
| 難易度(中) | |
| 平衡二分木 | |
| 赤黒木 | 平衡二分木の一種 |
| AVL木 | 平衡二分木の一種 |
| ワーシャルフロイド法(WF) | グラフの全ての２点間の最短距離を求めたいときに使われるアルゴリズム。頂点数をNとすると計算量はO(N^3)。辺の重みが負であっても適用でき、負閉路があればそれを検出することも可能。 |
| 最小全域木 | |
| ダイクストラ法 | グラフのある始点から全ての頂点への最短距離を求めたいときに使われるアルゴリズム。頂点数をN、辺の数をMとすると計算量はO((N+M)logN)。辺の重みが全て非負でないと適用できないことに注意。 |
| 素集合データ構造(UnionFind/DisjointSet/UF) | ２つの集合を１つにまとめたり、ある２つの要素が同じ集合に属しているかを高速に判定することを可能にするデータ構造。Nを要素数とすると、各操作のならし計算量はO(A(N))となる。A(N)はアッカーマン関数の逆関数で増加速度が非常に遅く、実質O(1)と考えても問題は無い。 |
| FenwickTree(BinaryIndexedTree/BIT) | 部分的な値の更新を繰り返す必要のあるデータの累積和を高速取得できるデータ構造。値の更新、累積和の取得がどちらもO(logN)で出来る。セグメント木の機能制限版のようなものであるが、こちらのほうが定数倍速い、実装が軽いなどの長所がある。 |
| 動的計画法(DynamicProgramming/DP) | 小さい部分問題の解を利用してより大きな部分問題の解を求めることを繰り返す手法。部分問題の解を記録しておくことと漸化式を用いることがポイント。非常に応用範囲が広く、競技プログラミングにおいても必須のテクニックである。代表的な問題としてナップサック問題がある。 |
| 線型計画法(LinearProgramming/LP) | |
| 貪欲法(GreedyAlgorithm/GA) | 後のことは考えずにその時その時での最適行動を取っていく手法。探索範囲を大きく狭められるので計算量を劇的に改善することも出来るが、その貪欲法で正しい解答が得られるかは慎重に考える必要がある。正しい解が得られない貪欲法を嘘貪欲と言ったりする。 |
| トライ木(TrieTree) | |
| セグメント木 | |
| トポロジカルソート | |
| 三分探索 | |
| 難易度(高) | |
| k平均法 | |
| 高速フーリエ変換(FFT) | |
| モンテカルロ法 | |
| A＊サーチ(Aスターサーチ) | |
| タブーサーチ | |
| ビームサーチ | |
| 山登り法(HC) | |
| 焼きなまし法(SA) | |
| いもす法(imos法) | |
| chokudaiサーチ | |
