brute force とは何で、いつ許容されますか？

Question

Accepted Answer

**Brute force** は答えが見つかるまで可能な candidate をすべて試すことです。simple で guaranteed correct ですが、多くの場合遅く、O(n²) や exponential になりがちです。

## 考え方

clever shortcut なしで solution space を exhaustive に enumerate します。

## 例: target sum の pair を探す（brute force）

```python
def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):  # every pair を check
            if nums[i] + nums[j] == target:
                return (i, j)
    return None
# O(n^2) time, O(1) space
```

hash map を使えば O(n) にできますが、brute-force version は obvious starting point です。

## 許容される場合

- **small inputs** で n と constant factor が小さい。
- faster algorithm を検証する **correctness baseline** として。
- rare にしか実行されず、clarity が speed に勝る場合。
- interview では最初に述べ、その後 optimize する。

## pitfalls

large input で brute force は timeout を起こします。commit する前に solution space の size を必ず estimate します。

## なぜ重要なのか

brute force は honest first solution です。問題が解けることを示し、"correct" の意味を明確にします。optimization を test する reference implementation にもなります。O(n²) 以上でも十分な場面を知ることは real engineering skill です。すべての問題に clever algorithm が必要なわけではありません。