완전탐색(Brute Force)의 원리와 구현 - soo:bak

작성일 :

완전탐색이란?

4자리 자물쇠의 비밀번호를 잊어버렸다고 가정해보겠습니다. 비밀번호를 찾는 가장 확실한 방법은 0000부터 9999까지 모든 조합을 시도해보는 것입니다. 최대 10,000번의 시도만 하면 반드시 정답을 찾을 수 있습니다.


완전탐색(Brute Force) 은 이처럼 가능한 모든 경우의 수를 하나씩 검사하여 정답을 찾는 알고리즘입니다. “무식하게 풀기”라고도 불리지만, 문제 해결에서 가장 기본이 되는 접근법입니다.


완전탐색의 가장 큰 장점은 정답을 반드시 찾을 수 있다는 것입니다. 어떤 조건을 만족하는 해가 존재한다면, 모든 경우를 살펴보기 때문에 반드시 그 해를 발견하게 됩니다.

반면, 단점은 경우의 수가 많아지면 시간이 오래 걸린다는 것입니다. 4자리 비밀번호는 10,000가지이지만, 8자리가 되면 1억 가지, 12자리가 되면 1조 가지가 됩니다.


따라서 완전탐색을 적용하기 전에 경우의 수가 얼마나 되는지 먼저 계산해보는 것이 중요합니다.


완전탐색의 적용 조건

완전탐색은 다음과 같은 상황에서 적합합니다.


1. 입력 크기가 작은 경우

경우의 수가 적으면 모두 탐색해도 시간 내에 해결됩니다. 일반적으로 경우의 수가 1억(10⁸) 이하이면 완전탐색을 고려해볼 만합니다. 예를 들어, n이 20 이하인 부분집합 문제(2²⁰ ≈ 100만)나 n이 10 이하인 순열 문제(10! ≈ 360만)가 이에 해당합니다.


2. 최적화 알고리즘을 떠올리기 어려운 경우

복잡한 문제를 처음 접했을 때, 일단 완전탐색으로 정답을 구하는 코드를 작성해봅니다. 이렇게 하면 문제를 정확히 이해할 수 있고, 이후 최적화 방향을 찾기 쉬워집니다.


3. 정확한 해가 필요한 경우

근사 알고리즘과 달리, 완전탐색은 모든 경우를 살펴보기 때문에 최적해를 보장합니다.


경우의 수 계산

완전탐색을 적용하기 전에 경우의 수를 계산하는 것이 필수입니다.


주요 경우의 수 공식

유형 공식 예시 (n=10)
순열 (n개 중 n개 선택, 순서 O) n! 10! = 3,628,800
조합 (n개 중 r개 선택, 순서 X) \(\binom{n}{r}\) \(\binom{10}{5}\) = 252
부분집합 2ⁿ 2¹⁰ = 1,024
중복순열 (n개에서 r개 선택, 중복 O) nʳ 10³ = 1,000


시간 제한과 경우의 수

일반적으로 1초에 약 1억 번의 단순 연산이 가능하다고 추정합니다.

경우의 수 대략적인 값 1초 내 실행 가능 여부
10! 약 360만 ✅ 여유 있음
2²⁰ 약 100만 ✅ 여유 있음
11! 약 4000만 ⚠️ 가능하지만 빠듯함
2²⁵ 약 3300만 ⚠️ 경계선
12! 약 4억 8000만 ❌ 시간 초과 가능성 높음
2³⁰ 약 10억 ❌ 어려움


예를 들어, n = 20인 부분집합 문제는 2²⁰ ≈ 100만이므로 완전탐색이 가능합니다. 하지만 n = 30이면 2³⁰ ≈ 10억이므로 다른 방법을 찾아야 합니다.


완전탐색의 구현 방법

완전탐색을 구현하는 방법은 여러 가지가 있습니다. 문제의 특성에 따라 적절한 방법을 선택합니다.


1. 반복문을 이용한 탐색

가장 직관적인 방법으로, 중첩 반복문을 사용합니다. 탐색해야 할 변수의 개수가 고정되어 있을 때 적합합니다.


예시: 배열에서 합이 K인 두 수 찾기

배열 [2, 7, 11, 15]에서 합이 9인 두 수를 찾는다고 가정해보겠습니다.

1
2
3
4
5
6
7

[2, 7, 11, 15]에서 합이 9인 두 수 찾기

(2, 7) → 2 + 7 = 9 ✓ 정답!
(2, 11) → 2 + 11 = 13
(2, 15) → 2 + 15 = 17
(7, 11) → 7 + 11 = 18
...

모든 쌍을 하나씩 확인하면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;

