【書評】問題解決力を鍛える！アルゴリズムとデータ構造
「問題解決力を鍛える！アルゴリズムとデータ構造」を読んだので感想を書く。
問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)
- 作者:大槻 兼資
- 発売日: 2020/10/02
- メディア: 単行本（ソフトカバー）
書籍の概要と感想
待ちに待った、けんちょんさんの「問題解決力を鍛える！アルゴリズムとデータ構造」。ページを進めるたびに感動する。絵がたくさんあって、解説コードもたくさんあって、超絶わかりやすい!!! いくつかページを載せたいくらいだけど、載せられないので書き記すと、個人的に特にわかりやすかったところは、
- 設計技法
- 再帰
- DP
- にぶたん
- 貪欲
- データ構造
- グラフと木
- Union-Find
- グラフ
結局全部！っていう。それくらいどの章も絵とコードによる説明があって非常によかった。まだ始めたばかりで、グラフについてはおぼろげな感じで、この書籍を読んで理解が深まったので、実際に実装を踏まえて身につけていきたい。 また、競技プログラミングはPythonかJuliaでやっているので、C++をほぼ知らないが、それでもC++のハンドリング覚えられるくらい丁寧に書かれているのもよかった。（副産物的にC++の基本がおさえられて個人的にはよかった。）
難易度てきには広くおさえられていて、全体的にこのくらいは知ってましょうねって言う感じなんだと思うので初心者~中級者向けって言うところなんだと思う。
ご本人が書籍のターゲットとか難易度とかも記しているのでそちらの方が確かかも。
章末問題の概要
章末問題を解いたものの別記事載せて、その章ごとに概要を追記していく。 とりあえず３章から別記事にて実際にコードを書く。
第１章 アルゴリズムとは
深さ優先探索や幅優先探索・マッチングなどの具体的な例をだして、アルゴリズムの解説がされている。ここで、「問題に対する具体的な解を書き下すことができなくても解を得るための「手順」を与えることができればよい」ということが書かれていて、たしかにそうだなぁと思った。
第２章 計算量とオーダー記法
計算量の計算の解説が具体例と共にめちゃわかりやすく書かれている。
たとえば、年齢当てゲームで、線形探索でやった場合と二分探索で0歳以上65536歳未満を範囲とした時に、最悪ケースの回数には大きな差があることを紹介している。
また１秒間で処理できる処理数はC++では程度らしい。（CPUにもよるだろうが著者はMacBook Air Early2015でやっているようだ。）自分の環境ではPythonでは
程度。(MacBook Pro Late 2016）
特にいい表は表2.2で、CPUなどにも左右されるが、競技プログラミング的な制約では処理数としてPythonではを超えそうならTLEと思ってた方が無難。（numpyなどその他の高速化をすれば別だけど。）なので、実際に使う言語などで、処理数を考えて
でやらなきゃなのか
でやらなきゃなのかなどを考える指標になる。
第３章 設計技法(1)：全探索
詳細は、以下の記事に書いた。
線形探索・ペアの探索・組み合わせの探索について取り扱っていて、組み合わせの探索はbitを使うので、初心者は慣れないとちょっときつい。
第４章 設計技法(2)：再帰と分割統治法
詳細は、以下の記事に書いた。
ベースケース（再帰の呼び出しを行わないでreturnするケースのこと）の処理に気をつけて、実装することを心がける。最大公約数の関数を作るときなどに再帰を使うといい。
第５章 設計技法(3)：動的計画法
詳細は、以下の記事に書いた。
DPの漸化式、初期条件を問題の制約に合わせて上手に設計することがポイント。せめて２重のリストで対応できるようになると解ける問題の幅が膨らむ。
第６章 設計技法(4)：二分探索法
詳細は、以下の記事に書いた。
複数の配列があるなど、探索する量が多い時は、複数の配列の１つを固定する、2つにまとめるなど、うまく工夫が必要。
問題に合わせてbisectで作ることができるチェック用の関数を作ると楽、例えば、
- リストからx以下の最大値を得る関数
- x以下の積の数がk個以上あるかを判定する関数
第７章 設計技法(5)：貪欲法
詳細は、以下の記事に書いた。
ポイントとしては、
- 貪欲は未来のことは考えず、すぐ次のステップのことだけ考えて今の最善を繰り返し行うことなので比較的イメージしやすい。
- 貪欲が必ずしも最善とは限らないことがあるので注意（今の選択が未来の選択に影響してしまう場合など）
まだ章末問題やっている最中の章
以下の章はまだ別記事でまとめてないので保留。
ここからあとは、AtCoderで問題が解けるものを基本扱うようにする。
誰かが、各章の入力と正解アウトプットの例をいくつか作ってくれたら実装する。
別件で忙しいのでしばらくは更新しない。
第８章 データ構造(1)：配列、連結リスト、ハッシュテーブル
第９章 データ構造(2)：スタックとキュー
第１０章 データ構造(3)：グラフと木
第１１章 データ構造(4)：Union-Find
第１２章 ソート
第１３章 グラフ(1)：グラフ探索
第１４章 グラフ(2)：最短路問題
第１５章 グラフ(3)：最小全域木問題
第１６章 グラフ(4)：ネットワークフロー
第１７章 PとNP
第１８章 難問対策
終わりに
書籍に関しては、めっちゃわかりやすくて期待通り。自分がAtCoderはじめて間もないタイミングでこの本を読めることはめっちゃよかった。
問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)
- 作者:大槻 兼資
- 発売日: 2020/10/02
- メディア: 単行本（ソフトカバー）
現状、章末問題をPythonでこなしていこうと思っている。難易度が高いものはテータ構造・グラフあたりから厳しくなりそうだがやれるだけやってみる。
あと正直なところ、これとは別に初心者向けに、競技プログラミングに必要な数学知識実践編的な物が欲しい。個人的にはまとめているが、数学的に当たり前みたいなものが、ガンガンでてきて「知らんがな」「気づかねー」ってなることが結構あって、どうすればいいのかなーと思っている。
お願い（欲しい書籍リスト）
ずうずうしいのですが、ブログを続けるのも大変で、基本自分の学習メモのためですが、サポーター募集です。ポチッとしてくれると嬉しいです。
https://www.amazon.jp/hz/wishlist/ls/2EDNNTYRW2BJE?ref_=wl_share
もしくは、レビューなど書くので、献本していただけたらものすごく喜びます（お問い合わせ or TwitterのDMからお問い合わせ下さい。）
