tech-book.net

ISBN 9784065128442

問題解決力を鍛える！アルゴリズムとデータ構造

問題解決力を鍛える！アルゴリズムとデータ構造
著者
大槻 兼資/秋葉 拓哉
出版社
講談社
刊行
2020-10
楽天ブックス → Amazon 紙版 → Kindle → 紀伊國屋書店 → honto →
Amazonアソシエイトおよび楽天アフィリエイト等の広告リンクを含みます。Amazonのアソシエイトとして tech-book.net は適格販売により収入を得ています。 詳細

概要

競技プログラミングを題材にアルゴリズム設計技法を実践的に習得する

想定読者

AtCoderを通じてアルゴリズムを道具として使える状態を目指すエンジニア・学生。特にC++で実装しながら設計技法を体得したい層

こんな人には向いていない

  • AtCoderで青〜黄以上のレーティングを持つ競技者には既知の内容が多く、復習以上の価値を得にくい
  • PythonやJavaなど、C++以外の言語で完結させたい読者はサンプルコードの言語差を自力で埋める必要があり、補助資料の併用が前提になる
  • アルゴリズムの数学的証明や理論的厳密性を重視するCS学術書として使いたい読者には記述の粒度が合わない

この本で身につくこと

  • O記法を用いて複数のアルゴリズムの計算量を定量的に比較・評価できる
  • 全探索・動的計画法・貪欲法・二分探索などの設計技法を問題のパターンに対応付けて選択できる
  • ヒープ・ハッシュテーブル・木構造などのデータ構造をC++標準ライブラリと対応付けて理解・活用できる
  • BFS/DFSおよびダイクストラ法・クラスカル法などのグラフアルゴリズムを実装できる
  • P/NP問題の概念を把握し、解くのが困難な問題に動的計画法や貪欲法での変換・近似を試みる設計判断ができる

ハイライト(外部からの言及)

現実世界の問題を解決するための実践的なアルゴリズム設計技法の鍛錬を目指しています — 出典

多くの書籍が設計技法を巻末に置くのに対し、本書が3〜7章という前半から設計技法に注力する構成意図が端的に表れている

どのようにすれば効率のよい結果が得られるか？　すなわちどのようなアルゴリズムを採用すればよいか？　という点に対して、幅広くかつ明快に解説している — 出典

国立情報学研究所副所長・河原林健一氏による推薦文。「幅広く、かつ明快に」という評価が本書の性格を端的に示している

僕は、アルゴリズムの面白さ・考え方を伝える記事を、Qiita 上に多数執筆してきました。それらを有機的にまとめあげる形で、アルゴリズム本を出版しました。 — 出典

著者(drken)自身の言葉。本書がQiita上で読者に検証された解説群を集約した書籍であることを示す。既存2件が「本書の構成意図」「第三者専門家評価」を扱うのに対し、本書の成り立ちと著者の姿勢という独立した角度を補完する

読了後にできること

Before(読む前): AtCoderの問題を前にして、どの設計技法を選べばよいかわからず、TLEを出しながら力任せの全探索しか書けない

After(読み終えた後): 問題の構造を見て動的計画法・BFS・貪欲法などの設計技法を当てはめる判断ができ、水色〜青色レベルの問題に対応できる

章立て

第1章 アルゴリズムとは

本書全体の問題設定と編集方針を整理する導入

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

Big-O 表記の体系的解説。後続章を理解する前提

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

競プロでも実務でも最初に検討する素朴解。本書は理論と実装を地続きで扱う

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

マージソート・FFT 等の前提となる設計法

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

本書の中核章の 1 つ。状態定義・遷移の言語化方法を学ぶ

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

「答えで二分探索」する発想が競プロの頻出パターン。while ループの境界条件と不変量の設定が典型的な詰まりポイントであり、本章を確実に理解しないと後半の応用問題で繰り返し躓く

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

「局所最適が大域最適になる」条件の見極めが難しく、証明なしに適用すると誤りになる。交換論法を用いた正当性の議論を意識しながら読むと、本番で誤適用するミスが減る

第8章 データ構造(1): 配列、連結リスト、ハッシュテーブル

C++ STL の vector / unordered_map との対応で解説される。実装手間よりも計算量特性の差異を掴むことが本章の主眼

第9章 データ構造(2): スタックとキュー

後続のグラフ章(13〜16章)で BFS / DFS の実装基盤として多用される。本章で stack / queue の操作感を手を動かして確認しておくと詰まりが減る

第10章 データ構造(3): グラフと木

隣接リスト表現と木の概念定義を押さえる章。13〜16章のグラフアルゴリズムはここで定義した用語・表現形式を前提とするため、曖昧なまま先に進まない

第11章 データ構造(4): Union-Find

競プロ頻出。実装簡潔さと応用範囲のバランスが本書の独自性

第12章 ソート

比較ベースのソートの下限定理と非比較ソートを扱う。AtCoder では std::sort で足りる場面が多いが、計算量の下限の理解が問題設計の見通しにつながる

第13章 グラフ(1): グラフ探索

BFS / DFS。後続グラフ章すべての前提

第14章 グラフ(2): 最短路問題

Dijkstra / Bellman-Ford / Floyd-Warshall の理論と実装

第15章 グラフ(3): 最小全域木問題

Kruskal / Prim 法。Union-Find と組み合わせる章

第16章 グラフ(4): ネットワークフロー

Ford-Fulkerson / Edmonds-Karp。本書の到達点に近い章

第17章 PとNP

計算複雑性理論の導入。ある意味本書の哲学的な締め

