브루트포스 (Bruteforcing)

정의

브루트포스 (Bruteforcing, 완전 탐색) 는 가능한 모든 경우를 체계적으로 나열하고 검증하는 알고리즘. 프로그래밍 대회에서 가장 기초이자 가장 안전한 접근이며, 문제 크기가 충분히 작을 때 최적해를 보장한다.

대표 기법: 순열 (permutation), 조합 (combination), 부분집합 (subset, 비트마스크), 재귀적 백트래킹.

문제 상황과 동기

N 명의 사람을 배치하거나, M 개 중 K 개를 고르거나, 2^N 개 부분집합 중 조건을 만족하는 것을 찾아야 한다.

• naive (잘못된 접근): 단일 for 루프로 전부 시도하려 하면 구조 복잡.
• brute force (올바른 접근): 조합론 기법 (next_permutation, bitmask) 또는 재귀로 모든 경우를 명시적으로 생성. 탐색 범위가 10^6 이하면 대부분 가능.

핵심 통찰: 모든 가능성을 다 보면 절대 놓치지 않는다. 최적화가 불명확할 때는 일단 완전 탐색으로 정답을 찾고, 시간 내에 들어오면 그대로 제출.

PS 에서 “N ≤ 10” 같은 제약은 브루트포스 신호.

시각화

핵심 아이디어

가능한 모든 후보를 생성하고 각 후보를 검증.

candidates = generate_all()
answer = null
for c in candidates:
    if is_valid(c):
        if is_better(c, answer):
            answer = c

invariant: 지금까지 본 후보 중 최적해를 유지. 전부 보면 전역 최적.

대표 구현 패턴:

• 순열 (permutation): STL next_permutation 또는 swap 재귀. O(N!).
• 조합 (combination): DFS 또는 C(N, K) 생성. O(N choose K).
• 부분집합 (subset): 비트마스크 0..2^N-1 또는 DFS. O(2^N).
• 백트래킹 (backtracking): 조건 위반시 조기 종료해 상수 감소. 최악 복잡도는 동일하지만 평균 케이스 훨씬 빠름.

알고리즘

비트마스크로 부분집합 열거

for mask = 0 to 2^N - 1:
    subset = []
    for i = 0 to N-1:
        if mask & (1 << i):
            subset.append(a[i])
    if is_valid(subset):
        update_answer(subset)

재귀로 조합 생성 (C(N, K))

def choose(idx, chosen):
    if len(chosen) == K:
        process(chosen)
        return
    if idx == N:
        return
    choose(idx+1, chosen + [a[idx]])   # 선택
    choose(idx+1, chosen)               # 건너뜀

구현

// 비트마스크로 2^N 부분집합 열거
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n; cin >> n;
  vector<int> a(n);
  for (auto& v : a) cin >> v;
  int max_sum = -1e9;
  for (int mask = 0; mask < (1 << n); mask++) {
      int sum = 0;
      for (int i = 0; i < n; i++) {
          if (mask & (1 << i))
              sum += a[i];
      }
      max_sum = max(max_sum, sum);
  }
  cout << max_sum << "\n";
}

# itertools.combinations 로 조합 열거
from itertools import combinations
n = int(input())
a = list(map(int, input().split()))
max_sum = -int(1e9)
for r in range(n + 1):
  for subset in combinations(a, r):
      max_sum = max(max_sum, sum(subset))
print(max_sum)

// 비트마스크 부분집합
import java.util.*;
public class Main {
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int[] a = new int[n];
      for (int i = 0; i < n; i++) a[i] = sc.nextInt();
      int maxSum = Integer.MIN_VALUE;
      for (int mask = 0; mask < (1 << n); mask++) {
          int sum = 0;
          for (int i = 0; i < n; i++)
              if ((mask & (1 << i)) != 0)
                  sum += a[i];
          maxSum = Math.max(maxSum, sum);
      }
      System.out.println(maxSum);
  }
}

4
1 -2 3 4

8

3
-5 -3 -7

0

복잡도

T_check = 한 후보 검증 비용. 부분집합 합이면 O(N), 순열 조건이면 O(N^2) 등.

실전 분기점

백트래킹 가지치기가 강하면 N=15 순열도 가능할 수 있음 (상수 큰 폭 감소).

변형

1. next_permutation (C++ STL)

sort(a.begin(), a.end());
do {
    // process permutation a
} while (next_permutation(a.begin(), a.end()));

O(N!) 번 순열 생성. 사전순 순서 보장.

2. 백트래킹 (Backtracking)

조건 위반 시 더 이상 탐색하지 않음. N-Queen 같은 제약 만족 문제.

void bt(int depth, vector<int>& chosen) {
    if (pruning_condition()) return;  // 가지치기
    if (depth == target) {
        process(chosen);
        return;
    }
    for (int i = 0; i < N; i++) {
        chosen.push_back(i);
        bt(depth + 1, chosen);
        chosen.pop_back();
    }
}

3. 중간에서 만나기

N=40 부분집합을 앞 20 / 뒤 20 으로 나눠 각각 2^20, 합쳐서 O(2^20 log 2^20).

함정

1. 중복 순열 vs 조합

“3개 중 2개를 뽑는다” 가 순서를 고려하면 P(3,2)=6, 순서 무관이면 C(3,2)=3. 문제 조건 정확히 읽기.

2. 비트마스크 범위 초과

1 << 30 은 int 범위 내 (2^30 ≈ 1e9), but 1 << 31 은 부호 비트. 1LL << i 또는 unsigned 사용.

3. 시간 초과 낙관

“N=20 이면 2^20=1M 여유있다” 가 아니라, 내부 루프 비용까지 곱해야. 부분집합 합 문제면 O(2^N · N), N=20 이면 20M, 타이트. N=25 면 800M, 아슬아슬하거나 TLE.

4. 공간 초과

모든 후보를 메모리에 저장하면 N! / 2^N 개 배열. 거의 항상 불가능. 생성과 동시에 검증/업데이트.

BOJ 연습 문제

참고

• 백트래킹
• 비트마스크
• 중간에서 만나기
• 재귀