【アルゴリズムとデータ構造】復習day3

やかんです。

OSの復習と異なり、アルゴリズムとデータ構造の復習はもはや完全に僕のメモと化しています。

すみません。。

積み残し

開番地法の場合、計算の手間が「再計算の回数+1」なことに注意だな。プラス1の部分。

メモリを節約する実装も、まあ当然だけどシンプルだよな。「どうやったら右側と左側に二分できるか」を素直に考えて実装すれば、それが正解だったりする。

トライ木、3分探索木、パトリシア木。どれも、概念自体はシンプルだ。

正直、何で深さ優先探索で強連結成分が求まるかっていうのは説明できない。「深さ優先探索のこんな使い方見つけた人すごい！天才！」っていうお気持ち。

ついでにトポロジカルソートもやってみた。まあ、すごいよね。

使う局面が想像つかないけど、できる。

バケットソートはもう良いでしょう。

まあ、大丈夫じゃないかなあ。解析には対応しきれていない感があるが、まあ許容の範囲内じゃないかな。主観の問題だけど。

再帰方程式は立てられる。あとはもう色々工夫して答えを導出してねっていう話だから、いいか。方程式が立てられればOKや。

実装は都度考えるとして、概念をまずは理解する、、んだけど、概念自体はすごいシンプルだよな。でもこれを実装するのめちゃむずそうだな。。試験が終わったらじっくり取り組んでみよう。ナップサックの問題とか有名だし。

名前が全く直感的でないことで有名な（？）動的計画法。最長共通部分列問題を例に理解を試みる。まあ、概念自体は超シンプルなんだけど、一歩だけ進んで「実際に手を動かせますか？」というところだよな。

お、意外とややこしいな。

表自体は機械的に書けるし、最長共通部分列の取得もそれなりに機械的に可能。が、どうなってる？あ、そんな複雑なことはないわ。OK。

すごい。やろうと思ってたこと一通り終わった。明日試験だけど、試験前は何を見ていようか。

→2019年の過去問の8問目と9問目かな。グラフの探索と、分枝限定法の図解。

ということで、今回の復習は終了。最後までお読みいただき、ありがとうございます。