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