はじめに
今週から半年ぶりにAtCoderに参加していこうと思う。
それにあたり、茶コーダーの自分が緑コーダーになるために身につけるべきアルゴリズムについてまとめる。
復習のために、すでに覚えているものも書いていく。
本当に自分用でただのメモなので、読者様のお役に立たないとは思いますが、ぜひ最後までお付き合いください 
1. 全探索
順番に全部探索していくヤーツ。
工夫した全探索もあるから下に書いてく↓
bit全探索
変数が取りうる値が2つしかないときに使える全探索。
過去に自分が記事を書いていたので省略
【bit全探索】誰でも理解できるアルゴリズム解説
順列全探索
順列を全列挙して探索する。
でも全列挙するとTLEになることがある。
並び方が決まっていて、その前後などを出せば解決することが多いイメージ。
C++のnext_permutation使えば一発。
2. 累積和・しゃくとり法
区間系の問題に使える。
左から順に、そこまでの合計を記録した配列を用意するヤーツ。
累積和の配列で、条件を満たすなら区間を広げ、満たさないなら区間を狭めるみたいな使い方できる。
3. 高速素数判定
めっちゃ出るイメージ
「xが合成数ならば、√x以下の約数を持つ」という性質を使う
昔はこれ知ってるだけでたまに茶問題解けたな。
参考：最速の素数判定プログラム C# Java C++
4. 座標圧縮
全然使わないけど、知ってたら即答できる系アルゴリズム
二次元配列で、何もない場所、みたいなのが存在する時に使える。
これも昔記事を書いていたので省略
【座標圧縮】誰でも理解できるアルゴリズム解説
5. ダイクストラ法
有向グラフの最短距離に使う。
都度その場所に行くまでの最短コストを記録して探索していく。
このアルゴリズム使う問題に本番で出会ったことがない！出現頻度は低そう。
6. Union-Find木
木だからトップからダウンまで高速で探索できる。
グループ機能付きキーバリュー構造みたいな感じ？
UnionFindのクラスと関数作っておくだけで、これ使うってわかれば解ける。
↑問題によっては一工夫しないと解けないっぽい(全部のアルゴリズムそうかも)
7. DSF・BFS
深さ優先探索と幅優先探索ですね。
グラフで何かを探索したり、最短経路を求めたりで使いますね。
深い位置に答えがある時は深さ、浅い箇所に答えがある時は幅を利用するイメージ
再帰とキュー理解してればどっちも実装できる。
8. DP
動的計画法。これだけが理解できない。
フロッグ問題とかナップサック問題が有名で、それは理解できるしコードも書けるんだけど、他に全く応用できない。
誰か教えて欲しい...
説明見てみると、１つの問題を複数問題に分割して考えるみたいなことあるけど、なんとなくしか理解できない。
ここがいちばんの課題な気がします...
勉強してできるようになったらここ編集します！！！
Ex. 数学的知識
アルゴリズムとか知らなくても、数学の知識があれば解ける問題って多いですよね。
私は数I・Aで終わった人間なので数学系がでたら詰みます。
ここも課題ですね。
終わりに
この記事書いて気づいたけど、ネットで調べて出てくる緑に必要なアルゴリズム、DP以外は全部理解してる気がする。
DPと数学知識が課題かな。。。
死ぬ気で頑張って今年中に緑目指します！！！
