知っておいて損はないアルゴリズム達

##全検索

###DFS（深さ優先検索）
- 事例：全ての状態に対して処理をしたい場合。
- メモ：スタック（最後に入れた要素が最初に出てくる）が使われる。

###BFS（幅優先検索）
- 事例：最短経路、最短手数を求めたい場合。
- メモ：キュー（最初に入れた要素が最初に出てくる）が使われる。

**参考：**[「アルゴリズム」資料 12. 深さ優先探索と幅優先探索](http://taurus.ics.nara-wu.ac.jp/algo/search1.pdf)

##DP（動的計画法）
- 事例：ナップサック問題、最長共通部分列、最大部分配列問題　

##データ構造

###ヒープ
子要素が親要素より必ず大きい二分木（全てのノードについて子が2個以下である木のこと）
キーワード：プライオリティキュー

###二分探索木
全てのノードで、その左の子以下の数は全て自分の数より小さく、右の子以下の数は全て自分の数より大きい。
キーワード：set、map、平衡二分木

###Union-Find木
グループ分けを木構造で管理するデータ構造。

**参考：**[Union-find（素集合データ構造）](https://www.slideshare.net/chokudai/union-find-49066733?ref=https://atcoder.jp/contests/atc001/tasks/unionfind_a)

##グラフ理論

キーワード：無向グラフ、有向グラフ、二部グラフ（奇数長の閉路を部分グラフとして持たない）

###隣接行列
グラフの頂点（集合V）と（集合E）の関係を、|V|×|V|の二次元配列gで表す。

**無向グラフの場合：**結ばれているなら1、結ばれていないなら0
**有向グラフの場合：**g[i][j]の値は、頂点iから頂点jに向かう辺があるなら1。他は0。
**重み付きグラフの場合：**g[i][j]は辺の重みの値になる。辺がない場合は∞（0にすると重みと区別がつかなくなるため）にする。

###隣接リスト
各頂点からの行き先をリスト化して表す。

##最短路問題

###ダイクストラ法
参考：[ダイクストラ法についてまとめる](http://galileo-magazin.com/2017/09/05/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6%E3%81%BE%E3%81%A8%E3%82%81%E3%82%8B/)

###ベルマンフォード法
参考：[ベルマンフォード法をやっと理解した。](http://galileo-magazin.com/2017/09/13/%E3%83%99%E3%83%AB%E3%83%9E%E3%83%B3%E3%83%95%E3%82%A9%E3%83%BC%E3%83%89%E6%B3%95%E3%82%92%E3%82%84%E3%81%A3%E3%81%A8%E7%90%86%E8%A7%A3%E3%81%97%E3%81%9F%E3%80%82/)

###ワーシャルフロイド法
参考：[素人によるワーシャルフロイド法](https://qiita.com/okaryo/items/8e6cd73f8a676b7a5d75)

##数学的問題

###ユークリッド互除法
2つの自然数の最大公約数を求める手法

- 事例：最大公約数、最小公倍数

- コード例

```c++:gcd.cpp
int gcd(int a, int b){
    if(b == 0) return a;
    return gcd(b, a%b);
}

// 363と66の最大公約数
int main(){
    int a = 363;
    int b = 66;
    cout << gcd(a, b) << endl;
}
```

###拡張ユークリッド互除法
ax + by = gcd(a, b) の整数解(x, y)の組が必ず存在する。

- 事例：すごろく

- コード例

```c++
int extgcd(int a, int b, int& x,int& y) {
    int d = a;
    if (b != 0){
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    }else{
        x = 1; y = 0;
    }
    return d; // 返り値はgcd(a, b)
}

int main() {
    int x, y;
    extgcd(163, 66, x, y);
    cout << x << ", " << y << endl;
}
```

参考：[拡張ユークリッドの互除法 〜 一次不定方程式 ax + by = c の解き方 〜](https://qiita.com/drken/items/b97ff231e43bce50199a)

###素数判定（エラトステネスの篩）

事例：n以下の総数の個数、素因数分解

- コード例

```c++
bool is_prime[1000005]; // is_prime[i]がtrueならiは素数

// 素数かどうかの判定（nは2以上）
bool judge_prime(int n){   
    for (int i = 2; i * i <= n; i++){
        if (n % i == 0) return false;
    }  
    return true;
}

// n以下の素数の数を返す
int eratos(int n) {
    int p = 0;
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= n; i++) is_prime[i] = true;
    for (int i = 2; i <= n; i++) {
        if (judge_prime(i)) {
            p++;
            for (int j = 2 * i; j <= n; j += i) is_prime[j] = false; // 素数の数の倍数は全てfalseにする
        }
    }
    return p;
}

int main(){
    int n = 1000000;
    cout << "総数の個数：" << eratos(n) << endl;
    return 0;
}
```

###繰り返し自乗法（効率的に）
$ n^p $ (mod m)を効率的に計算する。

- 事例：カーマイケル数

- コード例

```c++
//問題：nのp乗をmで割った余りを求める
typedef long long ll;

//パターン1
ll mod_pow1 (ll n, ll p, ll m) {
    ll res = 1;
    while (p > 0) {
        if (p & 1) res = res * n % m; // 最下位ビットで1が立っている時
        n = n * n % m;
        p >>= 1; // 右シフト
    }
    return res;
}

//パターン2
ll mod_pow2 (ll n, ll p, ll m) {
    if (p == 0) return 1;
    int res = mod_pow2(n * n % m, p / 2, m);
    if (p & 1) res = res * n % m;
    return res;
}

int main(){
    cout << mod_pow1(13, 561, 561) << endl;
    cout << mod_pow2(13, 1729, 1729) << endl;
}
```

###二分探索
ソートされたデータ群の探索範囲を半分に絞り込む操作を繰り返すことで、高速に探索する手法

- 事例：単調増加の数列からの値検索、最小値の最大化、最大値の最小化

###しゃくとり法
区間の先頭と末尾を交互に進めて条件を満たす区間を求める手法。