アルゴリズムとデータ構造の学習におすすめの本5選 ~競技プログラミングの視点から~

 2022.07.13  株式会社システムインテグレータ

 

アルゴリズムとデータ構造の学習と競技プログラミングは切ってもきれない関係になっています。
本記事では、趣味で競技プログラミングをしている筆者がアルゴリズムとデータ構造を学ぶメリットについて整理したのち、競技プログラミングとの関わりやおすすめの書籍について紹介します。
 

アルゴリズムとデータ構造を学ぶメリット

アルゴリズムとデータ構造を学習するとうれしいことがたくさんあります。以下に列挙します。

論理的思考力や問題解決力が身につく

当ブログの以下の記事でも紹介されていますが、

アルゴリズムとは?プログラミングにおいての重要性、代表的なアルゴリズムの種類を紹介

そもそもアルゴリズムとは、問題を解くための方法や手順を指します。
アルゴリズムを学習する意義は、典型的なアルゴリズムは公式のように使いこなせるようにするだけでなく、プログラミングに限らず、課題に対して適切なアプローチをとるための訓練になることにもあります。
実際のところ、大半のIT企業では実務開発で高度なアルゴリズムそれ自体が要求される場面はそれほど多くないかと思いますが、「課題に対する解決方法の考察と実装が習慣化されている」という点は開発をスピーディに進めたり顧客の要望を取り込む上で大きな強みになります。

数学的な知識や思考力が身につく

「RSA暗号について、巨大な数の素因数分解が難しいことを安全性の根拠にしていることは一応知っているけど、フェルマーの小定理とかは知らない」
という人は結構いるのではないでしょうか。

アルゴリズムと数学は密接に関係しています。
アルゴリズムの学習を通じて、数学の知識や、数学的な考察力を身につけることができます。
ちなみに、私は競技プログラミングを通じてフェルマーの小定理を知りました。

計算量を意識したプログラミングができるようになる

仕事でプログラミングをしている方であっても
「計算量って何?」
「計算量なんて競プロでしか使わんでしょ」
と思っている方は一定数いると思います。

しかし、何も考えずに実装するとパフォーマンスが悪い例は、実は身近に結構あります。
けんちょん氏の以下のQiita記事の説明が非常にわかりやすいです。

特集!知らないと損をする計算量の話

アルゴリズムとデータ構造を学ぶことで必然的に計算量を意識するようになり、適切なデータ構造を用いて効率的に実装できるようになります。

資格試験に役立つ

基本/応用情報技術者試験の午後問題のアルゴリズムで苦労した方はいませんか?

アルゴリズムとデータ構造は、IPAが実施する情報技術者試験の出題範囲にもなっています。
アルゴリズムとデータ構造を学ぶことで、資格試験の際にそれらを得点源にすることができます。アルゴリズムに慣れた競技プログラマが応用情報の午後問題を初見で受けたら受かった、という例もあります。

また、AtCoder株式会社が実施するアルゴリズム実技検定などの民間検定もあります。

就職活動に役立つ場合がある

企業によっては就職試験としてコーディングテストを課す場合があります。
コーディングテストの問題はアルゴリズムを題材としたものが多く、アルゴリズムの勉強は間接的にコーディングテスト対策にもなります。

また、AtCoderなどのプログラミングコンテストサイトでコンテストに参加している場合、面接時に話のネタになったりします。

楽しい

楽しいです。

アルゴリズム学習と競技プログラミングの関係

競技プログラミングとは、参加者に与えられた問題について、その仕様を満足するプログラムをより早く(あるいはより高いスコアが得られるように)記述することを競う競技です。
当ブログの以下の記事でも紹介されています。

競技プログラミングとは?問題例や参加方法なども解説!

「アルゴリズムとデータ構造」の学習と「競技プログラミング」ですが、以下のような理由から、良くも悪くも切っても切れない関係になっています。

アルゴリズムやデータ構造の工夫が問題の解法に直結する

競技プログラミングでは、そのコンテストごとに様々な問題が出題されますが、ここでは短期型のコンテストを例に説明します。

比較的簡単な問題では、題意に沿って for-loop を書くなどして解くことができます。

出典: PG BATTLE 2020 (本年度のPG BATTLEへのリンクはこちら)

この問題では、A、Bそれぞれについて for-loop で合計値を求めることで平均気温を比較することができます。

