brute force(무차별 대입)란 무엇이며 언제 허용되나요?

Question

IT Interview Practice · Accepted Answer

**Brute force(무차별 대입)**는 답을 찾을 때까지 가능한 모든 후보를 시도하는 것을 의미합니다. 단순하고 정확성이 보장되지만, 종종 느립니다 — 흔히 지수 시간이나 O(n²)입니다.

## 개념

영리한 지름길 없이 해 공간을 남김없이 열거합니다.

## 예시: 목표 합이 되는 쌍 찾기 (brute force)

```python
def two_sum_brute(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
# O(n^2) 시간, O(1) 공간
```

해시 맵을 사용하면 이를 O(n)으로 바꿀 수 있지만, brute-force 버전은 명백한 출발점입니다.

## 언제 허용되나

- 상수 인자와 n이 작은 **작은 입력**일 때.
- 더 빠른 알고리즘을 검증하기 위한 **정확성 기준선**으로.
- 문제가 드물게 실행되어 속도보다 명료함이 중요할 때.
- 면접 중에는 먼저 이것을 말한 뒤 최적화하세요.

## 함정

큰 입력에 대한 brute force는 타임아웃을 유발합니다. 시작하기 전에 항상 해 공간의 크기를 추정하세요.

## 왜 중요한가

Brute force는 정직한 첫 해법입니다. 문제가 풀 수 있음을 증명하고 "정확함"이 정확히 무엇을 의미하는지 명확히 합니다.

최적화를 테스트할 참조 구현을 제공합니다.

O(n²) 또는 그 이상이 *충분히 좋은* 경우를 아는 것은 실제 엔지니어링 역량입니다 — 모든 문제가 영리한 알고리즘을 필요로 하는 것은 아닙니다.

개념

예시: 목표 합이 되는 쌍 찾기 (brute force)

관련 질문

언제 허용되나

함정

왜 중요한가