// 합이 k인 두 원소의 인덱스를 반환
// 찾지 못하면 {-1, -1} 반환
pii findTwoSum(vector<int>& arr, int k) {
  int n = arr.size();

  // 모든 쌍 (i, j)에 대해 검사 (i < j)
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (arr[i] + arr[j] == k)
        return {i, j};
    }
  }

  return {-1, -1};
}

int main() {
  vector<int> arr = {2, 7, 11, 15};
  auto result = findTwoSum(arr, 9);
  cout << result.first << ", " << result.second << "\n";  // 0, 1

  return 0;
}


시간 복잡도: O(n²)

n개의 원소에서 2개를 선택하는 모든 쌍의 수는 \(\binom{n}{2} = \frac{n(n-1)}{2}\)이므로 O(n²)입니다.


장점:

  • 구현이 간단하고 직관적
  • 디버깅이 쉬움

단점:

  • 탐색 대상이 많아지면 반복문 중첩이 깊어짐
  • 탐색 변수의 개수가 가변적인 경우 사용 불가


2. 재귀를 이용한 탐색

탐색해야 할 변수의 개수가 가변적이거나, 선택의 연속으로 구성된 문제에서 재귀를 사용합니다.


예시: 부분집합 생성

집합 {1, 2, 3}의 모든 부분집합을 생성한다고 가정해보겠습니다. 각 원소에 대해 “포함한다 / 포함하지 않는다”의 두 가지 선택을 할 수 있으므로, 총 2³ = 8개의 부분집합이 존재합니다.

1
2
3
4
5
6
7
8
9

{1, 2, 3}의 부분집합:
{} (공집합)
{1}
{2}
{3}
{1, 2}
{1, 3}
{2, 3}
{1, 2, 3}

이를 재귀적으로 생성하는 과정을 트리로 나타내면 다음과 같습니다:

1
2
3
4
5
6
7

                     []
           /                    \
        [1]                      []
       /    \                  /    \
    [1,2]   [1]             [2]     []
    /  \    / \             / \     / \
[1,2,3][1,2][1,3][1]    [2,3][2] [3] []

각 레벨에서 해당 원소를 포함할지 말지 결정합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

vi arr = {1, 2, 3};
vi current;  // 현재까지 선택한 원소들

// idx번째 원소부터 선택 여부를 결정
void generateSubsets(int idx) {
  // 기저 조건: 모든 원소에 대해 결정을 마침
  if (idx == arr.size()) {
    // 현재 current가 하나의 부분집합
    cout << "{ ";
    for (int x : current)
      cout << x << " ";
    cout << "}\n";
    return;
  }

  // 선택 1: arr[idx]를 포함하지 않음
  generateSubsets(idx + 1);

  // 선택 2: arr[idx]를 포함함
  current.push_back(arr[idx]);
  generateSubsets(idx + 1);
  current.pop_back();  // 백트래킹: 상태 복원
}

int main() {
  generateSubsets(0);

  return 0;
}


시간 복잡도: O(2ⁿ)

각 원소마다 2가지 선택이 있으므로, n개 원소에 대해 2ⁿ개의 부분집합이 생성됩니다.


장점:

  • 가변적인 깊이의 탐색이 가능
  • 코드가 간결하고 구조적

단점:

  • 재귀 깊이가 깊어지면 스택 오버플로우 가능
  • 반복문보다 함수 호출 오버헤드가 있음

참고 : 백트래킹(Backtracking)의 개념과 구조적 사고 - soo:bak


3. 순열 생성

순서가 중요한 문제에서는 순열을 생성합니다. C++의 next_permutation 함수를 활용하면 쉽게 구현할 수 있습니다.


예시: 모든 순열 출력

{1, 2, 3}의 모든 순열:

1
2
3
4
5
6

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

void printAllPermutations(vi arr) {
  // 정렬 필수: next_permutation은 현재 상태에서 다음 순열을 생성
  sort(arr.begin(), arr.end());

  // 첫 번째 순열 출력
  for (int x : arr)
    cout << x << " ";
  cout << "\n";

  // 다음 순열이 존재하는 동안 반복
  while (next_permutation(arr.begin(), arr.end())) {
    for (int x : arr)
      cout << x << " ";
    cout << "\n";
  }
}

int main() {
  vi arr = {1, 2, 3};
  printAllPermutations(arr);

  return 0;
}


시간 복잡도: O(n! × n)

n!개의 순열을 생성하고, 각 순열을 출력하는 데 O(n)이 걸립니다.


참고: next_permutation은 배열을 사전순으로 정렬한 상태에서 시작해야 모든 순열을 생성합니다.


4. 비트마스크를 이용한 탐색

비트마스크는 집합을 정수로 표현하는 기법입니다. 정수의 각 비트가 해당 원소의 포함 여부를 나타냅니다.


예를 들어, 집합 {a, b, c, d}에서 {a, c}를 선택한 상태는 이진수 0101(십진수 5)로 표현합니다.

