완전 탐색

탐색 공간을 체계적으로 전부 뒤지는 설계법.

실버 V

선수 지식: 브루트포스 기초

1강 모든 경우를 빠짐없이 세는 사고법 공식

완전 탐색이란?

완전 탐색(brute force) 은 답이 될 수 있는 모든 후보를 빠짐없이, 겹치지 않게
만들어 보고 그중 조건을 만족하는 것을 고르는 가장 정직한 풀이법입니다. 똑똑한
알고리즘을 떠올리기 전에, "경우의 수가 얼마나 되는가?" 를 먼저 따져 보는 것이
문제 풀이의 출발점입니다.

완전 탐색이 통하는지 판단하는 기준은 단 하나, 경우의 수 × 한 경우를 확인하는 비용
이 제한 시간 안에 들어오느냐입니다. 보통 1초에 약 $$10^8$$ 번의 연산을 기준으로 잡습니다.

1. 탐색 공간의 크기 가늠하기

후보가 어떤 모양인지에 따라 경우의 수가 정해집니다.

후보의 모양	경우의 수	예시
$$N$$ 개 중 하나 고르기	$$N$$	최댓값 찾기
두 개 고르기(순서 무관)	$\binom{N}{2} \approx \frac{N^2}{2}$	모든 쌍
각 칸을 켜고 끄기	$$2^N$$	부분집합
순서까지 정하기	$$N!$$	순열

예를 들어 $N \le 20$ 이면 $2^N \approx 10^6$ 이라 부분집합 전체 탐색이 가능하지만,
$N \le 1000$ 에서 $$2^N$$ 은 우주의 원자 수보다 큽니다. 제한을 보고 어떤 모양의
완전 탐색이 허용되는지 거꾸로 읽어 내는 연습이 중요합니다.

2. 가장 기본: 이중 반복문으로 모든 쌍 보기

"두 수를 더해 목표가 되는 쌍이 있는가?" 같은 문제는 모든 쌍을 봅니다.

bool found = false;
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)   // i+1부터: 같은 쌍을 두 번 안 본다
        if (a[i] + a[j] == target) found = true;

경우의 수는 $\binom{N}{2}$ , 즉 $$O(N^2)$$ 입니다. $N \le 5000$ 정도까지 안전합니다.

3. 완전 탐색의 가치

완전 탐색은 느려 보여도 반드시 맞는 답을 준다는 큰 장점이 있습니다. 그래서
두 가지 용도로 늘 쓰입니다.

작은 입력에서는 그 자체로 정답. 제한이 작다면 굳이 어려운 알고리즘을 쓸
이유가 없습니다.
빠른 풀이의 검증기(brute). 효율적인 풀이를 짠 뒤, 작은 입력에서 완전 탐색과
답을 맞춰 보면 버그를 잡을 수 있습니다.

4. 복잡도 감각 익히기

$$N = 100$$ 일 때 각 풀이의 연산량을 비교해 보겠습니다.

$$O(N^2) = 10^4$$ — 순식간
$$O(N^3) = 10^6$$ — 충분히 빠름
$$O(2^N)$$ — $2^{100}$ , 절대 불가능
$$O(N!)$$ — $$100!$$ , 불가능

같은 $$N$$ 이라도 탐색 공간의 모양에 따라 하늘과 땅 차이가 납니다. "무엇을
고르는 문제인가" 를 먼저 정의하면 경우의 수가 자동으로 따라 나옵니다.

정리

완전 탐색의 핵심은 알고리즘이 아니라 태도입니다. 문제를 만나면

답의 후보가 어떤 모양인지 정의하고,
그 개수를 제한과 비교해 보고,
통하면 망설임 없이 전부 시도한다.

이 습관이 Silver 이후 모든 탐색·DP·백트래킹의 토대가 됩니다.

2강 순열·부분집합 생성과 구현 패턴 공식

완전 탐색을 코드로 옮기기

