応用情報技術者 ― アルゴリズムとプログラミング 問題一覧・解説

📝 解説

バブルソートは「隣り合う要素を比較して順序が逆なら入れ替える」操作を繰り返す整列アルゴリズムです。体育の整列を思い浮かべてください。「前の人より背が高ければ前と交換」を端から端まで繰り返すと、一番大きな値が泡（バブル）のように末尾へ浮き上がっていきます。n個のデータで最大n-1回のパスが必要で、計算量はO(n²)です。実用的には遅いですが、仕組みが直感的でアルゴリズム学習の入門として世界中で使われています。誤答の「最小値を探して先頭と交換」は選択ソート、「基準値で分割を繰り返す」はクイックソート、「整列済みの列の正しい位置に挿入」は挿入ソートの説明です。ソートの種類ごとの特徴と計算量はセットで覚えましょう！

📝 解説

クイックソートは「基準値（ピボット）を選び、それより小さいグループと大きいグループに分割する」操作を再帰的に繰り返す分割統治法のアルゴリズムです。図書館で本を整理するとき、まず「500番台より前か後か」で大別し、各グループ内でさらに細分化する方法と同じ発想です。平均計算量はO(n log n)と高速で、C言語やPythonなど多くの標準ライブラリで採用されています。ただし最悪ケース（整列済みデータでピボットが端になる場合）はO(n²)に落ちるため、ランダムなピボット選択で改善するのが一般的です。誤答の「O(n)」はハッシュ探索など特殊ケース、「O(n²)」はバブルソートや選択ソート、「O(log n)」は二分探索の計算量です！

📝 解説

スタック（Stack）は「後入れ先出し（LIFO：Last In First Out）」のデータ構造です。洗った皿を積み上げたとき、一番上（最後に置いた）皿から順に取り出す動作がまさにLIFOです。関数呼び出しの管理（呼び出した逆順に戻る）、undo機能（操作を逆順に戻す）、ブラウザの「戻る」ボタンなどで実際に使われています。データ追加を「プッシュ（Push）」、取り出しを「ポップ（Pop）」と呼びます。反対の概念がキュー（Queue）で「先入れ先出し（FIFO）」です。「スタック＝LIFO＝プッシュ＆ポップ」「キュー＝FIFO＝エンキュー＆デキュー」という対比を整理して覚えましょう。この区別は試験の最頻出事項の一つです！

📝 解説

キュー（Queue）は「先入れ先出し（FIFO：First In First Out）」のデータ構造です。銀行や病院の窓口に並ぶ行列そのものです。先に並んだ人が先にサービスを受けるのがFIFOです。データを追加する操作を「エンキュー（Enqueue）」、取り出す操作を「デキュー（Dequeue）」と呼びます。スタックのプッシュ／ポップと混同しやすいので注意！キューはプリンターのジョブ管理（先に送ったデータから順に印刷）、OSのプロセス待ち行列、ネットワークのパケットバッファなどで広く使われています。「エン（En）＝入れる、デ（De）＝出す」と語源から理解すると覚えやすいですよ。スタックとキューの使い分けと用語の違いを確実に身につけましょう！

📝 解説

二分探索（バイナリサーチ）は「整列済みデータの中央値と比較して探索範囲を半分に絞る」高速探索アルゴリズムです。辞書で単語を探すとき、真ん中のページを開いて前か後かで半分に絞り込む方法と全く同じです。1000件のデータなら最大10回の比較で見つかります（2¹⁰＝1024）。計算量O(log n)は線形探索のO(n)より圧倒的に速い！ただし「データが昇順または降順に整列されていること」が必須の前提条件です。整列されていなければ使えません。誤答の「2のべき乗個数が必要」「リンクリスト構造が必要」「正の整数のみ」はどれも事実と異なります。整列済みデータへの繰り返し検索では二分探索が最適解です！

📝 解説