しかし、難易度が高くなるにつれて、
「単純な for-loop では時間がかかりすぎてしまう問題」
「そもそもどうやって解けば良いのか一見わからない問題」
などが出題されます。

出典: PG BATTLE 2020 (本年度のPG BATTLEへのリンクはこちら)

この問題は、部屋と通路をグラフ理論における頂点と辺とみなし、適切な優先順位に基づいてグラフ上を探索するアルゴリズムを実装することで解くことができます。
解法にもよると思いますが、実装にあたっては

  • 辞書順最小を達成するためのソートアルゴリズムに関する知識
    (ソートは標準ライブラリ等で用意されていることが多く、自力実装は必ずしも必要ではありません)
  • グラフ上の探索を行うアルゴリズム(幅優先探索)に関する知識と実装力
    • 探索に必要なデータ構造(キュー)に関する知識

などが必要になります。
これらのアルゴリズムやデータ構造は MIT の教科書である Introduction to Algorithms にも掲載されていたり、IPAの情報技術者試験の範囲になっていたりします。つまり、競技プログラミングの文脈に限らず、基本的かつ重要なアルゴリズムとしてよく知られているといえます。

競技プログラミングにおいては、こうしたアルゴリズムやデータ構造を適切に考察・実装できるか、できるとすればどれくらい時間の時間で実装できるか、ミスなく実装できるかといった要素が競技性の由来になっています。
そのため、競技プログラミングの実力は、ある種のアルゴリズムやデータ構造に関する知識、実装力に直結しています。また、有名なアルゴリズムの知識によらず、問題自体に対する考察によってアルゴリズムが劇的に改善する場合も多くあり、問題解決のためのアルゴリズムを考える上での実践的な訓練にもなります。

問題演習のための環境が整っている

先述のとおり、競技プログラミングの問題の解法はアルゴリズムとデータ構造に深く関わっています。
これは、競技プログラミングをとっかかりにして多くの有名なアルゴリズムを学ぶことができるということを意味します(もちろん、全てではありません)。

ところで、アルゴリズムに限った話ではありませんが、実際に自分で実装してみたり、演習問題を解いたりすることは学習において重要です。
しかし、自分が使用する言語で実装したアルゴリズムや、自分が解いた演習問題が特殊なケースの入力値も含めて実際に正しく動作するのかを自分で保証することは中々難しく、誰かに採点してほしい気持ちになります。

プログラミングコンテストサイトではジャッジシステムも提供されていることが一般的であるため、競技プログラミングの問題で演習を行うことで、自分が実装したアルゴリズムの採点を効率的に行うことができます。

近年では、コンテストサイトのジャッジシステムと連携し、書籍に掲載されている演習問題の答え合わせができるようになっているものまで出てきています。至れり尽くせりですね。
今後も、このようなアルゴリズム学習と競技プログラミングの関わりは続いていくのではないかと思います。

また、ジャッジシステムを提供するサイトは複数の言語に対応していることも多く、自分の好きな言語で学習を進めることができるのも魅力的です。例えば、AtCoderでは50以上の言語に対応しているほか、他の人の解答を言語別に閲覧できるため、間違えた問題の復習や、より効率的な実装のための参考として活用できます。

アルゴリズムとデータ構造を学ぶのにおすすめの書籍5選

ここまでで、アルゴリズムとデータ構造を学ぶメリットや、競技プログラミングとの関係について紹介してきました。最後に、それらの観点を踏まえた上でのおすすめ書籍を5冊紹介します。
アルゴリズム一般についてより教科書的・体系的に知りたい場合は、アルゴリズムイントロダクションなども候補になってくると思います。

問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本

図が非常にわかりやすく、かつ豊富です。
「整数とは?」「文字式とは?」「関数とは?」「2進法とは?」 といった用語レベルの説明から始まっており、数学的な基礎知識が無い状態から読み進めることができる構成になっています。

全ての初学者にオススメできる良書ですが、とくに、数学に自信が無い大学生や社会人の方々にとっては第一選択になるかと思います。
演習問題の解答をAtCoder上で採点できるようになっている点も非常に魅力的です。
 
 
また、情報科学的な側面から中学、高校数学の範囲も含めて学ぶことが可能な本書の特徴から、プログラミングに興味を持っている中高生が楽しく勉強するための参考書的な使い方もできると思います。
 

アルゴリズム実技検定 公式テキスト[エントリー~中級編]