후보를 빠짐없이, 중복 없이 만들어 내는 정형화된 도구들을 익히면 완전 탐색
문제의 대부분을 기계적으로 풀 수 있습니다. 여기서는 부분집합과 순열을 만드는
표준 방법을 다룹니다.

1. 부분집합 — 비트로 켜고 끄기

$$N$$ 개의 원소 각각을 "넣는다/뺀다"로 보면, $$0$$ 부터 $$2^N - 1$$ 까지의 정수가 곧
모든 부분집합입니다. 정수의 $$i$$ 번째 비트가 켜져 있으면 $$i$$ 번 원소를 넣습니다.

for (int mask = 0; mask < (1 << n); mask++) {
    long long sum = 0;
    for (int i = 0; i < n; i++)
        if (mask & (1 << i))   // i번 비트가 켜졌는가
            sum += a[i];
    // sum = 이 부분집합의 합
}

for mask in range(1 << n):
    s = 0
    for i in range(n):
        if mask & (1 << i):   # i번 비트가 켜졌는가
            s += a[i]
    # s = 이 부분집합의 합

복잡도는 $O(2^N \cdot N)$ 입니다. $N \le 20$ 이 안전한 상한입니다.

2. 순열 — 라이브러리를 쓰자

"N개를 줄 세우는 모든 순서"가 필요하면 직접 만들지 말고 표준 도구를 씁니다.

#include <bits/stdc++.h>
using namespace std;
int a[] = {1, 2, 3};
int main() {
    sort(a, a + 3);          // 반드시 정렬된 상태에서 시작
    do {
        for (int x : a) cout << x << ' ';
        cout << '\n';
    } while (next_permutation(a, a + 3));
}

from itertools import permutations
for p in permutations([1, 2, 3]):
    print(p)

next_permutation은 사전순으로 다음 순열을 만들어 주며, 더 큰 순열이 없으면
false를 돌려줍니다. 그래서 반드시 정렬된 상태에서 시작해야 모든 순열을
한 번씩 봅니다.

3. 직접 재귀로 만들기 (선택의 일반형)

라이브러리가 없는 상황이나 더 일반적인 선택(예: $$N$$ 개 중 $$M$$ 개 고르기)은
재귀로 만듭니다.

int n, m;
int chosen[20];
void rec(int start, int depth) {
    if (depth == m) {            // m개를 다 골랐다
        for (int i = 0; i < m; i++) cout << chosen[i] << ' ';
        cout << '\n';
        return;
    }
    for (int i = start; i < n; i++) {
        chosen[depth] = i + 1;
        rec(i + 1, depth + 1);   // i+1: 다음 단계는 더 큰 것만
    }
}

start로 "이전에 고른 것보다 큰 것만 고르기"를 강제해 조합(순서 무관) 을
중복 없이 만듭니다. start 대신 매번 0부터 돌면서 방문 표시를 쓰면 순열이
됩니다.

4. 흔히 하는 실수

중복 카운팅 — 쌍을 셀 때 j를 i+1이 아니라 0부터 돌리면 같은 쌍을
두 번 셉니다. 순서가 무관하면 항상 i+1부터.
순열 전에 정렬을 빼먹음 — next_permutation은 정렬 안 된 배열로 시작하면
일부 순열을 놓칩니다.
1 << n 오버플로 — n이 31 이상이면 1 << n이 int 범위를 넘습니다.
1LL << n을 쓰세요(애초에 그 크기면 완전 탐색이 불가능하긴 합니다).

5. 패턴 알아보기

문제에서 다음 신호가 보이면 완전 탐색을 의심하세요.

$$N$$ 이 유난히 작다( $N \le 20$ 부근).
"가능한 모든 방법 중", "최대/최소가 되도록 고르면" 같은 표현.
답의 형태가 "고른다 / 배치한다 / 순서를 정한다"로 환원된다.

후보의 모양을 정하고, 위 세 도구(비트마스크·순열·재귀 선택) 중 맞는 것을 끼우면
됩니다.

3강 실전 가이드 — 제한을 보고 완전 탐색을 택하는 법 공식

실전에서 완전 탐색 문제 알아보기

