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

##全検索

###DFS（深さ優先検索）

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

###BFS（幅優先検索）

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

参考：「アルゴリズム」資料 12. 深さ優先探索と幅優先探索

##DP（動的計画法）

• 事例：ナップサック問題、最長共通部分列、最大部分配列問題　

##データ構造

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

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

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

参考：Union-find（素集合データ構造）

##グラフ理論

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

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

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

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

##最短路問題

###ダイクストラ法
参考：ダイクストラ法についてまとめる

###ベルマンフォード法
参考：ベルマンフォード法をやっと理解した。

###ワーシャルフロイド法
参考：素人によるワーシャルフロイド法

##数学的問題

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

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

• コード例

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)の組が必ず存在する。

• 事例：すごろく

• コード例

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 の解き方 〜

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

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

• コード例

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)を効率的に計算する。

• 事例：カーマイケル数

• コード例

//問題：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;
}

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

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

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