はじめに

今週から半年ぶりにAtCoderに参加していこうと思う。
それにあたり、茶コーダーの自分が緑コーダーになるために身につけるべきアルゴリズムについてまとめる。
復習のために、すでに覚えているものも書いていく。

本当に自分用でただのメモなので、読者様のお役に立たないとは思いますが、ぜひ最後までお付き合いください

1. 全探索

順番に全部探索していくヤーツ。
工夫した全探索もあるから下に書いてく↓

変数が取りうる値が2つしかないときに使える全探索。
過去に自分が記事を書いていたので省略
【bit全探索】誰でも理解できるアルゴリズム解説

順列を全列挙して探索する。
でも全列挙するとTLEになることがある。
並び方が決まっていて、その前後などを出せば解決することが多いイメージ。
C++のnext_permutation使えば一発。

区間系の問題に使える。
左から順に、そこまでの合計を記録した配列を用意するヤーツ。
累積和の配列で、条件を満たすなら区間を広げ、満たさないなら区間を狭めるみたいな使い方できる。

めっちゃ出るイメージ
「xが合成数ならば、√x以下の約数を持つ」という性質を使う
昔はこれ知ってるだけでたまに茶問題解けたな。
参考：最速の素数判定プログラム C# Java C++

全然使わないけど、知ってたら即答できる系アルゴリズム
二次元配列で、何もない場所、みたいなのが存在する時に使える。
これも昔記事を書いていたので省略
【座標圧縮】誰でも理解できるアルゴリズム解説

有向グラフの最短距離に使う。
都度その場所に行くまでの最短コストを記録して探索していく。
このアルゴリズム使う問題に本番で出会ったことがない！出現頻度は低そう。

木だからトップからダウンまで高速で探索できる。
グループ機能付きキーバリュー構造みたいな感じ？
UnionFindのクラスと関数作っておくだけで、これ使うってわかれば解ける。
↑問題によっては一工夫しないと解けないっぽい(全部のアルゴリズムそうかも)

深さ優先探索と幅優先探索ですね。
グラフで何かを探索したり、最短経路を求めたりで使いますね。
深い位置に答えがある時は深さ、浅い箇所に答えがある時は幅を利用するイメージ
再帰とキュー理解してればどっちも実装できる。

動的計画法。これだけが理解できない。
フロッグ問題とかナップサック問題が有名で、それは理解できるしコードも書けるんだけど、他に全く応用できない。
誰か教えて欲しい...

説明見てみると、１つの問題を複数問題に分割して考えるみたいなことあるけど、なんとなくしか理解できない。

ここがいちばんの課題な気がします...
勉強してできるようになったらここ編集します！！！

アルゴリズムとか知らなくても、数学の知識があれば解ける問題って多いですよね。
私は数I・Aで終わった人間なので数学系がでたら詰みます。
ここも課題ですね。

この記事書いて気づいたけど、ネットで調べて出てくる緑に必要なアルゴリズム、DP以外は全部理解してる気がする。
DPと数学知識が課題かな。。。

死ぬ気で頑張って今年中に緑目指します！！！