こんにちは。paizaラーニングでコンテンツ制作をしている学生スタッフの工藤です。
プログラミングを学んでいる方の中には「アルゴリズムの勉強をしたい」という方も多くいらっしゃると思います。
先日ご紹介した「ソート」「動的計画法」もメジャーなアルゴリズムですが、「探索」も覚えておきたいアルゴリズムのひとつです。
その中でも今回扱う線形探索は、「探したい値を先頭からしらみつぶしに探していき、見つかれば終了」という探索方法です。
データの数が多くなると処理に時間がかかってしまいますが、理解しやすく実装も容易なため、これからアルゴリズムを学びたい方が学習の取っ掛かりとするにはちょうどいいアルゴリズムといえます。
そこで今回は、paizaラーニングのレベルアップ問題集に追加された「線形探索メニュー」を使った線形探索の学習法を紹介します。
探索アルゴリズムとは
本題に入る前に探索アルゴリズムについて、少し説明しておきます。
探索とは、簡単に言うと「配列やリストなどに格納された複数のデータの中から目的のデータがどこにあるかを探す」という意味です。
今回扱う「線形探索」の他にも「二分探索」「幅優先探索」「深さ優先探索」あたりがメジャーなアルゴリズムで、名前は聞いたことがあるという方もいるかもしれませんね。
データが少なければ線形探索を使ってもよいのですが、冒頭でも少し触れたとおりデータ量が多いと計算量は最悪O(n)かかり非常に効率が悪いといえます。（計算量についてはこちらの記事も参考にしてください。）
よって、高速に探索をおこなう必要がある状況においては、もっと効率よく目的の値を探し出せる探索アルゴリズムを用いて計算量を減らす必要があります。
ただ線形探索は、すべての探索アルゴリズムの基礎となるアルゴリズムでもあります。これから理解を深めていくためにもまずは線形探索をしっかりマスターしましょう。
以下の記事では初めてアルゴリズムの学習をする方向けに、入門として押さえておきたい内容をまとめていますので、問題集に取り掛かる前に軽く目を通していただけるとよいかもしれません。
レベルアップ問題集とは
「線形探索メニュー」は、レベルアップ問題集にて公開しています。
レベルアップ問題集とは、プログラミング学習における計算ドリルや漢字ドリルのようなものだと思ってください。
ドリルのようにプログラミング問題を解き進めながら、解答例となるコード（一部言語）や解説文も参照できる*1ため分からないことを理解したり、苦手なポイントを克服したりできるように作られています。
paizaが提供しているスキルチェックとは異なり時間制限がなく、問題文や自分の解答コードを公開することが認められていますので、誰かと協力して取り組むことも可能です。
練習問題集「線形探索メニュー」
今回追加された線形探索メニューでは、線形探索について学習することができます。現在は、C++の解答コード例を公開しています。なお、今後他の言語の解答コード例も追加予定です。
線形探索メニューは、小規模なプログラムであれば自力で書けるようになってきた方に取り組んでいただくことを想定して作成しています。
そのため問題を解くにあたって、標準入出力や配列、if文やfor文などの基礎的な文法についてはあらかじめ理解している必要があります。
標準入力については、言語別で学習講座を公開していますのでこちらの一覧から取り組みたい言語を選択して受講してみてください。合わせてレベルアップ問題集の「標準入力メニュー」「標準出力メニュー」も解いておくとよいでしょう。
基礎文法が理解できているかどうかは、同じく問題集の「配列メニュー」「条件分岐メニュー」を解いて確認してみてください。
出題される問題の特徴
線形探索メニューは4つのセクションに分かれており、全17問のプログラミング問題が用意されています。
各セクションは何問かの「準備問題」と、1問の「ボス問題」から構成されています。「準備問題」を順に解いていくことで最後の「ボス問題」が自力で解けるようになっています。
各セクションは独立しているため、興味のあるテーマから選んで問題を解くことができますが、線形探索を初めて学習するという方は最初のセクションから順に解くとよいでしょう。
1:指定された値の探索
1つめのセクションは「指定された値の探索」です。
このセクションでは、線形探索を使って解くことのできる問題のうち最もシンプルな、数列から特定の値を探索する問題を扱っています。
まずは線形探索がどういったものか知りたい方におすすめです。
レベルアップ問題集の問題はスキルチェック同様、問題にS～Dのランクが表示されています。Sがもっとも難易度が高く、Dがもっとも低くなっています。ランクについて詳細はこちら。
このセクションはDランク相当の問題のみで構成されているためプログラミングを始めたばかりの方もぜひ挑戦してみてください。
2:最大最小
2つめのセクションは「最大最小」です。
このセクションでは、数列の最大値や最小値を線形探索によって求める手法を学習することができます。
与えられる値の大小を順に比較して解くこともできますが、ソートして最小値・最大値を求める方法を考えてみてもよいでしょう。配列に入れた数値をソートしたり、最小値・最大値を求める関数を使ったりと工夫することでシンプルなコードで書けます。
前述のとおり解答コード例は現在C++のみですが、解説は言語関係なく解き方のヒントになりますので、よければ参照してみてください。
3:特定の条件を満たす値の探索
3つめのセクションは「特定の条件を満たす値の探索」です。
このセクションでは、これまでのセクションよりやや複雑な実装が必要とされるような問題を扱います。
準備問題が7問と多めに用意されていますが、順番に解いていくことで力がつきますので、ぜひ頑張って取り組んでみてください。
最後には以下のような問題も解けるようになるはずです。
問題文：
n 人の生徒がテストを受けました。このテストで k 点以上 l 点以下の点数を取った人が合格です。
n 人の各生徒について、その人の名前とその人が取った点数が入力として与えられるので、このテストに合格した人の名前をすべて、入力された順に改行区切りで出力してください。
なお、合格者が一人もいない場合は、何も出力しないでください。
入力値：
n
s_1 t_1
s_2 t_2
...
s_n t_n
k l
- 1行目に、生徒の人数を表す整数 n が与えられます。
- 続く n 行のうち i 行目に、i 番目の生徒の名前 s_i とその生徒の得点 t_i が半角スペース区切りで与えられます。
- n+2 行目に、合格点の基準を表す整数 k, l が半角スペース区切りで与えられます。
期待する出力：
テストに合格した人の名前をすべて、入力された順に改行区切りで出力してください。また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
なお、合格者が一人もいない場合は、何も出力しないでください。
条件：
すべてのテストケースにおいて、以下の条件をみたします。
- 入力は s_i を除いて全て整数
- 1 ≦ n ≦ 100
- s_i は英小文字 'a', 'b', ... , 'z' からなる1文字以上10文字以下の文字列
- i ≠ j ならば s_i ≠ s_j
- 0 ≦ t_i ≦ 100
- 1 ≦ k, l ≦ 100
- k ≦ l
少々条件が複雑で難しそうに感じるかもしれませんが、入力値を順に「合格しているかどうか」を見て、合格していれば名前を出力すると考えるとよいでしょう。
4:第k要素の探索
最後のセクションは「第k要素の探索」です。
このセクションでは、線形探索を複数回おこなうことにより答えを得る手法を学習することができます。
すべての問題が解けたらぜひ「素朴なソートアルゴリズムメニュー」にも挑戦してみてください。
今回もソートを使う場面がありましたが、ソートアルゴリズムの中でも基本となる「選択ソート」「挿入ソート」「バブルソート」を扱っており、こちらもアルゴリズム学習を始めるのに適した題材となっています。
まとめ
レベルアップ問題集に追加された「線形探索メニュー」について紹介してきました。
本文でもお伝えしたとおり、線形探索は探索アルゴリズムのもっとも単純かつ基本となるアルゴリズムです。
これからもっと探索アルゴリズムの学習を深めたいという方は、ぜひこの問題集を利用してマスターしていただければと思います。
プログラミングを始めたばかりで問題集の内容が難しいと感じた方は、まずは基礎文法からしっかり身につけるのもよいでしょう。
paizaラーニングでは、Python・PHP・Ruby・Java・C・C#・JavaScriptの7言語の入門講座を公開していますので、ぜひご活用ください。
練習問題をたくさん解いたあと、そろそろ自分のプログラミング力を腕試ししてみたい！という方は、時間制限ありのスキルチェックにもチャレンジしてみてください。
詳しくはこちら
*1:ただし、それらを閲覧するためには学習チケットが必要となります。チケットは毎日初回ログイン時に1枚付与され6枚まで所持できます。（有料会員の場合はチケットの消費なしで閲覧可能です）
