こんにちは。倉内です。
プログラミングの学習がある程度進んだ方や問題を解くのが楽しいと感じている方で「次はアルゴリズムを学んでみたい！」という方は多いと思います。
ただ、そもそもアルゴリズムとはどういうもので、どうやって独学すればいいのか…となかなか手を出せない方もいるのではないでしょうか。
今回は、アルゴリズムを基礎から学べる学習講座や問題集、書籍などをご紹介します。無料で利用できるコンテンツも取り上げますので、ぜひ参考にしてみてください！
「アルゴリズムとはなにか」を知る
アルゴリズムとは、広い意味では「なんらかの問題を解くための決められた手順や法則のこと」と定義されています。プログラミング学習で考えるときは、解のある計算可能な問題に対して、解を求める手続きのことと理解するとよいでしょう。（参考：アルゴリズム - Wikipedia）
同じ解を求めるプログラムでもさまざまな書き方があり、アルゴリズムを知らなくても、たとえば、ループ処理を繰り返して求めたい結果を得られることもあります。
しかし、大量のデータを処理するWebサービスや処理速度を重視する業務システムの開発などは、効率のよいアルゴリズムを知らないと結果を得るのに実用に耐えない時間がかかってしまうこともあります。そのため実際の開発業務では、ただコードを書くだけではなく、効率的な処理になるよう考慮しなければいけません。
アルゴリズムをいちから考え出すのはとても難しいですが、わたしたちは先人が生み出した多くのアルゴリズムを利用できます。
paizaラーニングの講座「新・アルゴリズムとデータ構造入門 Java編」（レッスン1）でも、アルゴリズムとはなにかについて動画で解説していますのでぜひ参考にしてみてください。
ちなみに、アルゴリズムを理解する上で欠かせない計算量については以下の記事で説明しています。
定番のアルゴリズムと学習法
プログラミング問題を解く際によく利用される代表的なアルゴリズムをいくつか取り上げました。
理解のしやすさや実装難易度別に分類してみましたが、対象のデータ量や実現したい実行時間などさまざまな要因で一概には言えないケースもあるので参考までにごらんください。
また、そのアルゴリズムを学べる動画講座と問題集もまとめました。
初級編
ソートアルゴリズム「選択ソート」「挿入ソート」「バブルソート」
ソートアルゴリズムは、もっとも基本的なアルゴリズムのひとつで、順序付け可能なデータの列を昇順または降順に並び替えるアルゴリズムです。
ソートの中でもこの3つは特にシンプルで、アルゴリズム学習の最初に触れることが多いものです。
プログラミングの練習問題を集めた「レベルアップ問題集」*1の「素朴なソートアルゴリズムメニュー」で扱っています。どのような特徴を持つソートなのかも問題文で説明していますので初めての方も取り組んでみてください。
動画講座の「新・アルゴリズムとデータ構造入門 Java編4: 素朴なソートアルゴリズム」でも解説しています。
探索アルゴリズム「線形探索」「二分探索」
探索とは、簡単に言うと「配列やリストなどに格納された複数のデータの中から目的のデータがどこにあるかを探す」という意味です。
ここで取り上げるふたつの探索アルゴリズムは基本的なもので、特に「線形探索」は、探したい値を先頭からしらみつぶしに探していき、見つかれば終了という探索方法です。
データの数が多くなると処理に時間を要してしまいますが、理解しやすく実装も容易なため、これからアルゴリズムを学びたい方が学習の取っ掛かりとするにはちょうどいいアルゴリズムといえます。
「レベルアップ問題集」の「線形探索メニュー」「線形探索メニュー 応用編」「二分探索メニュー」「二分探索メニュー 応用編」で問題を解くことができます。
動画講座の「新・アルゴリズムとデータ構造入門 Java編2: 線形探索」でも解説しています。
FizzBuzz問題
ITエンジニアの就活・転職の面接において、初級問題として定番の「FizzBuzz問題」は、以下のような問いです。
与えられた整数が
・3の倍数かつ5の倍数のときには、"Fizz Buzz"
・3の倍数のときには、"Fizz"
・5の倍数のときには、"Buzz"
を表示してください。
これをプログラムで実現するためには、四則演算や基本的な条件分岐を理解している必要があります。
「レベルアップ問題集」では、「スキルチェック見本問題セット」にFizzBuzzの問題がありますのでぜひ挑戦してみてください。
また、動画講座の「アルゴリズム入門編」でも解説しており、2パターンの解き方を解説しています。
中級編
ソートアルゴリズム「シェルソート」「マージソート」「クイックソート」
初級編で紹介したソートアルゴリズムより少し難しいですが、効率よくデータの並び替えをおこなえるように工夫されています。
「レベルアップ問題集」の「効率的なソートアルゴリズムメニュー」で扱っています。こちらもどのような特徴を持つソートなのかも問題文で説明していますので、どう効率がよいのかも合わせて考えてみてください。
動画講座の「新・アルゴリズムとデータ構造入門 Java編5: 効率的なソートアルゴリズム」でも解説しています。
探索アルゴリズム「幅優先探索」「深さ優先探索」「ハッシュ法」
幅優先探索（BFS：Breadth First Search）と深さ優先探索（DFS：Depth First Search）は、木構造に対してノードをすべて巡回して探索する方法です。文字で見るより図解を見たほうが分かりやすいので、以下の記事も参考にしてみてください。
また、ハッシュ法（ハッシュ探索）とは、これまで紹介してきた探索アルゴリズムの中ではもっとも小さい計算量で探索をおこなえるアルゴリズムです。ハッシュ関数*2を用いて目的のデータの格納位置を特定します。
「レベルアップ問題集」の「幅優先探索・深さ優先探索メニュー」「ハッシュメニュー」で問題を解くことができます。
フィボナッチ数（再帰的処理での実装）
フィボナッチ数と呼ばれる数値を表示するためのプログラムには、もっと単純な実装方法もありますが、再帰を理解するのにもよいので動画講座「アルゴリズム入門編」を参考に挑戦してみましょう。
ユークリッドの互除法
ユークリッドの互除法は、2つの自然数の最大公約数を求める手法です。ちなみに、最大公約数とは2つ以上の正の整数の共通の約数のうち最大の数字を言います。
2つの数字の最大公約数を求めるアルゴリズムには単純なものもありますが、ユークリッドの互除法を使うとコード量が非常に少なく、計算量も小さいほうの数字の桁数の約5倍繰り返せば必ず答えが出ると言われています。詳しくは以下の記事もご参照ください。
上級編
動的計画法
動的計画法（DP：Dynamic Programming）は、競技プログラミングの問題を解く際に非常に多く用いられます。
初心者の方には少しハードですが、レベルアップ問題集の「DPメニュー」に取り組めば、動的計画法とは何かを理解できると思います。
そしてこの動的計画法を用いて解く問題の代表といえば「巡回セールスマン問題」です。動画講座「アルゴリズム入門編: 「巡回セールスマン問題」を学ぶ」で図解していますので、問題集をいきなり解くのが難しいと感じた方はこちらを先に受講してみてください。
「巡回セールスマン問題」にはいろいろな解き方があります。以下の記事では8つの解法について解説しています。
ダイクストラ法
ダイクストラ法とは、グラフ上にある2点間の最短経路を求めるアルゴリズムで、考えられる全経路を挙げていくよりも効率的に求めることができます。
最短経路問題として競技プログラミングなどでは頻出のアルゴリズムなのでぜひ覚えておきたいところです。
自力で問題を解こうとすると最初は難しいと思いますので、解説を参考にしながら理解してみてください。paiza.IOを使えば実行環境を構築しなくてもWebブラウザ上でコード実行ができます。
また、「レベルアップ問題集」の「グリッド版ダイクストラ問題セット」で問題も解けますので合わせてチェックしてみてください。
乱択アルゴリズム「ラスベガス法」「モンテカルロ法」
ここまでと少し毛色が違いますが、乱択アルゴリズムとは大雑把に言うと、乱数を使って平均するとよい結果を出せることを狙ったアルゴリズムです。
乱択アルゴリズムには「ラスベガス法」と「モンテカルロ法」の2種類あります。以下の記事で解説している「モンテカルロ法」は、運がよければ短い計算時間で正しい結果を求められますが、運が悪いと間違った結果を返します。
必ず最適な解を得られるわけではありませんが、パズルを完成させるための手数や近似値を求めるのに用いられることがあります。
よりアルゴリズムを極めたい方へおすすめの書籍
難度の高い問題で腕試しをする
ここまでpaizaラーニングの動画講座や問題集をご紹介してきましたが、paizaにはスキルチェックというS・A・B・C・Dランクの難易度別のプログラミング問題を制限時間内に解くことで、結果に応じたランクを獲得できるサービスがあります。
Aランク、Sランクの問題は、問題文や条件が複雑なものももちろんありますが、一見それ以下のランクの問題よりシンプルに見えるものもあります。
そこで問われるのが、ここまで紹介してきたようなアルゴリズムを用いて計算量の少ない処理を書けるかどうかです。S・Aランクでは実行時間が長いと満点を取れません。
アルゴリズム力が鍛えられたか、自分は今どのくらいコードを書けるのか、ぜひスキルチェック問題で腕試しをしてみてください！
まとめ
基本的なアルゴリズムから少し難度の高いアルゴリズムまで、代表的なものをピックアップしてご紹介してきました。
アルゴリズムは説明を読んだだけではなかなか理解できません。コードを書いて実装する力をつけるために、本文で紹介した講座や問題集、書籍を活用していただければと思います。
「レベルアップ問題集」には、今回紹介しきれなかったプログラミングの練習問題がまだまだたくさんあります。もっと簡単なものから始めたいという方もぜひごらんください。
「paizaラーニング」では、未経験者でもブラウザさえあれば、今すぐプログラミングの基礎が動画で学べるレッスンを多数公開しております。
詳しくはこちら
そしてpaizaでは、Webサービス開発企業などで求められるコーディング力や、テストケースを想定する力などが問われるプログラミングスキルチェック問題も提供しています。
スキルチェックに挑戦した人は、その結果によってS・A・B・C・D・Eの6段階のランクを取得できます。必要なスキルランクを取得すれば、書類選考なしで企業の求人に応募も可能です。「自分のプログラミングスキルを客観的に知りたい」「スキルを使って転職したい」という方は、ぜひチャレンジしてみてください。
詳しくはこちら
