Brute Force: 완전 탐색

Brute Force, 완전 탐색, brute force

정의

Brute Force 는 문제의 모든 후보 해를 하나씩 검증하는 접근. 최적은 아니지만 정확 하고 명확 하며, 큰 문제에도 부분 검증 도구로 사용.

패턴

• 모든 부분집합: for mask in 0..2^n
• 모든 순열: next_permutation 또는 재귀
• 모든 조합: nested loop 또는 combinations
• 모든 위치: nested for

언제 유효한가

• N ≤ 20 subset (2^N ≤ 10⁶)
• N ≤ 10 permutation (10! ≈ 3.6M)
• N ≤ 100 quadratic (10⁴)
• N ≤ 1000 quadratic (10⁶)

최적화로 발전

• 가지치기 (pruning) → Branch and Bound
• 메모이제이션 → DP
• 비트마스크 → Bitmask DP

참고

• Branch and Bound
• DP Bitfield