問題解決力を鍛える!アルゴリズムとデータ構造(モンダイカイケツリョクヲキタエル!アルゴリズムトデータコウゾウ)

◆ 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 章) といった設計技法が活躍します。

アルゴリズムの教科書を読み終えたのに、初見の問題を前にすると何も思いつかない。この「知識はあるのに設計できない」状態に正面から効くのが『問題解決力を鍛える! アルゴリズムとデータ構造』 (大槻兼資 著、秋葉拓哉 監修、講談社、 2020 年刊、 A5 判 368 ページ) です。監修の秋葉拓哉氏は 競技プログラミング の定番書『プログラミングコンテストチャレンジブック』 (通称・蟻本) の共著者でもあり、本書は版元言明で 2 万部を超えたベストセラー、エンジニア投票の IT エンジニア本大賞 2021 では特別賞を受けています。国立情報学研究所副所長 (刊行時) の河原林健一氏が推薦を寄せる、学術と実践の両方から支持された一冊です。

設計技法を前半に置く章立て

最大の特徴は章立ての順番にあります。多くの教科書がソートやデータ構造の各論から入り、設計技法を最後に軽く触れるのに対し、本書は 1 〜 2 章で 計算量 の考え方を押さえたら、 3 〜 7 章の「アルゴリズム設計技法」を早くもメインパートとして据えます。版元の紹介文にあるとおり、多くの書籍が最後に簡単に触れるだけのこの話題を前半で徹底的に鍛えることで、個別のアルゴリズムを暗記する前に「初見の問題をどの型に落とすか」という思考の筋肉を作り、 8 〜 11 章のデータ構造、 12 章のソート、 13 〜 16 章のグラフアルゴリズムでも、その設計技法が随所で再登場することを確かめていく構成です。問題を解く順に学ぶから、知識が道具になります。

AtCoder の例題と C++ で確かめる作り

例題には AtCoder の問題が使われ、コードは C++ で示されます。実際にジャッジへ提出して確かめながら進められるので、読了と実力の乖離が起きにくい作りです。数式は使いますが、大学の教科書のような証明中心ではなく、実装と例題で納得させる中間の水準に調整されています。書名の「問題解決力」は誇張ではなく、現実の問題をグラフや 動的計画法 の問題として定式化し直す訓練が本書の一貫した狙いです。

前提知識と対象読者

対象は、プログラミングの基本 (ループ・配列・関数) を習得済みで、アルゴリズムを体系的に学び直したい学生・エンジニア、競技プログラミングの序盤から中盤へ進みたい人、コーディング面接に備えたい人です。 C++ 以外の言語しか書けない場合も、コードは読み替え可能な水準ですが、写経の快適さを重視するなら C++ の初歩だけ先に押さえると滑らかです。より競技特化の演習量が欲しければ『競技プログラミングの鉄則』が、その先の到達点として蟻本が続きます。

アルゴリズム学習は「読んだ」で終わると数か月で蒸発しますが、設計技法の型として身につけると、業務のパフォーマンス改善からコーディング面接まで、長期間にわたって配当が出続けます。日本語で書かれたアルゴリズム入門の水準を一段引き上げたと評されることの多い本書は、その投資の最初の一冊として揺るがない選択です。