アルゴリズムとデータ構造を学ぶメリット
アルゴリズムとデータ構造を学習するとうれしいことがたくさんあります。以下に列挙します。
論理的思考力や問題解決力が身につく
当ブログの以下の記事でも紹介されていますが、
アルゴリズムとは？プログラミングにおいての重要性、代表的なアルゴリズムの種類を紹介
そもそもアルゴリズムとは、問題を解くための方法や手順を指します。
アルゴリズムを学習する意義は、典型的なアルゴリズムは公式のように使いこなせるようにするだけでなく、プログラミングに限らず、課題に対して適切なアプローチをとるための訓練になることにもあります。
実際のところ、大半の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冊紹介します。
アルゴリズム一般についてより教科書的・体系的に知りたい場合は、アルゴリズムイントロダクションなども候補になってくると思います。
問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本
アルゴリズム実技検定 公式テキスト［エントリー～中級編］
AtCoder株式会社が実施する検定試験「アルゴリズム実技検定(PAST)」の公式テキストです。
アルゴリズムの検定対策本である一方で、Pythonの基本文法から解説されており、これ1冊でプログラミング自体の初学者でも段階的に学習することができます。
検定試験を見据えて勉強することでモチベーションを維持しやすい点も魅力的です。
また、競技プログラミングではしばしば数学色のかなり強い問題などが出題されることもありますが、PASTでは検定の主旨から、数学知識そのものが解法の本質となるような問題は基本的に出題されていません(数学的な考察や処理を行う問題自体は出題されています)。
そのため、本書で豊富に解説されているPASTの過去問はアルゴリズム学習の観点から教育的に良い問題も多く、演習問題の題材として非常に効果的だと思います。
プログラミングコンテストチャレンジブック
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
問題解決力を鍛える！アルゴリズムとデータ構造
おわりに
本記事がアルゴリズムや競技プログラミングに興味を持った方々の助けになれば幸いです。
株式会社システムインテグレータ 製品企画室 松永洋紀
