探索、ソート、最短経路、動的計画法など、アルゴリズムの定番テーマを10問にまとめました。どれも「なんとなく知っている」で済ませがちな内容ですが、計算量や仕組みの理由まで考えると意外と迷うものです。プログラミングの基礎固めや情報系の試験対策、知識の総点検にも役立ちます。まずは気軽に挑戦して、ご自身の理解度を確かめてみてください。解説もあわせて読めば、新しい発見があるかもしれません。
Q1 : 二分探索木を中順走査（左の子、自分、右の子の順に訪問）すると、キーはどのような順序で得られますか？
二分探索木では、どの節点についても、左部分木のキーはその節点のキーより小さく、右部分木のキーは大きいという性質があります。中順走査は左部分木、節点自身、右部分木の順に訪問するため、小さいキーから順に出力され、全体として昇順に並びます。この性質により、二分探索木のデータを整列した状態で取り出せます。挿入順や深さの順は、走査方法によって決まるものではなく、木の形にも左右されます。
Q2 : ユークリッドの互除法を用いて、48 と 18 の最大公約数を求めると、いくつになりますか？
ユークリッドの互除法は、gcd(a, b) = gcd(b, a mod b) という関係を使い、余りが 0 になるまで繰り返す方法です。48 と 18 の場合、gcd(48, 18) から 48 mod 18 = 12 なので gcd(18, 12) となり、18 mod 12 = 6 なので gcd(12, 6) となります。さらに 12 mod 6 = 0 となるため、最後の除数である 6 が最大公約数です。計算量は O(log(min(a, b))) と非常に高速です。
Q3 : 次のソートアルゴリズムのうち、入力データの並び方にかかわらず、最悪時間計算量が O(n log n) で抑えられるものはどれですか？
ヒープソートは、配列から最大ヒープを構築する処理が O(n)、その後、最大値を取り出して再構築する操作を n 回繰り返し、各操作が O(log n) なので、どんな入力でも最悪 O(n log n) で終わります。クイックソートは平均で O(n log n) ですが、ピボットの選び方が悪く、すでに整列済みの配列などが入力されると最悪 O(n^2) になります。バブルソートと挿入ソートも最悪 O(n^2) です。
Q4 : 後置記法（逆ポーランド記法）で書かれた式 3 4 + 2 * を、スタックを使って評価した結果はどれですか？
後置記法は、式を左から順に読み、数値ならスタックに積み、演算子が来たらスタックの上から 2 つの値を取り出して計算し、その結果を積み直す方式で評価します。この式では、まず 3 と 4 を積み、+ で 3 + 4 = 7 を計算して積みます。次に 2 を積み、* で 7 × 2 = 14 を計算します。これは通常の中置記法では (3 + 4) * 2 に相当し、結果は 14 です。後置記法には括弧が不要という利点があります。
Q5 : フィボナッチ数 F(n) を、計算済みの値を保存するメモ化再帰で求めたとき、時間計算量はどれになりますか？
素朴な再帰では、F(n) の計算で F(n-1) と F(n-2) を呼び出し、同じ値を何度も計算し直すため、時間計算量は指数的（おおよそ O(2^n)）になります。メモ化を使うと、各 F(k) は一度だけ計算されて配列などに保存され、以降は保存値を参照するだけになります。k は 0 から n までの n+1 種類しかなく、各計算は定数時間なので、全体の時間計算量は O(n) になります。これは動的計画法の基本的な考え方です。
Q6 : 硬貨が 1 円、3 円、4 円の 3 種類あり、各硬貨は何枚でも使えるとき、ちょうど 6 円を作るのに必要な最小の枚数はいくつですか？
3 円玉 2 枚で 3 + 3 = 6 円になるため、最小枚数は 2 枚です。大きい硬貨から順に使う貪欲法では、4 円玉を 1 枚使い、残り 2 円を 1 円玉 2 枚で払うので合計 3 枚になり、最適解になりません。この硬貨の組み合わせでは貪欲法が最適解を保証できないため、動的計画法で 1 円から順に最小枚数を求める必要があります。dp[6] = min(dp[5], dp[3], dp[2]) + 1 = 2 と計算できます。
Q7 : 二分探索を用いて、昇順にソート済みの n 個の要素から目的の値を探すときの最悪時間計算量はどれですか？
二分探索は、探索範囲の中央の要素と目的の値を比べ、範囲を毎回半分に絞り込んでいく手法です。要素数 n が 1 になるまでに必要な分割回数は約 log2(n) 回なので、最悪時間計算量は O(log n) になります。たとえば 100 万件でも約 20 回の比較で見つかります。ただし、データがあらかじめソートされていることが前提条件です。ソートされていない場合は先頭から順に調べる線形探索になり、計算量は O(n) です。
Q8 : 次のソートアルゴリズムのうち、一般的な実装で安定ソート（同じ値の要素の元の順序が保たれるソート）であるものはどれですか？
マージソートは、配列を二分して各々をソートしたあと、併合する際に同じ値なら左側の要素を先に取り出すことで、等しい要素の相対的な順序を保てます。そのため安定ソートです。一方、クイックソート、ヒープソート、選択ソートは、離れた位置の要素を交換する操作を含むため、一般的な実装では等しい要素の順序が入れ替わる可能性があり、安定ではありません。複数のキーで段階的に並べ替えたいときは、安定性が重要になります。
Q9 : ダイクストラ法（優先度付きキューを使う標準的な実装）が、正しい最短経路を保証できなくなる条件はどれですか？
ダイクストラ法は、距離が最小の頂点から順に最短距離を確定させていく貪欲法です。確定済みの頂点の距離は、以後の経路でこれ以上短くならないという前提で動きます。この前提は辺の重みがすべて非負のときにのみ成り立ちます。負の辺があると、あとから負の辺を通ることで確定済みの距離がさらに短くなる場合があり、正しい結果が得られません。負の辺を含むグラフにはベルマン–フォード法などを使います。有向グラフや非連結でも、非負であれば問題なく動作します。
Q10 : 重みのないグラフで、始点から各頂点までの最短辺数（最短経路）を求めるとき、幅優先探索（BFS）で使用する基本的なデータ構造はどれですか？
幅優先探索は、始点に近い頂点から順に、距離が 1、2、3 と増える順番で訪問していくアルゴリズムです。先に見つけた頂点を先に処理する必要があるため、先入れ先出し（FIFO）のキューを使います。これにより、頂点が最初に到達された時点の距離が、その頂点への最短辺数になります。スタックを使うと深さ優先探索になり、最短経路は保証されません。優先度付きキューは、辺に重みがあるダイクストラ法で使います。
まとめ
いかがでしたか？ 今回はアルゴリズムクイズをお送りしました。
皆さんは何問正解できましたか？
今回はアルゴリズムクイズを出題しました。
ぜひ、ほかのクイズにも挑戦してみてください！
次回のクイズもお楽しみに。
