アルゴリズム問題パターン
まず結論
科目Bの擬似コードはほぼすべて探索・ソート・数値処理・文字列処理のいずれかです。各パターンの「見分け方」と「解き方の型」を身につけることが得点力アップの近道です。
コードを見てパターンを特定する判断フロー
擬似コードを受け取る
↓
push/pop が見える？
→ スタック操作
enqueue/dequeue が見える？
→ キュー操作
left/right/mid が見える？
→ 二分探索
自分自身を呼び出す？
→ 再帰処理
2重ループ＋隣接比較・交換？
→ バブルソート
2重ループ＋最小値→先頭交換？
→ 選択ソート
a mod b で繰り返し代入？
→ 最大公約数（GCD）
s[i] で1文字ずつアクセス？
→ 文字列処理
パターン1：選択ソート
// 配列を選択ソートで昇順にソート
i を 1 から n-1 まで繰り返す
minIdx ← i
j を i+1 から n まで繰り返す
もし a[j] < a[minIdx] ならば
minIdx ← j
もし終わり
繰り返し終わり
// a[i]とa[minIdx]を交換
tmp ← a[i]
a[i] ← a[minIdx]
a[minIdx] ← tmp
繰り返し終わり
| i | 選ばれる最小値のインデックス | 配列（外ループ後） |
|---|---|---|
| 1 | a[4]=1が最小 → i=1と交換 | [1, 5, 4, 3, 2] |
| 2 | a[5]=2が最小 → i=2と交換 | [1, 2, 4, 3, 5] |
| 3 | a[4]=3が最小 → i=3と交換 | [1, 2, 3, 4, 5] |
| 4 | a[4]=4は最小 → 交換不要 | [1, 2, 3, 4, 5] 完成 |
バブルソートとの違い：バブルは「隣り合う要素を交換」。選択ソートは「残りの中の最小値を先頭と交換」。比較回数は同じO(n²)だが交換回数が少ない。
パターン2：文字列処理
// 文字列中の特定文字の出現回数を数える
手続き countChar(s, c)
count ← 0
i を 1 から sの長さ まで繰り返す
もし s[i] = c ならば
count ← count + 1
もし終わり
繰り返し終わり
count を返す
手続き終わり
// 呼び出し例：countChar("HELLO", "L") → 2
文字列処理パターン：文字列をchar配列として1文字ずつアクセス。s[i]で i番目の文字を参照。長さ関数（lenやlength）が使われることも。
パターン3：GCD（最大公約数）ユークリッドの互除法
// ユークリッドの互除法でGCDを求める
手続き gcd(a, b)
b が 0 でない間, 繰り返す
r ← a mod b // 余り
a ← b
b ← r
繰り返し終わり
a を返す
手続き終わり
// gcd(24, 9) のトレース
// a=24,b=9 → r=6,a=9,b=6
// a=9,b=6 → r=3,a=6,b=3
// a=6,b=3 → r=0,a=3,b=0
// b=0で終了 → a=3 を返す
パターン識別チートシート
| コードの特徴 | おそらくこのパターン |
|---|---|
| 外ループ内で最小/最大インデックスを探して交換 | 選択ソート |
| 隣り合うa[j]とa[j+1]を比較して交換 | バブルソート |
| left/right/mid変数がある | 二分探索 |
| 自分自身を呼び出す手続き | 再帰処理 |
| push/popがある | スタック操作 |
| enqueue/dequeueがある | キュー操作 |
| a mod b（余り）を使って代入を繰り返す | ユークリッドの互除法（GCD） |
| 文字列をインデックスで1文字ずつアクセス | 文字列処理 |
🎯 試験での出方
- 「このコードは何を行うアルゴリズムか」→ パターン識別チートシートで特定
- 「k回目の外ループ後の配列はどれか」→ 外ループをk回だけトレース
- 「空欄□に当てはまる条件はどれか」→ 前後のコンテキストとアルゴリズムの目的から判断
⚠️ よくある間違い
- 「選択ソートとバブルソートを混同する」→ 交換方法を見る。隣同士→バブル、最小値を先頭と→選択
- 「再帰の戻り値を追わない」→ 再帰は呼び出しが終わった後に戻り値が戻ってくる。呼び出し順と戻り順は逆
- 「mod（余り）演算の結果を間違える」→ 7 mod 3 = 1（7÷3=商2余り1）。余りが答え
✍️ 確認クイズ
Q1. 配列[5, 3, 4, 1, 2]を選択ソートで昇順ソートする場合、1回目の外ループ後の配列はどれか。
✅ 正解は②。選択ソートの1回目の外ループは配列全体の最小値（1）を探し、a[1]=5と交換します。結果は[1, 3, 4, 5, 2]。末尾に最大値が行くのはバブルソートのパターン。
Q2. gcd(36, 12)をユークリッドの互除法で求めると何になるか。
✅ 正解は②。a=36,b=12→r=0,a=12,b=0→b=0で終了→a=12を返す。36 mod 12=0なので1ステップで終わります。36と12の最大公約数は12。
Q3. 擬似コードで「left」「right」「mid」という変数が登場した場合、おそらくどのアルゴリズムか。
✅ 正解は②。二分探索は探索範囲の左端（left）・右端（right）・中央（mid）を管理してループします。mid=(left+right)÷2で中央を計算し、条件によってleftまたはrightを更新して範囲を半分にします。
Q4. 選択ソートとバブルソートの違いとして正しいものはどれか。
✅ 正解は②。どちらもO(n²)で比較回数は同じですが、交換の仕方が異なります。選択ソート：未ソート部分の最小値を選んでソート済み末尾と交換→交換回数がO(n)と少ない。バブルソート：隣同士を比較してより大きい値を後ろに送る→交換回数がO(n²)と多い。安定性は逆で、バブルソートが安定ソートです。
Q5. 文字列"ABCBA"の文字数を数えるcountChar("ABCBA", "B")を実行した場合の戻り値はどれか。
✅ 正解は②。"ABCBA"の各文字をトレース：s[1]='A'≠'B'、s[2]='B'='B'→count=1、s[3]='C'≠'B'、s[4]='B'='B'→count=2、s[5]='A'≠'B'。ループ終了後、count=2を返します。文字列処理のトレース問題は1文字ずつ丁寧に追いかけることが重要です。
Sponsor Link