AtCoder株式会社が実施する検定試験「アルゴリズム実技検定(PAST)」の公式テキストです。

アルゴリズムの検定対策本である一方で、Pythonの基本文法から解説されており、これ1冊でプログラミング自体の初学者でも段階的に学習することができます。
検定試験を見据えて勉強することでモチベーションを維持しやすい点も魅力的です。

また、競技プログラミングではしばしば数学色のかなり強い問題などが出題されることもありますが、PASTでは検定の主旨から、数学知識そのものが解法の本質となるような問題は基本的に出題されていません(数学的な考察や処理を行う問題自体は出題されています)。
そのため、本書で豊富に解説されているPASTの過去問はアルゴリズム学習の観点から教育的に良い問題も多く、演習問題の題材として非常に効果的だと思います。

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

競技プログラミングの教科書におけるバイブル的な存在で、界隈では「蟻本」と呼ばれて親しまれているロングセラーです。
 
「蟻本」は表紙に蟻が描かれていることに由来する略称ですが、これは本書の序盤に解説されている POJ 1852 の問題が元になっていると思われます。

 

内容は全体的に難しく、初級編、中級編、上級編の3部に分かれていますが、中級編の段階でセグメント木やネットワークフローなどに関連した比較的高度なデータ構造、アルゴリズムが掲載されています。例えば、Grundy数などは本記事で紹介している中でこの本だけが扱っています。

高度なものも含めた有名なアルゴリズムが手広くカバーされているため、ある程度慣れた人がステップアップするために活用するのが良いと思います。
また、「とりあえずわかるところまで読み、プログラミングコンテストで解けなかった問題が出るたびに蟻本で類題をチェックして理解を深める」といった辞書的な活用もできます。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

表紙に螺旋が描かれていることから、界隈では螺旋本と呼ばれています。
 
蟻本と比較すると、蟻本よりもやや簡単な内容までをより網羅的に扱っている書籍という印象です。初級者が辞書的に使う場合、蟻本よりも使い勝手が良いかもしれません。

 
 
 
例えば、計算幾何関連の章では、蟻本でも紹介されている線分の交差判定、平面走査、凸包などのアルゴリズムなどに加え、点の対称移動、内積による直交判定、線分間、あるいは点と線分の距離、円と直線の交点などを計算するアルゴリズムがプロコン必携ライブラリとして幅広く掲載されています。
 
これらは高校数学の知識などをベースに自力で実装することもできるかもしれませんが、体系的にまとめてくれていることは初学者や数学から離れて久しい社会人にとって大きな助けになります。

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

本書の特徴として、単に既存のアルゴリズムをわかりやすく解説するだけに留まらず、設計技法という観点から解説が行われています。
 
「競技プログラミング的な問題を題材としたアルゴリズムの学習を通じて、世の中の問題にうまくアプローチできるようになろう!」というところまで考えられた書籍です。
 
そのため、有名なアルゴリズムを紹介する主旨の本ではあまり取り上げられることのないPとNPの解説にまで踏み込み、「そもそもこの問題は効率よく解けるのか」という判定問題に関する説明も行われています。
 
 
それぞれの解説も丁寧で、直感的なイメージによる理解や考察の過程を自然に追いやすいような配慮がされています。
本書は競技プログラミングの入門書として蟻本などと比較されることも多いですが、競技プログラミングの入門書"としても"優れているといったほうが良いかもしれません。

アルゴリズムや数理最適化の学習を実生活に活かすことも視野に入れて学びたい方におすすめです。

おわりに

本記事がアルゴリズムや競技プログラミングに興味を持った方々の助けになれば幸いです。

株式会社システムインテグレータ 製品企画室 松永洋紀

 


RELATED POST関連記事


RECENT POST「アルゴリズム」の最新記事


アルゴリズム

プログラミングのオンライン学習サイトおすすめ8選!メリット・選び方を徹底解説

アルゴリズム

【初心者におすすめ】アルゴリズムの最適な勉強方法とは?参考Webサイト・本・アプリを紹介

アルゴリズム

プログラマー人材不足の原因と採用における有効な対策とは?

アルゴリズム

プログラマーに資格は必要?取得するメリットとおすすめ資格8選

アルゴリズムとデータ構造の学習におすすめの本5選 ~競技プログラミングの視点から~

TOPSIC TOPへ

TOPSIC-SQL4コマ漫画

RANKING人気記事ランキング

RECENT POST 最新記事