読者です 読者をやめる 読者になる 読者になる

アルゴリズムとデータ構造

MIT Open Coursewareが終わったので、次は積ん読になっていたこれ。

プログラミングの宝箱 アルゴリズムとデータ構造 第2版

プログラミングの宝箱 アルゴリズムとデータ構造 第2版

ほぼ写経になってしまうが、備忘のため貼付けていく。

ソート

バブルソート

クイックソート

マージソート

検索

イナリサーチ

文字列検索

BM法

探索

深さ優先探索(バックトラック法)

f:id:kotaroito2002:20140212114129p:plain

再帰を利用して深さ優先で試行し、ダメだったら直前の分岐まで戻る。

幅優先探索

f:id:kotaroito2002:20140212114234p:plain

キューを利用して幅優先で試行し、ダメだったら次のキューを試す。

動的計画法

「全体を小問題に分割し、小問題の解を利用して目的の問題を解く」と言えるかな。小問題の回答が載っている表を参照しながら、順次アップデートしていくようなイメージ。

ナップザック問題

ダイクストラ