Overview
全探索（Brute Force Search） とは、すべての可能性を力ずくで試すアルゴリズム。
1.選択ソートの基本
2.選択ソートの特徴
3.典型問題を解いてみる
1. 全探索のパターン
| 探索方法 | 説明 | 使用例 |
|---|---|---|
| 1重ループ | リストを1回スキャンする | 最大値、最小値探索 |
| 2重ループ | すべてのペアを調べる | 2つの和が条件を満たすペア探索 |
| 3重ループ | すべての3つ組を調べる | 3つの和が条件を満たす組み合わせ探索 |
| 再帰的全探索（バックトラッキング） | 状態を保持しながら再帰で探索 | パス探索、ナップサック問題 |
| ビット全探索 | すべての部分集合を試す | すべての組み合わせを列挙 |
2. 1重ループを使った全探索
リストの中から 最大値 を求める。
arr = [3, 1, 4, 1, 5, 9]
max_value = -float('inf')
for num in arr:
max_value = max(max_value, num)
print(max_value) # 9
ポイント:
・$O(N)$ でリスト全体を探索する
・最適化せずにシンプルに実装するのが全探索の基本
3. 2重ループを使った全探索
(1) すべてのペアを探索
arr = [1, 3, 5, 7]
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
print(arr[i], arr[j])
ポイント:
・2つの要素の組み合わせを総当たりで試す
・$O(N²)$の計算量になる
(2) 指定の条件を満たすペアを探す
例: 数列 A の中で、A[i] + A[j] = X となる (i, j) のペアを探す。
A = [1, 2, 3, 4, 5]
X = 6
for i in range(len(A)):
for j in range(i + 1, len(A)):
if A[i] + A[j] == X:
print(f"Pair: {A[i]}, {A[j]}")
ポイント:
・2重ループでペアをすべて試す
・より効率的な方法（ハッシュセットを使う）と比較できる
4. 3重ループを使った全探索
例: $A[i] + A[j] + A[k] = X$ となる (i, j, k) の組み合わせを探す。
A = [1, 2, 3, 4, 5]
X = 6
for i in range(len(A)):
for j in range(i + 1, len(A)):
for k in range(j + 1, len(A)):
if A[i] + A[j] + A[k] == X:
print(f"Triplet: {A[i]}, {A[j]}, {A[k]}")
ポイント:
・3重ループで全パターンを探索
・$O(N³)$の計算量になるが、小さなデータセットなら問題ない
5. ビット全探索
例: N 個の要素のすべての部分集合を列挙する。
A = [1, 2, 3]
N = len(A)
for bit in range(1 << N): # 2^N 通りの部分集合
subset = [A[i] for i in range(N) if bit & (1 << i)]
print(subset)
ポイント:
・すべての部分集合を列挙
・$O(2^N)$の計算量なので N ≤ 20 程度まで
6. 典型問題を解いてみる
例題1. 2つの和が条件を満たすペア
問題: N 個の整数が与えられる。A[i] + A[j] = X となる (i, j) のペアが存在するか判定せよ。
回答
N, X = map(int, input().split())
A = list(map(int, input().split()))
for i in range(N):
for j in range(i + 1, N):
if A[i] + A[j] == X:
print("Yes")
exit()
print("No")
例題2. 3つの和が条件を満たす組み合わせ
問題: N 個の整数が与えられる。A[i] + A[j] + A[k] = X となる (i, j, k) の組み合わせを探せ。
回答
N, X = map(int, input().split())
A = list(map(int, input().split()))
for i in range(N):
for j in range(i + 1, N):
for k in range(j + 1, N):
if A[i] + A[j] + A[k] == X:
print(A[i], A[j], A[k])
例題3. ビット全探索
問題: N 個の整数から、すべての部分集合の和を出力せよ。
回答
N = int(input())
A = list(map(int, input().split()))
for bit in range(1 << N):
subset_sum = sum(A[i] for i in range(N) if bit & (1 << i))
print(subset_sum)
例題4. 文字列の全探索
問題: 長さ N の文字列 S が与えられる。S に "abc" が含まれるか判定せよ。
回答
S = input()
N = len(S)
for i in range(N - 2):
if S[i:i+3] == "abc":
print("Yes")
exit()
print("No")