브루트 포스(Brute Force, 완전 탐색)는 가능한 모든 경우를 시도해 답을 찾는 알고리즘이다. 구현이 단순하고 항상 정답을 보장하지만, 시간 복잡도가 높다. 최적화 없이 문제를 풀 때 출발점이 된다.
접근 방식
1. 반복문 (For Loop)
2. 재귀 (Recursion)
3. 비트마스크 (모든 부분집합)
4. 순열 (Permutation)
순열 완전 탐색
python
from itertools import permutations
# 모든 순열 탐색
def tsp_brute_force(distances):
n = len(distances)
cities = list(range(1, n))
min_cost = float('inf')
for perm in permutations(cities):
path = [0] + list(perm) + [0]
cost = sum(distances[path[i]][path[i+1]]
for i in range(len(path)-1))
min_cost = min(min_cost, cost)
return min_cost
비트마스크 완전 탐색
python
# 모든 부분집합 탐색
def find_subsets(arr):
n = len(arr)
result = []
for mask in range(1 << n): # 0 ~ 2^n - 1
subset = [arr[i] for i in range(n) if mask & (1 << i)]
result.append(subset)
return result
find_subsets([1, 2, 3])
# [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]
브루트 포스 → 최적화
완전 탐색 O(2ⁿ)
↓ 백트래킹 (가지치기)
적절한 복잡도 감소
↓ 동적 프로그래밍 (중복 제거)
O(n²) ~ O(n³)
관련 개념
참고문헌
- •코딩 테스트 전략: 브루트 포스 → 최적화 패턴
