Open4
アルゴリズムとデータ構造学習
masato_is_a_ snake学習したジャンルの習熟度を個人的に採点する。
- 全探索
- OK
- グリッド
- ABC258Bのようなトーラス問題になっても解ける。DFS、BFSのグラフ問題とセットになった際の対応を忘れてしまったのでzennでの記事化で記憶の定着を図りたい。
- 順列全探索
- next_permutationを用いた典型であれば解ける。
- bit全探索
- 典型であれば解ける
- 貪欲法
- 貪欲法だと分かれば大方解けるはず
- 2分探索
- 典型であればライブラリやめぐる式で解ける。
- 再帰
- 定期的にやり直すが、毎回ほとんど忘れるので、zennでの記事化で記憶の定着を図りたい。
- メモ化再帰
- 概要は把握しているので、zennでの記事化で記憶の定着を図りたい。
- DFS
- 定期的にやり直すが、毎回ほとんど忘れるので、zennでの記事化で記憶の定着を図りたい。
- BFS
- 定期的にやり直すが、毎回ほとんど忘れるので、zennでの記事化で記憶の定着を図りたい。
- DP
- 無理
masato_is_a_ snake2分探索
- 目的
- lower_boundとupper_boundに対してユースケースに応じた挙動結果をメモ化する。
lower_bound
ソート済み配列Xに対してkey以上最初のイテレータを取得する。
- Xが[1,3,5,8]の時
- keyが1なら取得できるイテレータは
- keyが2なら取得できるイテレータは3
例外対策
配列Xの
- Xが[1,3,5,8]の時
upper_bound
配列Xに対してkeyより大きい最初のイテレータを取得する。
ex: Xが[1,3,5,8]でkeyが1なら取得できるイテレータは3、keyが2なら取得できるイテレータは3
masato_is_a_ snake経過時間 30分 + 50 = 80 + 23 = 103分 + 120 = 220
幅優先探索
こちらを用いて自分言葉に変換しながら学習していく。他の記事は一旦見ない。
迷路に学ぶ、幅優先探索のアイデアのメモ
- 目的はグリッドグラフの一番左下Sから一番右上Gへ行く際の最短経路を求める。
- Sを0とすると、1手で行けるマスに現在のマス+1を書き込んでいきGはいくつになるかを求める。
- このように幅優先探索は、現在のマスに近いところから探索していくというアルゴリズム
一般的なグラフでの、幅優先探索のメモ
上記の迷路で見たBFSを一般のグラフとして整理する。まずグラフのスタート意味する頂点sを指定する。
- 頂点sから1手でいける頂点を全て探索する。
- 頂点s+1から1手でいける頂点を全て探索する。
- 頂点s+2から1手でいける頂点を全て探索する。
という探索を「まだ探索していない頂点」がなくなるまで繰り返す。
幅優先探索の実装のメモ
明日提出コードに対してメモを追記
幅優先探索の計算量のメモ
グラフの頂点数をN、辺の数をMとすると計算量はO(M)、つまりグラフの入力を受け取るのと同じ計算量になる。
幅優先探索と深さ優先探索のメモ
FIFO (fast-in first-out)
- 個人的な理解法
- 常にグラフの図を意識しながらコードリーディングしていくと分かりやすい。
- デバッガーを常に弄り出したら考察がうまくいっていない証拠
一般的にキューというデータ構造を用いる。
- キューとは？
- 先に追加したものが、先に削除される。
- キューにデータ1~3が順にあるとして、データ4をpushした後、popすると先頭のデータ1が削除される。
- こちらから現実世界での例を引用するとスーパーマーケットのレジ待ちの行列が挙げられ、人々は列の最後に並び、順番が来るとレジで会計を済ませて列を抜けます。
- 先に追加したものが、先に削除される。
サンプルコード↓
int main()
{
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
int v = q.front();
// 先頭の1が削除される。
q.pop();
}
- 比較対象としてスタックを挙げる
- 最後に追加されたデータが最初に削除されます。
- スタックにデータ1~3があるとして、データ4をpushした後、popするとデータ4が削除される
- こちらから現実世界での例として、皿を積み重ねた状態が挙げられます。新しい皿は上に積まれ、使うときは一番上の皿から取られます
- 最後に追加されたデータが最初に削除されます。
masato_is_a_ snakeグラフ理論
木とは連結でサイクルがないこと。