브루트포스 기초

배열의 모든 정보를 선형 탐색한다.

#include <stdio.h>
int main() {
    int arr[100];
    for (int i = 0; i < 100; i++) {
        scanf("%d", arr[i]);
    }
    int sum= 0;
    for (int i = 0; i < 100; i++) {
        sum += arr[i];
    }
    printf("%d", sum);

브루트포스를 제대로 쓰려면

"모든 경우를 다 해 본다"는 개념은 익혔다고 보고, 여기서는 언제 브루트포스가
통하는지 판단하는 법과 경우를 빠짐없이 만드는 설계를 다룹니다. 이게 브루트포스의
진짜 실력입니다.

1. 핵심 질문: 경우의 수는 몇 개인가?

브루트포스의 성패는 단 하나, "전부 해 봐도 시간 안에 끝나는가?" 입니다. 그러니
풀기 전에 경우의 수를 먼저 어림셈하세요.

대략적인 기준(1초 = 약 \(10^8\)번 연산):

예: \(N \le 100\)일 때 모든 쌍은 \(N^2 = 10^4\), 모든 세 쌍은 \(N^3 = 10^6\) — 둘 다 OK.

2. "경우"를 만드는 흔한 형태

• 모든 한 개 고르기 : 1중 반복.
• 모든 쌍 고르기 : 2중 반복(j = i+1).
• 모든 부분집합 : 각 원소를 넣거나 뺀다(\(2^N\)가지) — N이 작을 때만.
• 모든 좌표 검사 : 격자 전체 2중 반복.

// 세 수의 합이 목표가 되는 경우 찾기 (N^3)
for (int i = 0; i < n; i++)
  for (int j = i+1; j < n; j++)
    for (int k = j+1; k < n; k++)
      if (a[i]+a[j]+a[k] == target) { /* 찾음 */ }

3. 빠짐없이, 중복 없이

브루트포스의 두 원칙입니다.

• 빠짐없이 : 답이 될 수 있는 모든 후보를 반드시 포함.
• 중복 없이 : 같은 경우를 두 번 세지 않기(쌍은 j>i로).

후보를 빠뜨리면 오답, 중복하면 개수가 틀립니다. 범위를 종이에 적어 확인하세요.

4. 가지치기로 빨라지기 (맛보기)

"이미 답이 될 수 없는 경우"는 일찍 건너뛰면 빨라집니다.

if (현재까지_합 > target) continue;   // 더 봐도 소용없음

이 발상을 본격적으로 키우면 백트래킹이 됩니다(Silver에서 배움).

정리

• 풀기 전에 경우의 수를 어림셈 — \(10^8\)이 분기점.
• 한 개/쌍/부분집합/격자 — 경우를 만드는 표준 형태.
• 빠짐없이 + 중복 없이가 두 원칙.
• 불가능한 경우는 일찍 버리면(가지치기) 빨라진다.

브루트포스 구현 레퍼런스

대표 브루트포스 패턴 — 모든 쌍, 부분집합, 격자 전수 검사 — 을 코드로 정리하고
함정을 짚습니다.

1. 모든 쌍/세 쌍 검사

int n; cin >> n;
int a[1000];
for (int i = 0; i < n; i++) cin >> a[i];

int best = 0;
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        best = max(best, a[i] + a[j]);   // 두 수 합의 최대
cout << best << '\n';

a = list(map(int, input().split()))
best = max(a[i] + a[j] for i in range(len(a)) for j in range(i+1, len(a)))
print(best)

2. 모든 부분집합 (비트로 표현)

원소가 적을 때(\(N \le 20\) 정도) 각 원소를 넣고/빼는 모든 조합을 봅니다.

int n; cin >> n;        // 작은 N
for (int mask = 0; mask < (1 << n); mask++) {   // 0 ~ 2^n - 1
    int sum = 0;
    for (int i = 0; i < n; i++)
        if (mask & (1 << i)) sum += a[i];        // i번째를 골랐다면
    // sum = 이 부분집합의 합
}

from itertools import combinations
# 모든 부분집합을 직접:
for mask in range(1 << n):
    chosen = [a[i] for i in range(n) if mask & (1 << i)]
    s = sum(chosen)

1 << n은 \(2^n\)입니다. N이 조금만 커도 폭발하니 N 한계를 꼭 확인하세요.

3. 격자 전수 검사

// 모든 시작 칸에서 어떤 모양이 들어가는지 검사
for (int i = 0; i + H <= n; i++)        // H, W 크기 도형
    for (int j = 0; j + W <= m; j++) {
        // (i,j)를 좌상단으로 하는 영역 검사
    }

가능한 모든 위치를 빠짐없이 시도하는 전형적 격자 브루트포스입니다.

4. 함정과 패턴 인식

• 경우의 수 폭발 — N이 큰데 \(2^N\)이나 \(N^3\)을 돌리면 시간 초과. 먼저 어림셈.
• 중복 카운팅 — 쌍은 j>i, 같은 조합을 두 번 세지 않기.
• 후보 누락 — 범위(<= vs <)를 잘못 잡아 끝 경우를 빠뜨림.
• 오버플로 — 합/곱이 클 수 있으면 long long.

문제에 "가능한 모든", "N이 작다(≤20, ≤100)", "최대/최소가 되는 경우를 찾아라",
"모든 위치를 시도" 같은 신호가 보이면 브루트포스입니다.

정리

브루트포스 구현은 (1) 먼저 경우의 수 어림셈, (2) 한 개/쌍/부분집합/격자의 표준
틀로 모든 후보 생성, (3) 빠짐없이·중복 없이, (4) 합·곱은 long long — 이 흐름을
따르면 됩니다. N이 작다는 조건은 거의 항상 "전부 해 봐라"는 신호입니다.