完全探索 — Brute Force
このトピックを終えると
完全探索が適切な状況を判断できるようになり、繰り返し文、順列、組み合わせを活用して、すべてのケースを体系的に探索できるようになります。
最も確実な方法
パスワードが4桁の数字である場合、0000から9999まですべて試せば必ず見つかります。これが完全探索（Brute Force、Exhaustive Search）です。
# 4桁の数字パスワードを全件調査for code in range(10000): if check(code): print(f"パスワード: {code:04d}") break10,000個。コンピューターにとっては一瞬です。
完全探索の核心: 「漏れがないので、必ず答えが得られる」。正確性が保証されることが最大の長所です。
いつ使うか
ケースの数が十分に少ないときに完全探索を使います。
1秒あたり約1億（10^8）回の演算が可能な場合：
n ≤ 20 → 2^20 = 約100万 ✅
n ≤ 10 → 10! = 約360万 ✅
n ≤ 8 → 8! = 40,320 ✅
n ≤ 25～30 → 2^30 = 約10億 ⚠️ タイムアウトの危険性コーディングテストで入力のサイズが小さい場合（n ≤ 20程度）、まず完全探索を思いつくべきです。複雑なアルゴリズムを使う前に、「単純にすべて試せば良いのではないか」を最初に確認することです。
パターン1 — ネストされた繰り返し文
最も基本的な形です。
# 2つの数の合計がターゲットであるペアを見つけるdef two_sum(nums, target): for i in range(len(nums)): for j in range(i + 1, len(nums)): if nums[i] + nums[j] == target: return [i, j] return None
print(two_sum([2, 7, 11, 15], 9)) # [0, 1]すべてのペアを試します。O(n²)ですが、nが小さい場合は十分です。
パターン2 — 順列（Permutation）
順序が重要なすべてのケース：
from itertools import permutations
# [1, 2, 3]のすべての配列の順序for p in permutations([1, 2, 3]): print(p)# (1, 2, 3)# (1, 3, 2)# (2, 1, 3)# (2, 3, 1)# (3, 1, 2)# (3, 2, 1)n個の順列はn!個です。3! = 6、5! = 120、10! = 3,628,800。
# 数字カードで作成できる最も大きい数cards = [3, 1, 4]max_num = 0for p in permutations(cards): num = int("".join(map(str, p))) max_num = max(max_num, num)
print(max_num) # 431パターン3 — 組み合わせ（Combination）
順序が関係ないすべてのケース：
from itertools import combinations
# 5人の中から3人を選ぶすべての方法people = ["A", "B", "C", "D", "E"]for team in combinations(people, 3): print(team)# ('A', 'B', 'C')# ('A', 'B', 'D')# ('A', 'B', 'E')# ... 合計10個 (5C3 = 10)# 与えられたメニューから2つを選んで、合計が最も安い組み合わせprices = {"ラーメン": 3500, "おにぎり": 2500, "トッポギ": 4000, "スンデ": 3000}items = list(prices.items())
cheapest = float('inf')best_combo = Nonefor combo in combinations(items, 2): total = combo[0][1] + combo[1][1] if total < cheapest: cheapest = total best_combo = (combo[0][0], combo[1][0])
print(f"{best_combo}: {cheapest}円") # ('おにぎり', 'スンデ'): 5500円パターン4 — ビットマスク
各要素を「選択/非選択」に分ける部分集合の問題：
# n個の部分集合 = 2^n個items = ["リンゴ", "バナナ", "チェリー"]n = len(items)
for mask in range(1 << n): # 0 ～ 2^n - 1 subset = [] for i in range(n): if mask & (1 << i): subset.append(items[i]) print(subset)
# []# ['リンゴ']# ['バナナ']# ['リンゴ', 'バナナ']# ['チェリー']# ['リンゴ', 'チェリー']# ['バナナ', 'チェリー']# ['リンゴ', 'バナナ', 'チェリー']1 << nは2^nです。ビット1つが「この要素を含めるかどうか」を決定します。
完全探索から最適化へ
完全探索でまず正解を得た後、パフォーマンスが不足している場合に最適化します。
| 完全探索 | → | 最適化手法 |
|---|---|---|
| すべてのペア (O(n²)) | → | ハッシュマップ (O(n)) |
| すべての部分和 | → | 2ポインター、スライディングウィンドウ |
| すべてのパス | → | DP（メモ化） |
| 全件調査 | → | 枝刈り（pruning） |
コーディングテストの解法手順：
- 完全探索で正確な解法をまず作成
- タイムアウトになったら規則性を見つけて最適化
- 最適化された解法が完全探索と同じ答えを出すか検証
核心のまとめ
| 方法 | ケースの数 | 使用ツール |
|---|---|---|
| ネストされた繰り返し文 | O(n^k) | for文 |
| 順列 | n! | itertools.permutations |
| 組み合わせ | nCr | itertools.combinations |
| 部分集合 | 2^n | ビットマスク |
バックトラッキング — 枝刈りが付いた完全探索
完全探索で「この方向は答えになり得ない」と判断した場合、さらに進まずに引き返す手法です。
# N-Queen問題：N×Nのチェス盤にN個のクイーンを互いに攻撃できないように配置def solve_nqueens(n): solutions = []
def backtrack(queens, row): if row == n: solutions.append(queens[:]) return
for col in range(n): if is_safe(queens, row, col): queens.append(col) backtrack(queens, row + 1) queens.pop() # 巻き戻し（backtrack）
def is_safe(queens, row, col): for r, c in enumerate(queens): if c == col or abs(r - row) == abs(c - col): return False return True
backtrack([], 0) return solutions
print(len(solve_nqueens(8))) # 92個の解8×8のチェス盤で可能なすべての配置は約43億個ですが、枝刈りによって実際に探索するケースの数は数千個レベルに減ります。
再帰 vs 繰り返し文の選択
# 再帰 — ツリー構造の探索に自然def find_all_paths(graph, start, end, path=[]): path = path + [start] if start == end: return [path] paths = [] for node in graph[start]: if node not in path: paths.extend(find_all_paths(graph, node, end, path)) return paths
# 繰り返し文 — 単純な列挙に適しているfor i in range(n): for j in range(i + 1, n): check(arr[i], arr[j])ネストされた繰り返し文は深さが決まっている場合、再帰は深さが可変の場合に使用します。Pythonの再帰の深さの制限（デフォルト1000）に注意してください。
時間制限の感覚
コーディングテストで時間制限（通常1〜2秒）に合わせるには、演算回数を推測する必要があります。
Python基準（おおよその感覚）：
10^6 演算 → ～0.1秒
10^7 演算 → ～1秒
10^8 演算 → ～10秒（タイムアウト）# n=10 → 2^10 = 1,024 → 完全探索可能# n=20 → 2^20 = 1,048,576 → 可能だがやや厳しい# n=30 → 2^30 = 1,073,741,824 → タイムアウト# n! → n=10なら3,628,800、n=12なら479,001,600| nの範囲 | 可能な複雑度 | 手法 |
|---|---|---|
| ≤ 10 | O(n!) | 順列完全探索 |
| ≤ 20 | O(2^n) | 部分集合/ビットマスク |
| ≤ 1,000 | O(n²) | 二重for文 |
| ≤ 100,000 | O(n log n) | ソート + 二分探索 |
| ≤ 10,000,000 | O(n) | 線形探索、ハッシュ |
入力のサイズを見て、どのような複雑度が通過するかをまず判断することで、完全探索を試すか、すぐに最適化するかを決定できます。
完全探索は「無茶な方法」ではありません。正確な答えを保証する基準線であり、より良いアルゴリズムの出発点です。