再帰（リカーシブ）呼び出しとは「関数の中で自分自身を呼び出す」手法です。鏡の前に鏡を置いたときの「鏡の中の鏡」のような構造をイメージしてください。例えば5の階乗は「5! ＝ 5 × 4!」→「4! ＝ 4 × 3!」→…→「1! ＝ 1（終了条件）」のように問題を小さな同形の問題に分解します。大切なのは「終了条件（基底ケース）」を必ず設けること。なければ無限ループとなりスタックオーバーフローが発生します。木構造の全探索、ハノイの塔なども再帰で自然に表現できます。誤答の「引数を取れない」「戻り値が常にvoid」「グローバル変数を書き換えられない」はいずれも再帰とは無関係です！

📝 解説

線形探索（リニアサーチ）は「先頭から順番に全要素と比較する」最もシンプルな探索アルゴリズムです。落とし物を部屋の端から順番に探す方法そのものです。データが整列されていなくても使えるのが最大の強みです。最悪の場合は目的の値が末尾にある（またはない）ときで、n件のデータならn回の比較が必要。計算量はO(n)です。試験では「最悪の場合の比較回数」が問われることが多いので「n回」が正解です。「n/2回」は最悪ではなく平均の場合、「log n回」は二分探索の計算量、「n²回」はバブルソートなど整列の計算量と混同しないよう注意しましょう！

📝 解説

ハッシュ法では、異なるキーから同じハッシュ値（格納アドレス）が計算されることを「衝突（コリジョン）」と呼びます。郵便局の棚に例えると、郵便番号が同じ複数の人の荷物が同じ棚に割り当てられてしまう状況です。チェイン法（連鎖法）は衝突した要素を連結リストでつないで同じアドレスに格納する解決策です。もう一つの方法「オープンアドレス法」は衝突したら別の空きアドレスを探して入れます。衝突が増えると検索効率が落ちるため、テーブルサイズを大きめにして負荷率（格納率）を0.7〜0.8程度に抑えることが推奨されます。誤答の「オーバーフロー」「デッドロック」「スワッピング」はすべて別の概念です！

📝 解説

ポインタ変数は「別の変数のメモリアドレスを保持する変数」です。宝の地図がお宝の場所を示すように、ポインタはデータ本体ではなくデータが格納されているアドレスを指します。連結リスト（リンクリスト）は各ノードが「データ本体」と「次のノードのアドレス（ポインタ）」を持つ構造で、電車の各車両が「乗客（データ）」と「次の車両への連結器（ポインタ）」を持つイメージです。配列と比べて「中間への挿入・削除がO(1)で高速」という利点がありますが、「ランダムアクセスがO(n)で遅い」という欠点もあります。誤答の「固定長配列」「静的変数」「定数テーブル」はポインタを必須としない構造です！

📝 解説

継承（インヘリタンス）はオブジェクト指向の基本概念で、「サブクラスがスーパークラスの属性とメソッドを受け継ぐ」仕組みです。例えば「乗り物」クラスに「速度・重量」の属性と「走る・止まる」メソッドがあれば、「電車」クラスは継承によってそれらを再定義なしに使えます。「電車は乗り物の一種（is-a関係）」という階層関係を表現でき、コードの再利用性が高まります。オーバーライドで子クラスが親クラスのメソッドを独自に再定義することも可能です。カプセル化（データ隠蔽）・ポリモーフィズム（多態性）と並ぶオブジェクト指向の三大特徴のひとつです。「インスタンス化」はクラスからオブジェクトを生成する別の概念です！

📝 解説

バブルソートは「隣り合う2要素を比較して、順序が逆なら入れ替える」操作を全体に対して繰り返すソートアルゴリズムです。体育の整列で「隣の人と背の順を確認しながら端から端まで交換を繰り返す」動作に似ています。n個のデータに対して、1回のパスで最大n-1回の比較、それをn-1回繰り返すため、計算量は最悪も平均もO(n²)です。バブルソートの特徴は「実装がとてもシンプル」「データの大きい要素が泡のように末尾へ浮き上がる」「既にほぼ整列済みのデータに対してはO(n)に近い性能が出る」という点です。ただし大規模データには非効率で実用には向きません。マージソートやクイックソートのO(n log n)と比べると、n＝1000なら約100万対約1万回の比較で圧倒的な差があります。「バブルソート＝O(n²)」はアルゴリズム学習の基礎知識として確実に覚えましょう！

