やかんです。
積み残し
- avl木の各メソッドを再現。 ← done
- 動的計画法の表を描く。
- Aスターとか。← done
- ベルマンフォード法を実装してみてもいいかもしれない。
- 間接点のアルゴリズム。 ← done
2021年と2020年の過去問を解いてみた。
ヒープ
これはもう、「半順序」を強く意識するのみだよな。
ヒープは要するに、「詰まっていて半順序」。
二分探索木
計算量の導出以外は大丈夫なはず。
大丈夫だけど、二分探索木は歯応えあるよなあ。考えるたびに違う特徴というか、側面が見えてくる。面白い。
AVL木
今まで触れてなかったやつや。
- 手順自体は難しくない。まあ、実装は簡単にできないだろうなあ。
ハッシュ
計算量かあー、こいつはわかんねえ。勉強や。
- チェイン法はまあ良い。
- 問題は開番地法の手間だよなあ。見積もりが意外と計算コスト必要だな。
- まずは確率計算。確率は、よくわからなかったら全事象を地道に求めて、対象となる事象の数を地道に数えて割り算してあげればまあ求まるよね。でこれを一般化すればかんぺき。
- DONE
ハッシュは一般に、占有率上がってくると計算の手間が増えるから、一定の占有率を迎えたらハッシュを再構成（バケットの追加）を行うと計算の手間を低く維持できる。
クイックソート
計算量の解析かあ。
- 実装とか図解はできるけど計算量か。。
- 解析めっちゃ簡単だった。図でどうにかなるな。
クイックソート、ポインタを使う場合の復習が必要。前に理解してるから大丈夫だと思うけど。
マージソート
これは図解するときに、一番上に分割済みのデータを表記するのがいいな。
ダイクストラ
- あぶねえ、、ダイクストラ一部勘違いしてた。よかった気づけて。
プリムのアルゴリズム
わかってるつもりでも、いざ手を動かしてみるとできないもんなんだよなあ。
- プリムのアルゴリズムで生成される最小木の子の数は複数でOK。
クラスカルのアルゴリズム
まあ、シンプルだよね。OKと思われる。
文字列の検索
- KMPアルゴリズムとBMアルゴリズムの2つ。
- KMPは一通りやってみた。難しくはない。まあ、表を作るときに注意深くやろうね、くらいかな。
- BMややこしいな。。
- 要は、BMにおいては表を2つ用意しておくと。
分割統治の練習としての長大整数の掛け算
- もう大丈夫なはず。
やることなど
- 二分探索木の計算量の導出を再現したい。 ← done
- ベルマンフォード法を実装してみてもいいかもしれない。 ← 不要
- 動的計画法の表を描く。
- トライ木。
- KMPとBM。← done
- ハッシュの計算量、というか、計算の手間。
- avl木のメソッドもう一度再現したい。
- ハッシュの計算量について再現。
- グラフについては、強連結成分とトポロジカルソートがまだ。それ以外は意外と済んでるんだよな。
あと、2020年の過去問最後まで解けてないから、最後まで解こうか。
ということで、アルゴリズムとデータ構造の試験勉強day2終了。まあ、day2と言いつつ、ちょこちょこ復習とかしてたから実際は何日めかわからないんですけど。
最後までお読みいただき、ありがとうございます。