1
2
3

비트:    3  2  1  0
원소:    d  c  b  a
선택:    0  1  0  1  → {a, c} → 5


예시: 부분집합의 합이 target인 경우의 수

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

int countSubsetsWithSum(vi& arr, int target) {
  int n = arr.size();
  int count = 0;

  // 0부터 2^n - 1까지 모든 부분집합 탐색
  // 각 정수는 하나의 부분집합을 나타냄
  for (int mask = 0; mask < (1 << n); mask++) {
    int sum = 0;

    // mask의 각 비트를 확인
    for (int i = 0; i < n; i++) {
      if (mask & (1 << i))  // i번째 비트가 1이면 i번째 원소 포함
        sum += arr[i];
    }

    if (sum == target)
      count++;
  }

  return count;
}

int main() {
  vi arr = {1, 2, 3, 4, 5};
  cout << countSubsetsWithSum(arr, 7) << "\n";  // 합이 7인 부분집합 개수

  return 0;
}


시간 복잡도: O(2ⁿ × n)

2ⁿ개의 부분집합을 탐색하고, 각 부분집합의 합을 계산하는 데 O(n)이 걸립니다.


장점:

  • 반복문만으로 모든 부분집합을 탐색할 수 있음
  • 집합 연산(합집합, 교집합 등)을 비트 연산으로 빠르게 처리

단점:

  • n이 32를 초과하면 int 범위를 벗어남 (long long 사용 시 64까지)
  • 비트 연산에 익숙해져야 함

참고 : 비트마스킹의 원리와 활용 - soo:bak


완전탐색의 최적화

완전탐색이 시간 제한에 걸릴 때, 다음과 같은 최적화 기법을 적용할 수 있습니다.


1. 가지치기 (Pruning)

탐색 도중 불가능한 경우를 조기에 제외하면 탐색량을 크게 줄일 수 있습니다.


예시: 부분집합의 합이 target인 경우를 찾을 때, 현재까지의 합이 이미 target을 초과했다면 더 이상 탐색할 필요가 없습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

void search(int idx, int currentSum, int target) {
  // 가지치기 1: 이미 목표를 초과하면 중단
  if (currentSum > target)
    return;

  // 가지치기 2: 남은 모든 원소를 더해도 목표에 못 미치면 중단
  if (currentSum + remainingSum[idx] < target)
    return;

  if (idx == n) {
    if (currentSum == target)
      count++;
    return;
  }

  // 선택 또는 미선택
  search(idx + 1, currentSum + arr[idx], target);
  search(idx + 1, currentSum, target);
}


가지치기를 잘 적용하면 최악의 경우에도 탐색 시간을 크게 줄일 수 있습니다.


2. 메모이제이션

같은 상태를 여러 번 방문하는 경우, 결과를 저장하여 재사용합니다. 이 기법이 체계화된 것이 동적 계획법(DP) 입니다.

참고 : 동적 계획법(DP)의 원리와 구현 - soo:bak


3. 탐색 순서 최적화

가능성이 높은 경우를 먼저 탐색하면 정답을 빨리 찾을 수 있습니다. 예를 들어, 배낭 문제에서 가치가 높은 물건부터 탐색하면 좋은 해를 빨리 발견하여 가지치기 효과를 높일 수 있습니다.


완전탐색 vs 다른 알고리즘

알고리즘 특징 장점 단점
완전탐색 모든 경우 탐색 정답 보장 시간 복잡도 높음
그리디 매 순간 최선 선택 빠름 최적해 보장 안 됨
동적 계획법 부분 문제 저장 중복 계산 제거 메모리 사용
백트래킹 완전탐색 + 가지치기 효율적 최악의 경우 완전탐색과 동일


완전탐색은 백트래킹의 기반이 됩니다. 백트래킹은 완전탐색에 가지치기를 추가한 것으로, 유망하지 않은 경로를 조기에 포기합니다.


마무리

완전탐색은 알고리즘 문제 해결의 가장 기본적인 접근법입니다.


핵심 포인트

  • 가능한 모든 경우를 탐색하므로 정답을 반드시 찾음
  • 적용 전에 경우의 수를 먼저 계산하여 시간 내 해결 가능한지 판단
  • 반복문, 재귀, 순열, 비트마스크 등 다양한 구현 방법 존재
  • 시간이 부족하면 가지치기로 최적화


입력 크기가 작다면 완전탐색만으로 충분히 해결할 수 있습니다. 입력이 커서 시간 초과가 발생한다면, 가지치기를 적용하거나 동적 계획법, 그리디 등 다른 알고리즘을 고려합니다.


참고 : 백트래킹(Backtracking)의 개념과 구조적 사고 - soo:bak


관련 문제

이 블로그의 다른 글