📝 解説

クイックソートは「ピボット（基準値）を選び、それより小さいグループと大きいグループに分割する」操作を再帰的に繰り返す、分割統治法に基づくソートアルゴリズムです。図書館の本を整理するとき「まず著者名のア行か行以降かで2山に分け、各山をさらに細かく分ける」やり方と同じ発想です。この分割が毎回ほぼ均等に行われる場合、分割の深さがlog n層になり1層あたりn回の操作で済むため、平均計算量はO(n log n)になります。クイックソートはキャッシュ効率も良く定数係数が小さいため実際の動作も非常に高速で、C言語のqsort()やPythonのTimSortなど多くの言語の標準ライブラリに採用されています。ただしピボットの選び方が悪く毎回最小か最大が選ばれると分割が偏り最悪O(n²)になります。乱数や中央値でピボットを選ぶことで最悪ケースを回避するのが実用上の工夫です。「クイックソート平均＝O(n log n)、最悪＝O(n²)」をセットで覚えましょう！

📝 解説

スタック（Stack）は「後入れ先出し（LIFO：Last In First Out）」のデータ構造です。食器棚に皿を積み重ねる動作をイメージしてください。一番上（最後に置いた皿）から順に取り出すしかできません。これがLIFOです。スタックへのデータ追加を「プッシュ（Push）」、取り出しを「ポップ（Pop）」と呼びます。実際のコンピュータでは関数の呼び出し管理（呼び出した逆順に戻る）、エディタのUndo機能（操作を逆順に取り消す）、ブラウザの「戻る」ボタンなどで広く使われています。誤答のFIFO（先入れ先出し）はキューの原則、LILO・FILOは実際には使わない表現です。「スタック＝LIFO＝皿の積み重ね」「キュー＝FIFO＝窓口の行列」という対比で覚えると混乱しません。試験ではスタックとキューの原則、それぞれの操作名（Push/Pop・Enqueue/Dequeue）を混同しないよう整理しておきましょう！

📝 解説

キュー（Queue）は「先入れ先出し（FIFO：First In First Out）」のデータ構造です。銀行や病院の窓口に並ぶ受付順の行列がまさにFIFOです。先に並んだ人から順にサービスを受けます。キューへのデータ追加を「エンキュー（Enqueue）」、取り出しを「デキュー（Dequeue）」と呼びます。プリンターの印刷ジョブ管理（先に送ったデータから順に印刷）、OSのプロセス待ち行列、ネットワークのパケットバッファなど、日常的なシステムで広く活用されています。誤答のLIFO（後入れ先出し）はスタックの原則です。LILOとFILOは実際には使わない表現で誤答の引っかけ選択肢です。「キュー＝FIFO＝行列（並んだ順に処理）」という日常のイメージと結びつけると覚えやすいです。スタックとキューのどちらを使うかは「処理順序」の設計に直結するため、違いをしっかり理解しておくことが重要です！

📝 解説

二分探索（バイナリサーチ）は「整列済みデータの中央値と比較して探索範囲を半分に絞る」を繰り返す高速探索アルゴリズムです。辞書で単語を調べるとき、まず真ん中のページを開いて「目的の単語は前か後か」で半分に絞り込む方法と全く同じです。毎回データが半分になるため、n件のデータを探すのに必要な最大比較回数はlog₂n回です。1000件なら約10回、100万件でも約20回で見つかります！これがO(log n)の威力です。前提として「データが昇順または降順にソートされていること」が必須です。誤答のO(n)は線形探索（先頭から順番に調べる）の計算量で、整列不要ですが遅い。O(n²)はバブルソートなど単純ソートの計算量、O(n log n)はクイックソートなど高速ソートの計算量です。「二分探索＝O(log n)＝ソート済みが前提」をしっかり覚えて、他の計算量との混同を避けましょう！