AtCoderに取り組んで、行き詰ってアルゴリズムを学習し始めた人のチラシの裏です。
[読んでる本]
アルゴリズムとデータ構造
アルゴリズムを考える時の基本方針
「困難は分割せよ」
全体の解決方法を考えるのではなく、まずは手近な小さい値で検討を始めるのが良い。
よく使うアルゴリズム
全探索
頭から順に探索して特定する。いわゆるforで解いていく。
二分探索
ソート済みの配列を、以上・以下などの条件で半分に割って、探索範囲を半減させて特定する。forにif-elseが組み合わさったやつ。
動的計画法
課題の部分を解く処理を作って、それを繰り返す。
この時、処理を表す表を作って、順番に表を埋めて、目的の値を探索する。
動的計画法を理解するための補助
①再帰
メソッド内で自分を呼び出すアレ。結果を出すために実施した処理の中で、さらに同じ処理を実施する。
問題を小さくして部分をメソッド内で作るイメージ。部分を繰り返すことで全体を解く。
無限ループできるので、終了条件は明確に。
②再帰＋メモ化
再帰で課題を解こうとすると、往々にして「同じ条件を繰り返し処理している」問題にぶち当たる。
ので、既に処理した条件はメモしていって、メモに書いてあるものはやらない、という考え方。
よくやる。
⇒これらを踏まえて、動的計画法はメモするモノが条件から結果に変わる。
表を作って、順繰り埋めていくイメージ。
※以下がイメージ湧きやすくて良きでした。
https://www.momoyama-usagi.com/entry/info-algo-dp#i-2
課題を解く時の考え方のコツ
初心者は、いきなり「全探索が最適だ」とか「動的計画法が最適だ」とか、出てこない。
あるかないかだけを考える
素直に頭から順に眺めて、条件に合ったかどうかで判断する。
ゴリ押しも案外使えるのだ。
選んだ時と選ばなかったときを考える
選んだ時に条件に当てはまるか
当てはまる：選んだ時に条件に当てはまるか繰り返す。
当てはまらない：選ばなかった時に条件に当てはまるかを見て同じように繰り返す。
まずは、全体じゃなくて、問題の一部を解いていく。
処理を繰り返して、最終的に全体を解くような流れ。
境界の右(true)か左(false)かを考える
線分のどこに境界を設けるかで無限にtrue/false領域として扱えるようになる。
二分探索の応用みたいなイメージ。
できたものはメモしていく
メモ化して、確認が終わったところはスキップさせるたり、条件を埋めていったり、とにかく保持しておく。
新人研修でメモ取らされるのも伊達じゃない。
感想
プログラムなので当たり前と言えば当たり前なのだが、最終的にYes/Noの話に絶対に落ちる。なので、条件として何に当てはまるか、当てはまらないかということを考えるのが大事っぽい。
と言いつつ、今のところ、見た問題に対して何を中心に考えるべきなのかすぐ迷子になる。無理。
あと、小難しいアルゴリズムになると再帰が深く関わるけど、かといって再帰に踊らされてもいけない。私は今踊らされている。なんもわからん。