원리와 생성 패턴을 배웠으니, 이번에는 실제 문제 앞에서 완전 탐색을 골라내고
끝까지 맞히는 과정을 다룹니다.

1. 출제 신호

문제에서 다음이 보이면 완전 탐색을 1순위로 의심하세요.

$$N$$ 이 유난히 작다. $N \le 10$ 이면 순열( $$N!$$ )까지, $N \le 20$ 이면
부분집합( $$2^N$$ )까지 허용이라는 출제자의 신호입니다.
"가능한 모든 ~ 중에서 최대/최소" 라는 표현이 있는데, 조건이 여러 개
얽혀 있어 수식 한 줄로 답이 나오지 않습니다.
답이 "무엇을 고른다 / 어디에 놓는다 / 어떤 순서로 한다" 로 환원됩니다.
조건이 지저분하고 예외가 많습니다. 똑똑한 풀이가 어려울수록 출제자는
제한을 줄여 완전 탐색을 열어 둡니다.

2. 풀이 결정 절차

후보의 모양을 정의합니다 — 고르기인가, 배치인가, 순서인가?
경우의 수를 계산합니다 — $$N^2$$ , $$2^N$$ , $$N!$$ 중 무엇인가?
한 후보를 검증하는 비용을 곱합니다. 이 곱이 약 $$10^8$$ 이하면 통과.
생성 도구를 고릅니다 — 쌍이면 이중 루프, 부분집합이면 비트마스크,
순서면 next_permutation/itertools, 그 외 일반 선택은 재귀.

3. 자주 하는 실수

검증 비용을 곱하지 않음. $2^{20} \approx 10^6$ 이라 안심했는데 후보마다
$$O(N^2)$$ 검사가 붙으면 $10^{10}$ 이 됩니다. 검사를 전처리로 줄이거나
후보 생성 중에 증분으로 갱신하세요.

// 나쁨: 부분집합마다 합을 처음부터 다시 계산 O(2^N * N)
// 좋음: 재귀로 만들며 합을 인자로 넘긴다 → 후보당 O(1)
void rec(int i, long long sum) {
    if (i == n) { best = max(best, f(sum)); return; }
    rec(i + 1, sum);          // i번 제외
    rec(i + 1, sum + a[i]);   // i번 포함
}

경계 후보 누락. "아무것도 안 고르는 경우", "전부 고르는 경우"가 답이 될
수 있는지 문제를 다시 읽으세요. 빈 부분집합을 빼고 도는 코드가 흔한 오답입니다.
첫 답에서 멈춤. "조건을 만족하는 것이 존재하는가"는 찾는 즉시 끝내도 되지만,
"최댓값"은 끝까지 돌아야 합니다. break를 넣을지 말지 문제 유형으로 결정하세요.
검증기 미사용. 더 빠른 풀이를 시도하다 막히면, 작은 입력에서 완전 탐색과
답을 대조하는 습관이 디버깅 시간을 크게 줄입니다.

4. 연습 방법

이 페이지 오른쪽의 추천 문제 목록은 쉬운 것부터 어려운 것 순으로 정렬되어
있습니다. 위에서부터 차례로, 풀기 전에 반드시 경우의 수를 먼저 종이에 계산
하고 시작하세요.

1~2번째 문제: 이중 루프·삼중 루프로 충분한 문제로 감을 잡습니다.
그다음: 비트마스크나 순열 생성이 필요한 문제로 넘어갑니다.

3문제 이상 풀어 이 알고리즘을 클리어하면 레이팅의 CLASS 보너스에
반영됩니다. 완전 탐색은 모든 탐색 알고리즘의 기초이니 여기서 확실히 다지세요.

후보의 모양	경우의 수	예시
$\(N\)$ 개 중 하나 고르기	$\(N\)$	최댓값 찾기
두 개 고르기(순서 무관)	$\binom{N}{2} \approx \frac{N^2}{2}$	모든 쌍
각 칸을 켜고 끄기	$\(2^N\)$	부분집합
순서까지 정하기	$\(N!\)$	순열