雑に読む「問題解決力を鍛える！アルゴリズムとデータ構造」
雑に読む「達人に学ぶDB設計徹底指南書」にインスパイアされた
2020
注意：章末問題の回答が書いてある可能性があります（あっている保証はないです）
目標
何日かに1回読む
コードはマネでもいいから書く
本書はC++になっているけどGoかTypeScriptで書こうかな。
Wandboxとかを使えば、C++でも環境構築なしに試せる
実例大事
使えないと意味ない(過激派)
著者の補足資料
アルゴ式というサイトは、この本をベースに問題を作成している
著者らの立ち上げた会社だ
前書き
アルゴリズム設計技法を大切にしている本らしい
1,2で準備して、3-7はいきなりこの本の核心である設計技法
理解を試す問題の難易度説明
星4（難しいが理解が格段に深まる）まで解けたらいいなー
>std::sort()の計算量がO(NlogN)であることが仕様として保証されていること (p.14). Kindle 版.
Goだとどうなるの？
基本はクイックソートで平均O(nlogn)
std::sort()の計算量は平均の話？
「平均が」と書いてない本の側が悪い
最悪ケースでどうかを議論したりすることもある
本書での「計算量」は最悪時間計算量らしい（後から出てくる）けどここは違うのかも
クイックソートの最悪計算量はO(N^2)の気がするけどなぁ
3章 設計技法(1)：全探索
3.1 全探索を学ぶ意義
遅くてもNが十分小さいなら実用できる
問題が深く理解できて高速なアルゴリズム設計に結びつく
どうしたら全ての場合を考慮し尽くせるかを検討するのは有効
3.2 全探索(1)：線形探索法
3.3 線形探索法の応用
3.4 全探索(2)：ペアの全探索
3.5 全探索(3)：組合せの全探索
3.6 まとめ
4.1 再帰とは
4.2 再帰の例(1)：ユークリッドの互除法
4.3 再帰の例(2)：フィボナッチ数列
4.4 メモ化して動的計画法へ
4.5 再帰の例(3)：再帰関数を用いた全探索
4.6 分割統治法
4.7 まとめ
5章 設計技法(3)：動的計画法
よく見るやつ
過去の計算結果を利用して全体の計算量を減らす系のアルゴリズムの多くに動的計画法って名前がついてるので一般的に説明しづらい
対象が文字列だろうがグラフだろうが点群だろうが動的計画法は使われうる、抽象度の高い概念
5.1 動的計画法とは
5.2 最初の例題
5.3 動的計画法に関連する諸概念
5.4 動的計画法の例(1)：ナップサック問題
5.5 動的計画法の例(2)：編集距離
5.6 動的計画法の例(3)：区間分割の仕方を最適化
5.7 まとめ
6章 設計技法(4)：二分探索法
6.1 配列の二分探索
6.2 C++のstd::lower bound()
6.3 一般化した二分探索法
6.4 さらに一般化した二分探索法
6.5 応用例(1)：年齢当てゲーム
6.6 応用例(2)：std::lower bound() の活用例
6.7 応用例(3)：最適化問題を判定問題に
6.8 応用例(4)：メディアンを求める
6.9 まとめ
7章 設計技法(5)：貪欲法
7.1 貪欲法とは
7.2 貪欲法が最適解を導くとは限らないこと
7.3 貪欲法パターン(1)：交換しても悪化しない
7.4 貪欲法パターン(2)：現在がよいほど未来もよい
7.5 まとめ
8.1 データ構造を学ぶ意義
8.2 配列
8.3 連結リスト
8.4 連結リストの挿入操作と削除操作
8.5 配列と連結リストの比較
8.6 ハッシュテーブル
8.7 まとめ
9.1 スタックとキューの概念
9.2 スタックとキューの動作と実装
9.3 まとめ
10.1 グラフ
10.2 グラフの例
10.3 グラフの実装
10.4 重み付きグラフの実装
10.5 木
10.7 二分木を用いるデータ構造の例(1)：ヒープ
10.8 二分木を用いるデータ構造の例(2)：二分探索木
10.9 まとめ
11章 データ構造(4)：Union-Find
11.1 Union-Findとは
11.2 Union-Findの仕組み
11.3 Union-Findの計算量を削減する工夫
11.4 Union-Findの工夫その1：union by size
11.5 Union-Findの工夫その2：経路圧縮
11.6 Union-Findの実装
11.7 Union-Findの応用：グラフの連結成分の個数
11.8 まとめ
12章 ソート
12.1 ソートとは
12.2 ソートアルゴリズムの良し悪し
ソートして返すAPIがソートしなくなったら高速化した話
12.3 ソート(1)：挿入ソート
12.4 ソート(2)：マージソート
12.5 ソート(3)：クイックソート
>例: クイックソートのアルゴリズムを書いてください。
>クイックソートの時間計算量は何ですか？
>どのようなときに平均計算量になりますか？
>どのようなときに最悪計算量になりますか？
>ピボットはどのように選びますか？
> 再帰をする場合、どのようなことに気を付けますか？
>定数倍高速化したい場合、どのような工夫をしますか？
12.6 ソート(4)：ヒープソート
12.7 ソートの計算量の下界
12.8 ソート(5)：バケットソート
12.9 まとめ
13章 グラフ(1)：グラフ探索
13.1 グラフ探索を学ぶ意義
13.3 再帰関数を用いる深さ優先探索
13.5 最短路アルゴリズムとしての幅優先探索
13.6 深さ優先探索と幅優先探索の計算量
13.7 グラフ探索例(1)：s-tパスを求める
13.8 グラフ探索例(2)：二部グラフ判定
13.9 グラフ探索例(3)：トポロジカルソート
13.10 グラフ探索例(4)：木上の動的計画法
13.11 まとめ
14章 グラフ(2)：最短路問題
14.1 最短路問題とは
14.2 最短路問題の整理
14.3 緩和
14.4 DAG上の最短路問題：動的計画法
14.5 単一始点最短路問題：ベルマン・フォード法
14.6 単一始点最短路問題：ダイクストラ法
14.7 全点対間最短路問題：フロイド・ワーシャル法
14.9 まとめ
15章 グラフ(3)：最小全域木問題
15.1 最小全域木問題とは
15.2 クラスカル法
15.3 クラスカル法の実装
15.4 全域木の構造
15.5 クラスカル法の正当性
15.6 まとめ
16章 グラフ(4)：ネットワークフロー
16.1 ネットワークフローを学ぶ意義
16.2 グラフの連結度
16.4 フォード・ファルカーソン法の実装
16.5 応用例(1)：二部マッチング
16.6 応用例(2)：点連結度
16.7 応用例(3)：プロジェクト選択問題
16.8 まとめ
17章 PとNP
17.1 問題の難しさの測り方
17.2 PとNP
17.3 P ≠ NP予想
17.4 NP完全
17.5 多項式時間帰着の例
17.6 NP困難
17.7 停止性問題
17.8 まとめ
18章 難問対策
これは何？
競プロ対策とか？
いやこれ競プロに出せない系では
18.1 NP困難問題との対峙
18.2 特殊ケースで解ける場合
18.3 貪欲法
18.5 分枝限定法
18.6 整数計画問題への定式化
18.7 近似アルゴリズム
18.8 まとめ
この本が終わったら
辞書だなぁ
なにこれ？w