第18章 難問対策

NP 困難問題への近似アルゴリズム・ヒューリスティクス

関連記事 / 参考情報

学習のヒント

  • 3〜7章のアルゴリズム設計技法は著者が意図的に前半に配置した核心部。特に動的計画法(5章)は後半のグラフアルゴリズムでも繰り返し登場するため、理解が曖昧なまま先に進まず、AtCoderの関連問題を数問解いてから次章へ進む往復学習が効果的
  • 本書はC++前提だが、PythonユーザーはQiitaのけんちょん本 to Pythonシリーズ(KevinST)と章単位のPython実装記事(eyuta)を補助資料として併用すると言語の壁を低くできる
  • AtCoderのBeginner Contestと並行して読むと、各章で学んだ設計技法を即日実問題で試せる。1章学んだら1〜2問解くという往復が最も定着率が高い
  • 17〜18章のP/NP・難問への対処はCS的教養として価値があるが、競技プログラミングの即戦力としての優先度は低い。初読では流し読みし、実際にNP困難な問題に直面したときに戻る使い方が現実的

前提知識

  • C++またはPythonで条件分岐・繰り返し・関数を含む基本的なプログラムが書ける
  • 高校数学レベルの論理的思考(数列・集合・帰納法的な考え方)があれば計算量の議論についていける
  • 競技プログラミングの経験は不要だが、AtCoderのアカウント登録とABC-A問題を1〜2問解いておくと本書サンプル問題の文脈が把握しやすい

次に読む本

競技プログラミングの鉄則

本書が設計技法の体系的理解を目的とするのに対し、『競技プログラミングの鉄則』は AtCoder 典型問題を 90 問に絞り反復演習に特化している。本書でアルゴリズムの原理を押さえた後に移行することで、パターン認識と解法選択のスピードを効率よく強化できる

プログラミングコンテストチャレンジブック(蟻本)

本書が AtCoder 中級レベルまでをカバーするのに対し、蟻本は国際情報オリンピック・ACM-ICPC レベルを念頭に置いた上中級演習書。本書で設計技法を体得した後、より高難度の問題群を通じて実装力と応用力を鍛える段階で参照する

アルゴリズムイントロダクション

本書が実装と直感的理解を優先するのに対し、アルゴリズムイントロダクションは各アルゴリズムの正確さ・計算量の数学的証明を提供する CS 教科書。本書でアルゴリズムの動作を理解した後、証明の厳密さが業務・研究で必要になった時点で参照する使い方が現実的

出版社による内容紹介

◆2万部突破のベストセラー！みんな読んでる！◆ ◆「 ITエンジニア本大賞2021 特別賞」受賞◆ 競技プログラミング経験が豊富な著者が、「アルゴリズムを自分の道具としたい」という読者に向けて執筆。入門書を標榜しながら、AtCoderの例題、C++のコードが充実。入門書であり実践書でもある、生涯役立つテキストを目指した。 【推薦の言葉】 プログラムが「書ける」ことと、効率の良い結果を得ることには大分ギャップがある。本書は、どのようにすれば効率のよい結果が得られるか？　すなわちどのようなアルゴリズムを採用すればよいか？　という点に対して、幅広くかつ明快に解説している。 また本書は、アルゴリズム初心者に対して、アルゴリズムへの興味を惹かれるように記述されている。アルゴリズム上級者への初めの一歩には最適であろう。 ーー河原林健一（国立情報学研究所副所長） 【全体を通して、アルゴリズムの設計技法を重視した構成】 まず、1、2章でアルゴリズムと計算量について概観します。そして、3〜7章が、早くも本書のメインパートといえる部分であり、「アルゴリズムの設計技法」について詳しく解説します。これらの設計技法に関する話題は、多くの書籍では、最後の方で簡単に説明しています。しかし本書は、現実世界の問題を解決するための実践的なアルゴリズム設計技法の鍛錬を目指しています。そこで、アルゴリズム設計技法について前半で詳しく解説する構成としました。そして、これらの設計技法が後半の章でも随所に使われていくことを示していきます。 その後、8〜11章では、設計したアルゴリズムを効果的に実現するうえで重要となるデータ構造を解説します。データ構造について学ぶことで、アルゴリズムの計算量を改善したり、また、C++やPythonなどで提供されている標準ライブラリの仕組みを理解して、それらを有効に活用したりすることができるようになります。 そしていったん、12章でソートアルゴリズムについての話題を挟んだ後に、13〜16章でグラフアルゴリズムについて解説します。グラフは、非常に強力な数理科学的ツールです。多くの問題は、グラフに関する問題として定式化することで、見通しよく扱うことができるようになります。また、グラフアルゴリズムを設計するとき、3〜7章で学ぶ設計技法や、8〜11章で学ぶデータ構造が随所で活躍します。 最後に、17章で PとNPに関する話題を解説し、世の中には「効率的に解くアルゴリズムを設計することができそうにない難問」が多数あることを見ます。18章で、これらの難問に取り組むための方法論をまとめます。ここでも、動的計画法 (5章) や貪欲法 (7章) といった設計技法が活躍します。

この本がどの学習段階で役立つかは、 関連する ロードマップ から確認できます。

質問に答えるだけで、
あなたに合う専門書が見つかる

IT・デザイン・士業・医療・経理・教育・研究 ほか、あらゆる分野の専門書と 「読む順序」(学習ロードマップ)を収録。何を選べばいいか分からなくても、 いくつかの質問に答えるだけでたどり着けます。

読む順序で設計する考え方を見る → データから読み解くストーリー →