Photo by Oferico
皆さんはアルゴリズムやデータ構造について勉強したことはありますか?そして、基本的なアルゴリズムについて、どのようなものがあって、どのようなときに使うとよいかといったことを説明することができますか?
仕事をしていると、プログラミング言語等の勉強や業務に忙しくて、正直アルゴリズムどころではないという場合がほとんどでしょう。しかし、いつか勉強しようと思っていたけど、基本的なアルゴリズムにどんなものがあるのかなんて今更聞けないな……ということもあるかと思います。
今回はそんな方に向けて、基本的なアルゴリズムの一部の概要に加え、アルゴリズムの勉強に役立つサイト、書籍をご紹介したいと思います。
■アルゴリズムを学ぶ意味
例えば、ソート等については、通常はすでにソート関数があるので、自分で作らなくても済む=アルゴリズムも勉強しなくていいと思ってしまうかもしれません。しかし、ソート一つとっても様々なアルゴリズムがあるので、それぞれどのような方法で、どのようなデータのソートに向いているかを知らないと、システムによって最適なソート方法を選ぶことはできません。また、問題が起きた時にも、中でどのような処理がされているかを理解していなければ、解決方法を考えることはできません。
数列を昇順に並び替えたいと思ったときに、先頭からデータを全て順番に見ていく……という方法しか知らなければ、データの種類にかかわらず、同じ方法でソートしていくしかありません。しかし、ある程度プログラミングの経験を積むと、「もっと効率のよいやり方があるのでは?」という指摘を受けたり、自分でも思うようになったりします。
学び始めの頃は思いつかなかったけど、もっと効率のよいやり方、処理が高速になるやり方があるのでは……と気付いたとき、またそういったよりよい方法でシステムを作る必要が発生したときは、アルゴリズムについて勉強する必要があります。
下記、基本的なアルゴリズムから、最近注目されている機会学習関連のアルゴリズムまで、簡単に種類と概要をご紹介していきます。
ごく簡単な概要のご紹介になりますので、興味がわいたり詳しく知りたいと思うアルゴリズムがありましたら、各項目にございます解説サイトのリンクを辿ってみたり、書籍等で詳細を調べてみるのもよいかと思います。
■ソートアルゴリズム
例えば、3 1 2……というふうにランダムに数字の値があったとします。これを、1 2 3……等といった順番に並べ替えるためのアルゴリズムがソートアルゴリズムです。
ソートには色々な手法があり、それぞれの手法の評価軸には、平均計算時間、最悪計算時間、安定ソートか否か、また、実行時のメモリ使用量などがあります。(安定ソートとは、同じ値に関して、ソート前の順序がソート後も維持されているソート方法のことです。)
計算時間を解説する関数に関しては、こちらに解説があります。(ランダウの記号 - Wikipedia)
また、こちらのサイトにも個々のアルゴリズムについて詳しい解説があります。
◆マージソート
分割統治法の一種。
計算量時間(平均、最悪ともに)n log n
安定ソート:〇
バブルソートは処理が遅くなるため、実行時間の早いクイックソートやマージソートなどがよく使われます。
クイックソートとマージソートでどちらが適しているかは、入力データ次第というところがあります。完全にランダムな数字が入力される場合はクイックソートのほうが一般的に早く、一部がソートされいてるなど完全にランダムではないようなデータの場合は、マージソートの方が有利になる場合があります。
ソートに関しては、n log nより早く処理出来るアルゴリズムは、特定の条件などを除き、存在しないということが証明されています。
上記の他にも、ある特定の条件を満たしている場合には早くなるソート、鳩ノ巣ソートやバケットソートなどもあります。
■探索アルゴリズム
複数のデータの中から、目的のデータがどこにあるかを探すアルゴリズムです。
こちらに一部図解つきの解説も載っています。
アルゴリズム : アルゴリズムとデータ構造
◆リスト探索
例えば、1 2 3 4 5……のような数字の列に対し、「3はどこにあるか?」というように目的のデータの場所をを探すアルゴリズムになります。
◇二分探索
データのリストを半分ずつに分けて探索することで、計算量を削減できる方法です。対象のリストがソートされていなくては使用できませんが、高速に探索することができます。
◆木探索、グラフ探索
木のノードやグラフの探索で、共通で使われるアルゴリズムです。種類としては以下のようなものがあります。
◇幅優先、深さ優先探索
グラフや木構造の探索に使われます。幅優先探索は、隣接ノードを探索を繰り返して解を探索する方法です。深さ優先探索は、ノードの子がなくなるまで深く探索し、解が見つからない場合は探索していないノードまで引き返し、再度ノードの子がなくなるまでを繰り返す探索方法です。
◆グラフ探索固有
◇巡回セールスマン問題
都市の集合と各2都市間の移動コストが与えられたとき、全ての都市を一度ずつ巡り、出発地に戻る巡回路の総移動コストが最小のものを求める組合せ最適化問題です。
◆文字列探索
文字列の中に、その文字列より短い任意の文字列が含まれるかを探索するようなアルゴリズムです。
◇ボイヤームーアの文字列探索アルゴリズム
検索文字列(パターン)の前処理を行い、検索対象テキストの前処理は行わない方法です。テキストについて何度も検索を行わない場合に適しています。
■計算幾何学の分野に関するアルゴリズム
◆レイトレーシング
空間内の物体の集合に、半直線にどの物体が最初に交わるかを求める方法で、例えば、3Dゲームなどで光がどの物体に当たるか等を求めるために使われています。
■その他
◆暗号のアルゴリズム
◆パターン認識と機械学習のアルゴリズム
◆誤り検出、訂正のアルゴリズム
◇リードソロモン符号
QRコードなどで使われている誤り訂正符号です。難しいですがこちらのブログでかなり詳しく解説されています。
■アルゴリズムの勉強に適したサイトと書籍
アルゴリズムは研究の域まで達すると非常に多くの種類があり、上記でご紹介したものははほんの一部になります。
「もっと具体的に知りたい!」という方のために、アルゴリズムの学習に最適なサイトと書籍もご紹介いたします。
◆1.VisuAlgo
http://www.comp.nus.edu.sg/~stevenha/visualization/index.html
アルゴリズムをビジュアルで見せてくれるサイトです。アルゴリズムは文章だけで概念を解説されてもなかなか分かりにくいことが多いですが、こちらはビジュアルで動作の様子を見ることができます。「文字で読んで何となく分かったような気がする」アルゴリズムについても、ビジュアルの動きで直感的に理解することができます。
◆2.アルゴリズムを、はじめよう
アルゴリズムの入門書としてかなり分かりやすい書籍だと思います。アルゴリズムを学ぶ以前の、プログラミングにおける基礎的な分岐や繰り返しといった処理についても解説がありますので、「そもそもプログラミングの勉強も始めたばかり」という方にもお勧めです。◆3.「アルゴリズム」のキホン
こちらも多くの図を使って、かなり初心者向けにかみくだいた解説がされているアルゴリズム入門書です。「情報系の勉強をしたことはないんだけど、仕事でエンジニアと会話することが多いので勉強したい……でも難しい書籍だと理解できない……」という場合にもよいかもしれません。フルカラーだしキャラクターもかわいいです。◆4.アルゴリズムの絵本
絵本シリーズのアルゴリズム版です。こちらは多少C言語の基礎知識が必要かと思いますが、「アルゴリズムは文章だけで説明されても分かりにくいし、図が多い書籍があればとっつきやすいな……」という方にぴったりだと思います。◆5.基本情報技術者 大滝みや子先生のかんたんアルゴリズム解法
基本情報技術者の試験対策向けの書籍で、疑似言語等アルゴリズムを考える必要がある問題の解法についてが詳しく解説されています。プログラミング経験が浅い人だと、こういった問題を解くのはなかなか難しいかと思いますが、初めて受験する人でも理解できるようにかなり丁寧に解説されています。もちろん受験しない人でもアルゴリズムの勉強に役立つと思います。◆6.図解でかんたんアルゴリズム
アルゴリズムについての説明がコンパクトにまとまっている新書です。よく使うアルゴリズムのパターンがが多く収録されています。技術書は大きいものが多い中で、このサイズ感はありがたいです……。「分厚い本は読む気がしない」「通勤中に勉強したい」「いろいろなアルゴリズムの概要が知りたい」という方にとても良い書籍だと思います。◆7.アルゴリズムパズル ―プログラマのための数学パズル入門
こちらは「パズルを解くことで、アルゴリズム的思考を鍛える」というコンセプトで、150問のパズル問題が収録されています。ハノイの塔やnクイーン問題など、採用試験等でもよく出される問題についても収録されています。「パズルを解くのが好きだ」「実際に問題を解いて頭を動かしながら勉強したい」という場合にぴったりです。問題解くの楽しいです。難問もたくさんありますが……。◆8.paizaオンラインハッカソンVol.1「新人女子プログラマの書いたコードを直すだけの簡単なお仕事です!」
https://paiza.jp/poh/ec-campaign
paizaオンラインハッカソンVol.1は、実際のプログラミング問題を通してアルゴリズムに触れることができます。
こちらの問題は、探索のアルゴリズムを使って解くことができます。全探索でも解くことはできますが、二分探索の方がより速くなります。さらに、テストケースを全てクリアしたい場合は、尺取り法(与えられた配列の中から、ある条件を満たす最大の範囲を見つけるアルゴリズム)で解く必要があります。
・模範解答
paizaオンラインハッカソン模範解答
・解説記事
paiza.hatenablog.com
■まとめ
プログラミングの勉強を始めると、言語の勉強が主体となり、アルゴリズムの勉強というのはなかなか後回しになってしまいがちです。また、初心者の方や数学が苦手だった方には敷居が高いと感じてしまうかもしれません。
しかし、今後もエンジニアとしてシステムを作り続けていくのであれば、早めに学んでおいて損はありません。
まずはよく使われる基本的な方法を押さえて、それから興味のわいたアルゴリズムを勉強してみるとよいかと思います。
paizaは、技術を追い続けることが仕事につながり、スキルのある人がきちんと評価される場を作ることで、日本のITエンジニアの地位向上を目指したいと考えています。
自分のスキルを磨いていきたいと考えている方におすすめなのが「paizaラーニング」。オンラインでプログラミングしながらスキルアップできる入門学習コンテンツです。初心者でも楽しくプログラミングの基本を学ぶことができます。
そして、paizaでは、Webサービス開発企業などで求められるコーディング力や、テストケースを想定する力などが問われるプログラミングスキルチェック問題も提供しています。
スキルチェックに挑戦した人は、その結果によってS・A・B・C・D・Eの6段階のランクを取得できます。必要なスキルランクを取得すれば、書類選考なしで企業の求人に応募することも可能です。「自分のプログラミングスキルを客観的に知りたい」「スキルを使って転職したい」という方は、ぜひチャレンジしてみてください。