완전탐색 — 브루트포스 (Brute Force)

관련 문제

문제	난이도	핵심
최소직사각형	Lv.1	완전탐색 기초
모의고사	Lv.1	패턴 반복 탐색
소수 찾기	Lv.2	완전탐색 + 소수 판별

---

1. 개념

브루트포스(Brute Force)는 가능한 모든 경우를 직접 시도해서 답을 찾는 방식이다.

정답을 보장하는 가장 단순한 방법이지만, 경우의 수가 많아지면 시간이 오래 걸린다는 단점이 있다.

1~100 중 소수를 찾는다면?

브루트포스: 1, 2, 3, ... 100 전부 확인
→ 느리지만 확실하다

알고리즘 문제에서 N이 작을 때 (대략 N ≤ 10,000,000) 브루트포스로 풀 수 있다.

---

2. 동작 과정

모의고사 — 수포자 3명의 패턴으로 모든 문제를 찍는 경우

수포자	패턴
1번	1, 2, 3, 4, 5 반복
2번	2, 1, 2, 3, 2, 4, 2, 5 반복
3번	3, 3, 1, 1, 2, 2, 4, 4, 5, 5 반복

문제 수만큼 반복하면서 각 수포자의 패턴과 정답을 비교한다. 가장 많이 맞힌 수포자를 반환하면 끝이다.

---

3. 핵심 사용 패턴

단순 반복

// 1부터 N까지 전부 확인
for (int i = 1; i <= n; i++) {
    if (조건) {
        // 처리
    }
}

이중 반복 (두 원소 조합)

// 모든 쌍 (i, j) 확인
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        // arr[i]와 arr[j]로 처리
    }
}

패턴 반복 (모듈러 연산)

int[] pattern = {1, 2, 3, 4, 5};
for (int i = 0; i < n; i++) {
    int pick = pattern[i % pattern.length];  // 패턴 반복
}

---

4. 핵심 포인트 2가지

시간복잡도를 먼저 계산해라

브루트포스를 쓰기 전에 경우의 수를 먼저 계산해야 한다. 대략 10^8 이상이면 시간초과가 날 가능성이 높다.

N = 100      → O(N^2) = 10,000      ✅
N = 10,000   → O(N^2) = 100,000,000 ⚠️ 위험
N = 100,000  → O(N^2) = 10^10       ❌ 시간초과

브루트포스가 안 되면 최적화를 고민해라

브루트포스로 시간초과가 나면 DP, 이분탐색, 그리디 등 더 효율적인 방법을 고민해야 한다. 브루트포스는 풀이의 출발점이지 끝이 아니다.

---

5. 시간복잡도

패턴	시간복잡도	사용 가능한 N
단순 반복	O(N)	N ≤ 100,000,000
이중 반복	O(N²)	N ≤ 10,000
삼중 반복	O(N³)	N ≤ 500

---

6. 주의사항

• 시간복잡도 먼저 계산해라. N이 크면 브루트포스는 바로 포기하고 다른 방법을 찾아라.
• 인덱스 범위를 조심해라. 이중 반복에서 j = i + 1로 시작해야 중복 없이 쌍을 만든다.
• 패턴 반복은 모듈러 연산으로 처리해라. i % pattern.length로 패턴을 순환시키면 간단하게 구현할 수 있다.
• 브루트포스로 먼저 풀고 최적화해라. 처음부터 최적화를 고민하기보다 브루트포스로 정답을 확인한 뒤 개선하는 게 실수가 적다.