コーディングテスト必須アルゴリズム入門 - 計算量・ソート・探索
📚 概要
コーディングテストで最も重要なのは、問題に対して適切なアルゴリズムを選択できる力です。どんなに美しいコードを書けても、制限時間内に処理が終わらなければ不正解になります。
この記事では、コーディングテストの土台となる計算量の見積もり方、ソートアルゴリズムの使い分け、探索アルゴリズムのテンプレートを体系的に解説します。初学者がつまずきやすいポイントを重点的にカバーし、実践的な問題解決力を身につけることを目指します。
🕰️ 歴史的背景
アルゴリズム解析の起源
アルゴリズムの計算量を体系的に分析する手法は、1960年代にドイツの計算機科学者 Juris Hartmanis と Richard Stearns によって確立されました。彼らは1993年にチューリング賞を受賞しています。
Big O 記法の普及
Paul Bachmann（1894年）が最初に O 記法を導入し、その後 Edmund Landau が広めました。現在では、プログラマがアルゴリズムの効率を議論するための共通言語となっています。
コーディングテストの変遷
- 2000年代前半: Google、Microsoft が技術面接でアルゴリズム問題を出題し始める
- 2007年: LeetCode が設立され、オンラインジャッジが普及
- 2010年代: AtCoder、Codeforces などの競技プログラミングが活発化
- 現在: コーディングテストは多くの企業の採用プロセスに組み込まれている
🔧 技術解説
1. Big O 記法と計算量の見積もり
Big O 記法は、入力サイズ N に対して処理時間がどのように増加するかを表します。定数倍や低次の項を無視し、最悪ケースの増加率に注目します。
計算量の階層
graph LR
A["O(1)"] --> B["O(log n)"]
B --> C["O(n)"]
C --> D["O(n log n)"]
D --> E["O(n²)"]
E --> F["O(2ⁿ)"]
F --> G["O(n!)"]
style A fill:#51cf66
style B fill:#8ce99a
style C fill:#ffe066
style D fill:#ffa94d
style E fill:#ff8787
style F fill:#ff6b6b
style G fill:#c92a2a| 計算量 | 名称 | N=10^6 での概算ステップ数 | 代表的なアルゴリズム |
|---|---|---|---|
| O(1) | 定数時間 | 1 | ハッシュテーブル参照 |
| O(log n) | 対数時間 | 20 | 二分探索 |
| O(n) | 線形時間 | 10^6 | 線形探索、1回のループ |
| O(n log n) | 準線形時間 | 2 x 10^7 | マージソート、ヒープソート |
| O(n^2) | 二乗時間 | 10^12 | バブルソート、二重ループ |
| O(2^n) | 指数時間 | 天文学的 | 全探索（部分集合列挙） |
| O(n!) | 階乗時間 | 天文学的 | 全順列列挙 |
制約から計算量を逆算する
コーディングテストでは、入力サイズの制約から使うべきアルゴリズムの計算量を逆算できます。一般に、1秒あたり約 10^8 回の演算が実行可能と考えます。
| 制約 (N の上限) | 許容される計算量 | アプローチ例 |
|---|---|---|
| N <= 10 | O(n!) / O(2^n) | 全探索、全順列 |
| N <= 20 | O(2^n) | ビット全探索 |
| N <= 100 | O(n^3) | 3重ループ、Floyd-Warshall |
| N <= 3,000 | O(n^2) | 二重ループ、単純DP |
| N <= 10^5 | O(n log n) | ソート、二分探索、セグメント木 |
| N <= 10^6 | O(n) / O(n log n) | 線形走査、HashMap |
| N <= 10^9 | O(log n) / O(sqrt(n)) | 二分探索、数学的解法 |
// 例: N <= 10^5 の問題
// O(n^2) = 10^10 → TLE（時間超過）
// O(n log n) = 10^5 * 17 ≈ 1.7 * 10^6 → OK
// → ソートや二分探索を使うアプローチを考える
計算量の数え方の基本
// ループの計算量
for i in range(n): // O(n)
処理
for i in range(n): // O(n^2)
for j in range(n):
処理
for i in range(n): // O(n^2) ではなく O(n*(n-1)/2) = O(n^2)
for j in range(i, n):
処理
// 再帰の計算量
function fib(n): // O(2^n) - メモ化なし
if n <= 1: return n
return fib(n-1) + fib(n-2)
function fib(n, memo): // O(n) - メモ化あり
if n in memo: return memo[n]
if n <= 1: return n
memo[n] = fib(n-1, memo) + fib(n-2, memo)
return memo[n]
2. ソートアルゴリズム
ソートアルゴリズムの分類
graph TB
A[ソートアルゴリズム] --> B[比較ベース]
A --> C[非比較ベース]
B --> D[安定ソート]
B --> E[不安定ソート]
D --> F[マージソート]
D --> G[挿入ソート]
D --> H[バブルソート]
E --> I[クイックソート]
E --> J[ヒープソート]
E --> K[選択ソート]
C --> L[計数ソート]
C --> M[基数ソート]
style D fill:#51cf66
style E fill:#ffa94d
style C fill:#74c0fc安定ソートと不安定ソートの違い
安定ソート: 同じ値の要素の相対順序が保たれる
// 例: (名前, 年齢) を年齢でソート
入力: [("Alice", 25), ("Bob", 25), ("Carol", 20)]
安定ソート結果: [("Carol", 20), ("Alice", 25), ("Bob", 25)]
// Alice と Bob の順序が保たれる
不安定ソート結果: [("Carol", 20), ("Bob", 25), ("Alice", 25)]
// Alice と Bob の順序が入れ替わる可能性がある
ソートアルゴリズム比較表
| アルゴリズム | 平均計算量 | 最悪計算量 | 空間計算量 | 安定性 | 特徴 |
|---|---|---|---|---|---|
| バブルソート | O(n^2) | O(n^2) | O(1) | 安定 | 実装が簡単、実用には遅い |
| 選択ソート | O(n^2) | O(n^2) | O(1) | 不安定 | 交換回数が少ない |
| 挿入ソート | O(n^2) | O(n^2) | O(1) | 安定 | ほぼ整列済みデータに強い |
| マージソート | O(n log n) | O(n log n) | O(n) | 安定 | 安定かつ高速、追加メモリ必要 |
| クイックソート | O(n log n) | O(n^2) | O(log n) | 不安定 | 実用最速、ピボット選択が重要 |
| ヒープソート | O(n log n) | O(n log n) | O(1) | 不安定 | 追加メモリ不要で安定した速度 |
クイックソートの動作
// クイックソートの基本的な流れ
function quicksort(arr, low, high):
if low < high:
pivot_index = partition(arr, low, high)
quicksort(arr, low, pivot_index - 1)
quicksort(arr, pivot_index + 1, high)
function partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
swap(arr[i], arr[j])
swap(arr[i + 1], arr[high])
return i + 1
graph TB
A["[3, 6, 8, 10, 1, 2, 1]"] --> B["pivot = 1"]
B --> C["左: [] | 右: [3, 6, 8, 10, 2, 1]"]
C --> D["pivot = 1"]
D --> E["左: [] | 右: [3, 6, 8, 10, 2]"]
E --> F["pivot = 2"]
F --> G["左: [] | 右: [3, 6, 8, 10]"]
G --> H["結果: [1, 1, 2, 3, 6, 8, 10]"]
style A fill:#74c0fc
style H fill:#51cf66コーディングテストでのポイント: 多くの言語の標準ソート関数は O(n log n) を保証しています。自分でソートを実装する必要はほぼありませんが、ソートの性質を理解していることが重要です。
3. 二分探索
二分探索は、ソート済み配列から目的の値を O(log n) で見つけるアルゴリズムです。コーディングテストで頻出のパターンです。
二分探索の動作イメージ
graph TB
A["配列: [1, 3, 5, 7, 9, 11, 13, 15]
目標値: 7"] --> B["left=0, right=7
mid=3, arr[3]=7"]
B --> C["arr[3] == 7 → 発見!"]
D["配列: [1, 3, 5, 7, 9, 11, 13, 15]
目標値: 11"] --> E["left=0, right=7
mid=3, arr[3]=7 < 11"]
E --> F["left=4, right=7
mid=5, arr[5]=11"]
F --> G["arr[5] == 11 → 発見!"]
style C fill:#51cf66
style G fill:#51cf66二分探索のテンプレート
// パターン1: 特定の値を見つける
function binary_search(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = left + (right - left) // 2 // オーバーフロー防止
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1 // 見つからない
// パターン2: 条件を満たす最小の位置（lower_bound）
// 「x 以上の最小の要素」のインデックスを返す
function lower_bound(arr, x):
left = 0
right = len(arr) // 注意: len(arr) であって len(arr)-1 ではない
while left < right: // 注意: <= ではなく <
mid = left + (right - left) // 2
if arr[mid] < x:
left = mid + 1
else:
right = mid // 注意: mid - 1 ではなく mid
return left
二分探索でよくある off-by-one バグ
| ミスのパターン | 症状 | 修正方法 |
|---|---|---|
right = len(arr) - 1 で lower_bound |
最後の要素を見逃す | right = len(arr) にする |
while left <= right で lower_bound |
無限ループ | while left < right にする |
right = mid - 1 で lower_bound |
答えの位置を飛ばす | right = mid にする |
mid = (left + right) / 2 |
整数オーバーフロー | mid = left + (right - left) / 2 |
// 二分探索の応用: 答えを二分探索する（二分探索 on answer）
// 例: N個のケーキを K人に分ける。1人あたりの最大サイズは？
function solve(cakes, K):
left = 0
right = max(cakes)
while right - left > 1e-9: // 実数の二分探索
mid = (left + right) / 2
if can_distribute(cakes, K, mid):
left = mid
else:
right = mid
return left
function can_distribute(cakes, K, size):
count = 0
for cake in cakes:
count += floor(cake / size)
return count >= K
4. 線形探索 vs 二分探索
graph LR
subgraph Linear["線形探索 O(n)"]
A1["[1]"] --> A2["[3]"] --> A3["[5]"] --> A4["[7]"] --> A5["[9]"] --> A6["[11]"]
end
subgraph Binary["二分探索 O(log n)"]
B1["[1, 3, 5, 7, 9, 11]"] --> B2["[7, 9, 11]"] --> B3["[9]"]
end
style A6 fill:#ff6b6b
style B3 fill:#51cf66| 特性 | 線形探索 | 二分探索 |
|---|---|---|
| 計算量 | O(n) | O(log n) |
| 前提条件 | なし | ソート済みであること |
| N=10^6 での比較回数 | 最大 10^6 回 | 最大 20 回 |
| 実装の難易度 | 低い | off-by-one に注意 |
| 使い所 | 小さいデータ、未ソート | 大きいソート済みデータ |
5. ガウスの等差数列の和
1 から N までの合計を O(1) で求める公式です。ループを回す必要がありません。
// O(n) のアプローチ
function sum_loop(n):
total = 0
for i in range(1, n + 1):
total += i
return total
// O(1) のアプローチ（ガウスの公式）
function sum_gauss(n):
return n * (n + 1) // 2
// 応用: a から b までの合計
function sum_range(a, b):
return sum_gauss(b) - sum_gauss(a - 1)
// 応用: 1~Nのうち特定の値が欠けている場合、欠けた数を求める
function find_missing(arr, n):
expected = n * (n + 1) // 2
actual = sum(arr)
return expected - actual
6. 尺取り法（Two Pointers）
ソート済み配列や連続部分配列に対して、2つのポインタを使って効率的に探索する手法です。O(n^2) を O(n) に改善できるケースが多くあります。
Two Pointers の動作
graph LR
A["配列: [1, 2, 3, 4, 6, 8, 11]
目標合計: 10"] --> B["left=0(1), right=6(11)
合計=12 > 10"]
B --> C["left=0(1), right=5(8)
合計=9 < 10"]
C --> D["left=1(2), right=5(8)
合計=10 == 10 → 発見!"]
style D fill:#51cf66// パターン1: ソート済み配列で合計が target になるペアを探す
function two_sum_sorted(arr, target):
left = 0
right = len(arr) - 1
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == target:
return (left, right)
elif current_sum < target:
left += 1
else:
right -= 1
return None // ペアが見つからない
// パターン2: 条件を満たす最長の連続部分配列
// 例: 合計が target 以下の最長部分配列の長さ
function max_length_subarray(arr, target):
left = 0
current_sum = 0
max_len = 0
for right in range(len(arr)):
current_sum += arr[right]
while current_sum > target:
current_sum -= arr[left]
left += 1
max_len = max(max_len, right - left + 1)
return max_len
Two Pointers が使えるパターン
| パターン | 説明 | 例 |
|---|---|---|
| 左右から挟む | ソート済み配列の両端からポインタを動かす | Two Sum (sorted) |
| 同方向に進む | 連続部分配列で左右のポインタが右に進む | 最長部分配列 |
| 速度差で進む | 2つのポインタが異なる速度で進む | 連結リストの環検出 |
💡 実践例
例題1: 配列の中から合計が K になるペアの数を求める
// 解法: ソートして Two Pointers
function count_pairs(arr, K):
sort(arr)
left = 0
right = len(arr) - 1
count = 0
while left < right:
s = arr[left] + arr[right]
if s == K:
// 重複処理
if arr[left] == arr[right]:
n = right - left + 1
count += n * (n - 1) // 2
break
else:
left_count = 1
right_count = 1
while arr[left] == arr[left + 1]:
left += 1
left_count += 1
while arr[right] == arr[right - 1]:
right -= 1
right_count += 1
count += left_count * right_count
left += 1
right -= 1
elif s < K:
left += 1
else:
right -= 1
return count
例題2: ソート済み配列で target 以上の最小値のインデックス
// 二分探索の典型応用
function find_first_ge(arr, target):
left = 0
right = len(arr)
while left < right:
mid = left + (right - left) // 2
if arr[mid] < target:
left = mid + 1
else:
right = mid
if left < len(arr):
return left
return -1 // target 以上の値が存在しない
// テスト
arr = [1, 3, 5, 7, 9, 11]
find_first_ge(arr, 6) // → 3 (arr[3] = 7)
find_first_ge(arr, 5) // → 2 (arr[2] = 5)
find_first_ge(arr, 12) // → -1
例題3: 1からNまでの整数のうち、欠けている数を見つける
// ガウスの公式を応用
function find_missing_number(arr, n):
expected_sum = n * (n + 1) // 2
actual_sum = sum(arr)
return expected_sum - actual_sum
// テスト
arr = [1, 2, 4, 5, 6] // 3が欠けている
find_missing_number(arr, 6) // → 21 - 18 = 3
📊 パフォーマンス比較
探索アルゴリズムの実行時間比較
| データサイズ (N) | 線形探索 O(n) | 二分探索 O(log n) | 改善倍率 |
|---|---|---|---|
| 1,000 | 1,000 回 | 10 回 | 100x |
| 100,000 | 100,000 回 | 17 回 | 5,882x |
| 1,000,000 | 1,000,000 回 | 20 回 | 50,000x |
| 10,000,000 | 10,000,000 回 | 24 回 | 416,667x |
ソートアルゴリズムの実測比較（N=100,000）
| アルゴリズム | 実行時間 | 備考 |
|---|---|---|
| バブルソート | 約 30 秒 | 実用には遅すぎる |
| 挿入ソート | 約 10 秒 | ほぼ整列済みなら高速 |
| マージソート | 約 0.05 秒 | 安定かつ高速 |
| クイックソート | 約 0.03 秒 | 平均最速 |
| 標準ライブラリ sort | 約 0.02 秒 | 最適化済み |
🎯 ベストプラクティス
1. 問題を読んだらまず制約を確認する
制約から逆算して、必要な計算量を見積もることが最も重要なステップです。
// 制約: N <= 10^5
// → O(n^2) は 10^10 で TLE
// → O(n log n) 以下のアルゴリズムが必要
2. 標準ライブラリのソートを信頼する
自分でソートを実装する代わりに、言語の標準ソート関数を使いましょう。
// Python
arr.sort() # インプレースソート
sorted_arr = sorted(arr) # 新しいリストを返す
arr.sort(key=lambda x: x[1]) # カスタムキーでソート
// JavaScript
arr.sort((a, b) => a - b) // 数値ソート（比較関数必須）
3. 二分探索は「条件の単調性」を確認する
二分探索が使えるのは、ある境界を境に True/False が切り替わる場合です。
// 使える: ソート済み配列で x 以上の最小値を探す
// [F, F, F, T, T, T] の最初の T を見つける
// 使えない: 配列が未ソートで値の大小が混在
// [T, F, T, F, T, F] では二分探索できない
4. Off-by-one エラーを防ぐテスト
二分探索を書いたら、以下のケースでテストしましょう。
// テストケース
// 1. 空の配列
// 2. 要素が1つの配列
// 3. target が先頭にある
// 4. target が末尾にある
// 5. target が配列に存在しない
// 6. target が全要素より小さい
// 7. target が全要素より大きい
5. Two Pointers は「何を left/right が表すか」を明確にする
// 明確な定義の例:
// left: 現在の部分配列の左端（含む）
// right: 現在の部分配列の右端（含む）
// 不変条件: arr[left..right] の合計は常に target 以下
🔍 関連する問題
この記事に関連するクイズ問題:
- Q2: 計算量に関する基本問題
- Q4: ソートアルゴリズムの特性
- Q7: 探索アルゴリズムの選択
- Q16: 二分探索の実装
- Q17: 計算量の見積もり
- Q19: 配列操作のアルゴリズム
- Q47: Two Pointers / 尺取り法
📝 まとめ
- Big O 記法: 入力サイズ N に対する処理時間の増加率を表す。定数倍は無視する
- 制約から逆算: N の上限から許容される計算量を判断し、アルゴリズムを選択する
- ソートの使い分け: 安定性・最悪計算量・空間計算量を考慮して選ぶ。基本は標準ライブラリを使う
- 二分探索: ソート済みデータや単調性のある条件で O(log n) の探索が可能。off-by-one に注意
- ガウスの公式: 1~N の和を O(1) で求められる。欠損値検出に応用可能
- Two Pointers: 2つのポインタで効率的に探索し、O(n^2) を O(n) に改善する
次のステップ: 実際に二分探索と Two Pointers の問題を解き、テンプレートを体に覚えさせましょう！