雑に読む「問題解決力を鍛える！アルゴリズムとデータ構造」

2020

注意：章末問題の回答が書いてある可能性があります（あっている保証はないです）

何日かに1回読む

コードはマネでもいいから書く

本書はC++になっているけどGoかTypeScriptで書こうかな。

実例大事

著者の補足資料

前書き

1,2で準備して、3-7はいきなりこの本の核心である設計技法

https://gyazo.com/40d2a2766f3e4e16edaa0dff19cc0afc

理解を試す問題の難易度説明

std::sort()の計算量がO(NlogN)であることが仕様として保証されていること (p.14). Kindle 版.

基本はクイックソートで平均O(nlogn)

std::sort()の計算量は平均の話？

最悪ケースでどうかを議論したりすることもある

3.1 全探索を学ぶ意義

遅くてもNが十分小さいなら実用できる

問題が深く理解できて高速なアルゴリズム設計に結びつく

どうしたら全ての場合を考慮し尽くせるかを検討するのは有効

3.3 線形探索法の応用

3.6 まとめ

4.1 再帰とは

4.5 再帰の例(3)：再帰関数を用いた全探索

4.6 分割統治法

4.7 まとめ

対象が文字列だろうがグラフだろうが点群だろうが動的計画法は使われうる、抽象度の高い概念

5.1 動的計画法とは

5.2 最初の例題

5.3 動的計画法に関連する諸概念

5.7 まとめ

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.9 まとめ

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.9 まとめ

11.1 Union-Findとは

11.2 Union-Findの仕組み

11.3 Union-Findの計算量を削減する工夫

11.6 Union-Findの実装

11.7 Union-Findの応用：グラフの連結成分の個数

11.8 まとめ

12.1 ソートとは

12.2 ソートアルゴリズムの良し悪し

https://youtu.be/QJcU7jO5HZ8

ソートして返すAPIがソートしなくなったら高速化した話

例: クイックソートのアルゴリズムを書いてください。

クイックソートの時間計算量は何ですか？

どのようなときに平均計算量になりますか？

どのようなときに最悪計算量になりますか？

ピボットはどのように選びますか？

再帰をする場合、どのようなことに気を付けますか？

定数倍高速化したい場合、どのような工夫をしますか？

12.7 ソートの計算量の下界

12.9 まとめ

13.1 グラフ探索を学ぶ意義

13.3 再帰関数を用いる深さ優先探索

13.5 最短路アルゴリズムとしての幅優先探索

13.6 深さ優先探索と幅優先探索の計算量

13.7 グラフ探索例(1)：s-tパスを求める

13.11 まとめ

14.1 最短路問題とは

14.2 最短路問題の整理

14.3 緩和

14.4 DAG上の最短路問題：動的計画法

14.9 まとめ

15.1 最小全域木問題とは

15.3 クラスカル法の実装

15.5 クラスカル法の正当性

15.6 まとめ

16.1 ネットワークフローを学ぶ意義

16.8 まとめ

17章 PとNP

17.1 問題の難しさの測り方

17.2 PとNP

17.8 まとめ

18章 難問対策

18.1 NP困難問題との対峙

18.2 特殊ケースで解ける場合

18.7 近似アルゴリズム

18.8 まとめ

この本が終わったら