くろたんく雑記帳

日常とか、わんちゃんとか、機械学習とか、競プロとか、

MENU

【書評】問題解決力を鍛える!アルゴリズムとデータ構造

「問題解決力を鍛える!アルゴリズムとデータ構造」を読んだので感想を書く。

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

  • 作者:大槻 兼資
  • 発売日: 2020/10/02
  • メディア: 単行本(ソフトカバー)


書籍の概要と感想

待ちに待った、けんちょんさんの「問題解決力を鍛える!アルゴリズムとデータ構造」。ページを進めるたびに感動する。絵がたくさんあって、解説コードもたくさんあって、超絶わかりやすい!!! いくつかページを載せたいくらいだけど、載せられないので書き記すと、個人的に特にわかりやすかったところは、

  • 設計技法
    • 再帰
    • DP
    • にぶたん
    • 貪欲
  • データ構造
    • グラフと木
    • Union-Find
  • グラフ

結局全部!っていう。それくらいどの章も絵とコードによる説明があって非常によかった。まだ始めたばかりで、グラフについてはおぼろげな感じで、この書籍を読んで理解が深まったので、実際に実装を踏まえて身につけていきたい。 また、競技プログラミングPythonかJuliaでやっているので、C++をほぼ知らないが、それでもC++のハンドリング覚えられるくらい丁寧に書かれているのもよかった。(副産物的にC++の基本がおさえられて個人的にはよかった。)

難易度てきには広くおさえられていて、全体的にこのくらいは知ってましょうねって言う感じなんだと思うので初心者~中級者向けって言うところなんだと思う。

ご本人が書籍のターゲットとか難易度とかも記しているのでそちらの方が確かかも。

drken1215.hatenablog.com


章末問題の概要

章末問題を解いたものの別記事載せて、その章ごとに概要を追記していく。 とりあえず3章から別記事にて実際にコードを書く。

第1章 アルゴリズムとは

深さ優先探索幅優先探索・マッチングなどの具体的な例をだして、アルゴリズムの解説がされている。ここで、「問題に対する具体的な解を書き下すことができなくても解を得るための「手順」を与えることができればよい」ということが書かれていて、たしかにそうだなぁと思った。


第2章 計算量とオーダー記法

計算量の計算の解説が具体例と共にめちゃわかりやすく書かれている。 たとえば、年齢当てゲームで、線形探索でやった場合と二分探索で0歳以上65536歳未満を範囲とした時に、最悪ケースの回数には大きな差があることを紹介している。 また1秒間で処理できる処理数はC++では{\displaystyle 10^9}程度らしい。(CPUにもよるだろうが著者はMacBook Air Early2015でやっているようだ。)自分の環境ではPythonでは{\displaystyle 1.5 \times 10^7}程度。(MacBook Pro Late 2016)

特にいい表は表2.2で、CPUなどにも左右されるが、競技プログラミング的な制約では処理数としてPythonでは{\displaystyle 3 \times 10^7}を超えそうならTLEと思ってた方が無難。(numpyなどその他の高速化をすれば別だけど。)なので、実際に使う言語などで、処理数を考えて {\displaystyle O(n)}でやらなきゃなのか{\displaystyle O(log(n))}でやらなきゃなのかなどを考える指標になる。


第3章 設計技法(1):全探索

詳細は、以下の記事に書いた。

blacktanktop.hatenablog.com

線形探索・ペアの探索・組み合わせの探索について取り扱っていて、組み合わせの探索はbitを使うので、初心者は慣れないとちょっときつい。


第4章 設計技法(2):再帰と分割統治法

詳細は、以下の記事に書いた。

blacktanktop.hatenablog.com

ベースケース(再帰の呼び出しを行わないでreturnするケースのこと)の処理に気をつけて、実装することを心がける。最大公約数の関数を作るときなどに再帰を使うといい。


第5章 設計技法(3):動的計画法

詳細は、以下の記事に書いた。

blacktanktop.hatenablog.com

DPの漸化式、初期条件を問題の制約に合わせて上手に設計することがポイント。せめて2重のリストで対応できるようになると解ける問題の幅が膨らむ。


第6章 設計技法(4):二分探索法

詳細は、以下の記事に書いた。

blacktanktop.hatenablog.com

複数の配列があるなど、探索する量が多い時は、複数の配列の1つを固定する、2つにまとめるなど、うまく工夫が必要。
問題に合わせてbisectで作ることができるチェック用の関数を作ると楽、例えば、

  • リストからx以下の最大値を得る関数
  • x以下の積の数がk個以上あるかを判定する関数

第7章 設計技法(5):貪欲法

詳細は、以下の記事に書いた。

blacktanktop.hatenablog.com

ポイントとしては、

  • 貪欲は未来のことは考えず、すぐ次のステップのことだけ考えて今の最善を繰り返し行うことなので比較的イメージしやすい。
  • 貪欲が必ずしも最善とは限らないことがあるので注意(今の選択が未来の選択に影響してしまう場合など)

まだ章末問題やっている最中の章

以下の章はまだ別記事でまとめてないので保留。
ここからあとは、AtCoderで問題が解けるものを基本扱うようにする。
誰かが、各章の入力と正解アウトプットの例をいくつか作ってくれたら実装する。
別件で忙しいのでしばらくは更新しない。

第8章 データ構造(1):配列、連結リスト、ハッシュテーブル
第9章 データ構造(2):スタックとキュー
第10章 データ構造(3):グラフと木
第11章 データ構造(4):Union-Find
第12章 ソート
第13章 グラフ(1):グラフ探索
第14章 グラフ(2):最短路問題
第15章 グラフ(3):最小全域木問題
第16章 グラフ(4):ネットワークフロー
第17章 PとNP
第18章 難問対策

終わりに

書籍に関しては、めっちゃわかりやすくて期待通り。自分がAtCoderはじめて間もないタイミングでこの本を読めることはめっちゃよかった。

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

  • 作者:大槻 兼資
  • 発売日: 2020/10/02
  • メディア: 単行本(ソフトカバー)

現状、章末問題をPythonでこなしていこうと思っている。難易度が高いものはテータ構造・グラフあたりから厳しくなりそうだがやれるだけやってみる。

あと正直なところ、これとは別に初心者向けに、競技プログラミングに必要な数学知識実践編的な物が欲しい。個人的にはまとめているが、数学的に当たり前みたいなものが、ガンガンでてきて「知らんがな」「気づかねー」ってなることが結構あって、どうすればいいのかなーと思っている。


お願い(欲しい書籍リスト)

ずうずうしいのですが、ブログを続けるのも大変で、基本自分の学習メモのためですが、サポーター募集です。ポチッとしてくれると嬉しいです。

https://www.amazon.jp/hz/wishlist/ls/2EDNNTYRW2BJE?ref_=wl_share

もしくは、レビューなど書くので、献本していただけたらものすごく喜びます(お問い合わせ or TwitterのDMからお問い合わせ下さい。)