완전 탐색(Brute Force)

완전 탐색이란?

번호 자물쇠를 푸는 가장 단순한 방법이 무엇일까요? 바로 모든 경우의 수를 넣어보는 것입니다. 아주 간단한 원리지만 자릿수가 늘어날 때마다 경우의 수는 기하급수적으로 많아지기 때문에 평범한 사람의 머리로는 빠르게 풀어내지 못합니다. 하지만 컴퓨터는 가능합니다. 컴퓨터의 빠른 계산 능력을 이용하여 모든 경우의 수를 전부 탐색하는 방법, 바로 완전 탐색 입니다.

 

 

완전탐색은 답을 무조건 찾아낼 수 있지만 시간이 최고로 많이 듭니다. 시간이 많이 들면 시간 제한이 문제가 됩니다. 모든 문제는 위와 같이 시간과 메모리 제한이 주어지는데, 그렇기 때문에 완전 탐색을 하더라도 시간 제한 안에 풀 수 있는 적은 탐색 범위가 주어졌을 때 사용 가능한 알고리즘입니다.

 

 

완전 탐색의 종류

완전 탐색에는 어떤 식으로 탐색하는지에 따라 단순 중첩 for문, 재귀, DFS/BFS, 백트래킹 등이 있습니다. 나중에 자세하게 할 예정이므로 이번에는 중첩for문이나 재귀로 풀리는 문제를 중심으로 다뤄보겠습니다. 항상 그렇듯 하나의 문제에는 여러 가지 풀이가 있기 때문에 사용하기 편한 것, 딱 떠오르는 알고리즘을 사용하면 됩니다.

 

 

중첩 for문 완전 탐색

https://www.acmicpc.net/problem/2309

 

이 문제에서 입력 개수는 9개입니다. 9개면 for문을 여러 번 돌려도 2초 내로 충분히 해결 가능하기 때문에 완전 탐색을 쓸 수 있습니다.

 

문제를 요약하자면 9명 중에 7명을 뽑아서 7명의 합이 100이 되는 경우를 출력하면 됩니다. 문제에서 우리는 7명의 합이 100이니 9명의 합은 100+a라는 사실을 알 수 있습니다. 결국 9명의 합-어떤 두 명의 합이 100인 경우를 찾아 그 둘을 빼고 오름차순으로 출력하면 정답입니다.

 

#include <stdio.h>
#include <algorithm>
int height[10], sum = 0;
int main() {
    for (int i = 0; i < 9; i++) {
        scanf("%d", &height[i]);
        sum += height[i];
    }
    std::sort(height, height + 9);
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (i != j && sum - (height[i] + height[j]) == 100) {
                height[i] = 0, height[j] = 0;
 
                for (int i = 0; i < 9; i++) {
                    if (height[i]) printf("%d\n", height[i]);
                }
                return 0;
            }
        }
    }
}

 

재귀 완전 탐색

같은 문제를 재귀로 풀어 봅시다.

 

재귀함수란 함수 내에서 함수 자기 자신을 계속 호출하며 반복 계산을 하는 것을 의미합니다.

9명 중에 7명을 뽑아서 7명의 합이 100이 되는 경우를 수학적으로 다시 말하면 9명 중에 7명을 순서와 상관없이 뽑는 경우, 즉 조합 문제로 9C7이 됩니다. 9명 중에 7명을 뽑고 100이 되는 7명이라면 출력하면 됩니다.

 

 

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
int height[10], visit[10], res[10];
 
void solve() {
    int p = 0, sum = 0;
    for (int j = 0; j < 9; j++) {
        if (visit[j]) {
            sum += height[j];
            res[p++] = height[j];
        }
    }
    if (sum == 100) {
        std::sort(res, res + p);
        for (int j = 0; j < p; j++) printf("%d\n", res[j]);
        exit(0);
    }
}
 
void Combination(int start, int cnt) {
    if (cnt == 7) {
        solve();
        return;
    }
    for (int i = start; i < 9; i++) {
        if (visit[i]) continue;
        visit[i] = 1;
        Combination(i, cnt + 1);
        visit[i] = 0;
    }
}
 
int main() {
    for (int i = 0; i < 9; i++) {
        scanf("%d", &height[i]);
    }
    Combination(0, 0);
}

 

재귀를 돌릴 때는 무한 루프에 빠지지 않도록 꼭 탈출 조건을 만들어 주어야 합니다. 또, 재귀 함수가 호출이 되면 그 이후 코드는 잠시 중단되며, 호출된 재귀들의 계산이 전부 끝난 후에 순차적으로 이후 코드가 돌아간다는 점을 주의합시다.

 

 

중복for문/재귀로 풀리는 완전 탐색 문제들

https://www.acmicpc.net/problem/2309 일곱 난쟁이
https://www.acmicpc.net/problem/7568 덩치
https://www.acmicpc.net/problem/6603 로또
https://www.acmicpc.net/problem/1065 한수
https://www.acmicpc.net/problem/1107 리모컨★