アルゴリズムとデータ構造を学ぶメリット
アルゴリズムとデータ構造を学習するとうれしいことがたくさんあります。以下に列挙します。
論理的思考力や問題解決力を鍛える
当ブログの以下の記事でも紹介されていますが、
アルゴリズムとは？プログラミングにおいての重要性、代表的なアルゴリズムの種類を紹介
そもそもアルゴリズムとは、問題を解くための方法や手順を指します。
アルゴリズムを学習する意義は、典型的なアルゴリズムを公式のように使いこなせるようにするだけでなく、プログラミングに限らず、課題に対して適切なアプローチをとるための訓練になることにもあります。
実際のところ、大半のIT企業では実務開発で高度なアルゴリズムそれ自体が要求される場面はそれほど多くないかと思いますが、「課題に対する解決方法の考察と実装が習慣化されている」という点は開発をスピーディに進めたり顧客の要望を取り込む上で大きな強みになります。
数学的な知識や思考力が身につく
「RSA暗号について、巨大な数の素因数分解が難しいことを安全性の根拠にしていることは一応知っているけど、フェルマーの小定理とかは知らない」
という人は結構いるのではないでしょうか。
アルゴリズムと数学は密接に関係しています。
アルゴリズムの学習を通じて、数学の知識や、数学的な考察力を身につけることができます。
ちなみに、私は競技プログラミングを通じてフェルマーの小定理を知りました。
計算量を意識したプログラミングができるようになる
仕事でプログラミングをしている方であっても
「計算量って何？」
「計算量なんて競プロでしか使わんでしょ」
と思っている方は一定数いると思います。
しかし、何も考えずに実装するとパフォーマンスが悪い例は、実は身近に結構あります。
けんちょん氏の以下のQiita記事の説明が非常にわかりやすいです。
アルゴリズムとデータ構造を学ぶことで必然的に計算量を意識するようになり、適切なデータ構造を用いて効率的に実装できるようになります。
資格試験に役立つ
基本/応用情報技術者試験の午後問題のアルゴリズムで苦労した方はいませんか？
アルゴリズムとデータ構造は、IPAが実施する情報技術者試験の出題範囲にもなっています。
アルゴリズムとデータ構造を学ぶことで、資格試験の際にそれらを得点源にすることができます。アルゴリズムに慣れた競技プログラマが応用情報の午後問題を初見で受けたら受かった、という例もあります。
また、AtCoder株式会社が実施するアルゴリズム実技検定などの民間検定もあります。
就職活動に役立つ場合がある
企業によっては就職試験としてコーディングテストを課す場合があります。
コーディングテストの問題はアルゴリズムを題材としたものが多く、アルゴリズムの勉強は間接的にコーディングテスト対策にもなります。
また、AtCoderなどのプログラミングコンテストサイトでコンテストに参加している場合、面接時に話のネタになったりします。
楽しい
楽しいです。
アルゴリズムを本で学ぶことのメリット
アルゴリズムを本で学習すると、下記のようなメリットがあります。
- 種類が豊富
- 比較的安価
- 信憑性が高い
1.種類が豊富
アルゴリズムについて説かれている本は、初心者から上級者向けまで数多く存在します。また、演習問題を解くことがメインの教材も豊富です。教材の中から、自分に合ったもの選択できれば効率よく学習を進められるでしょう。本を選ぶ前に、自分のレベルを自己分析することも大切です。
2.比較的安価
本は、学習サイトやプログラミングスクールに比べると安価です。中古本は安く購入できますが、アルゴリズムを学習する場合はおすすめできません。アルゴリズムやプログラミングの知識は、常に情報が新しくなるからです。できるだけ最新の情報を元に解説されている本で学習を進めましょう。
3.信憑性が高い
出版されている本は、ネットの情報よりも信憑性が高いです。ネットは匿名で気軽に情報を発信できるため、間違った情報もたくさん溢れています。一方で本は、現場で活躍するプログラマ、編集者、校閲者とプロが多く携わっているため、情報の信憑性が非常に高いです。本で正しい知識を習得しながら、補足的なものとしてネットの情報を取り入れるとより効果的に学習できます。
アルゴリズム学習と競技プログラミングの関係
競技プログラミングとは、参加者に与えられた問題について、その仕様を満足するプログラムをより早く(あるいはより高いスコアが得られるように)記述することを競う競技です。
当ブログの以下の記事でも紹介されています。
「アルゴリズムとデータ構造」の学習と「競技プログラミング」ですが、以下のような理由から、良くも悪くも切っても切れない関係になっています。
アルゴリズムやデータ構造の工夫が問題の解法に直結する
競技プログラミングでは、そのコンテストごとに様々な問題が出題されますが、ここでは短期型のコンテストを例に説明します。
比較的簡単な問題では、題意に沿って 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冊紹介します。
アルゴリズム一般についてより教科書的・体系的に知りたい場合は、アルゴリズムイントロダクションなども候補になってくると思います。
問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本
アルゴリズム実技検定 公式テキスト［エントリー～中級編］
AtCoder株式会社が実施する検定試験「アルゴリズム実技検定(PAST)」の公式テキストです。
アルゴリズムの検定対策本である一方で、Pythonの基本文法から解説されており、これ1冊でプログラミング自体の初学者でも段階的に学習することができます。
検定試験を見据えて勉強することでモチベーションを維持しやすい点も魅力的です。
また、競技プログラミングではしばしば数学色のかなり強い問題などが出題されることもありますが、PASTでは検定の主旨から、数学知識そのものが解法の本質となるような問題は基本的に出題されていません(数学的な考察や処理を行う問題自体は出題されています)。
そのため、本書で豊富に解説されているPASTの過去問はアルゴリズム学習の観点から教育的に良い問題も多く、演習問題の題材として非常に効果的だと思います。
プログラミングコンテストチャレンジブック
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
問題解決力を鍛える！アルゴリズムとデータ構造
アルゴリズムの学習におすすめの本3選【入門編】
アルゴリズムを、はじめよう
まず初心者プログラマーにおすすめなのが、「アルゴリズムを、始めよう」です。初心者向けに書かれており、無理なく学習を始められます。
具体的には、「アルゴリズムとは」「プログラミングとは」を説明しており、流れに沿ってプログラムの形を学習できます。
また、C言語などの具体的なプログラミング言語は登場せず、興味本位で手にとっても読み進められます。
アルゴリズム図鑑 絵で見てわかる26のアルゴリズム
本書は、アルゴリズムをイラストでわかりやすく解説しています。そのため、挫折しにくく初心者でも楽しく学習できます。具体的には、下記のような内容です。
・基本の26のアルゴリズム＋7つのデータ構造を解説
・アルゴリズムの考えや、問題点まで徹底解説
これからアルゴリズムを独学でおこなう方には最適です。
見て試してわかる機械学習アルゴリズムの仕組み 機械学習図鑑
本書は、機械学習初心者向けの入門書です。
図を多用し、機械学習アルゴリズムの専門家ではない人でも理解しやすいように解説されています。
一つ一つのアルゴリズムを深堀するのではなく、どのようなアルゴリズムがあるのかを見渡せるような構成です。
定番のアルゴリズム入門書3選
アルゴリズムの絵本 第2版 プログラミングが好きになる新しい9つの扉
本書では、イラストを多用し、2ページを単位とした説明で基本中の基本からアルゴリズムをわかりやすく解説しています。
効率の良い効果的なコードを作るための第一歩を踏み出すためには最適な一冊です。
「C言語の基礎」やプログラミングに必要な知識も広くフォローされ、基礎に絞り込んだ内容でスピーディに学習することができます。
おうちで学べるアルゴリズムのきほん
アルゴリズムの基本となる考え方や、開発＆活用力（＝問題解決力）、機械学習や深層学習など身近なテクノロジーへの活用例についてわかりやすく解説した入門書です。
自宅のPCで実際に試しながら学習を進めていくことが可能です。（ダウンロードサンプル付）
プログラマだけでなく、どなたでもアルゴリズムの知識を得ることができます。
なっとく！アルゴリズム
ソート／再帰／クイックソート／ハッシュテーブル／幅優先探索／ダイクストラ法／貪欲法／動的計画法／ｋ近傍法などのアルゴリズムについて、イラストや図解を交えわかりやすく解説されています。
サンプルコードはPythonを使用しています（何かしらのプログラミング言語を知っていれば問題ありません）。
アルゴリズムに苦手意識のあるプログラマの方、脱初心者を目指す方におすすめの一冊です。
おわりに
本記事では、アルゴリズムの学習におすすめの本を紹介しました。その後、基礎知識が身についたら自分が今後どのようなプログラミングをおこないたいのか考えてみましょう。そうすることで、次にどんな本を選ぶべきかが明確になります。本ブログがアルゴリズム学習のきっかけの一つになれば幸いです。
