완전 탐색 (Brute Force)

완전 탐색은 문제를 풀 때, 가능한 모든 경우를 살펴보면서 답을 찾는 방법을 말합니다.

일반적으로 가장 간단하고 쉽게 생각할 수 있는 방법이면서도, 제대로 구현했다면 절대 틀릴 수 없는 방법이기도 합니다.

 

PS에 입문하는 사람들이 문제를 풀 때 많이 하는 실수 중 하나는 입력이 작은 문제에 대해 완전 탐색 풀이를 쓸 생각을 하지 못한다는 것입니다.

 

예를 들어 \(N\)이 최대 1000이고, 완전 탐색으로 \(O(N^2)\)으로 풀 수 있는 풀이가 있다면, \(O(NlogN)\)이나 \(O(N)\)에 동작하는 더 나은 풀이에 대해 생각할 필요가 없습니다.

물론 개인적인 공부를 위해서라면 충분히 가치가 있겠지만, 만약 목표가 지금 앞에 있는 문제를 푸는 것이라면 의미가 없다는 것을 알아야 합니다.

 

대회에서는 완전탐색을 이용하는 문제가 그렇게 많이 나오지는 않습니다만, 완전 탐색은 다른 풀이들을 생각해내는 근본적인 아이디어가 됩니다.

예를 들어, 작은 경우의 문제를 완전 탐색으로 풀어본 다음 패턴을 찾아낸다거나, 완전 탐색 풀이에 자료구조를 더해 시간복잡도를 줄인다거나, 어려운 풀이를 검증할 때 완전 탐색으로 찾은 정답과 비교해서 내 코드가 맞는지 확인할 수도 있습니다.

 

서론은 여기까지 하고, 완전 탐색을 사용하여 푸는 문제들의 예를 몇 가지 살펴보도록 합시다.

 

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

2309번: 일곱 난쟁이

9개의 수가 있습니다. 이 중에서 7개의 수의 합이 100이 되는데, 이 7개를 출력해야 합니다.

 

문제를 조금만 바꿔봅시다. 9개의 모든 수의 합에서 100을 빼서 나오는 숫자를 \(x\)라고 합시다.

어떤 2개의 수의 합이 \(x\)라면, 이 2개의 수를 제외한 나머지 수들의 합이 100일 것입니다.

 

2중 반복문을 이용해 수 2개를 모두 골라본 다음, 합이 \(x\)인 경우가 있는지 찾아봅시다.

그런 수 2개를 아무거나 하나 찾았으면, 그것들만 빼고 출력하면 됩니다.

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int sum = 0; // 수들의 총 합
 
    int arr[9];
    for (int i = 0; i < 9; i++)
    {
        cin >> arr[i];
        sum += arr[i];
    }
 
    sort(arr, arr + 9); // 오름차순 정렬
 
    int x = sum - 100;
    int spy[2];
    for (int i = 0; i < 9; i++) for (int j = i + 1; j < 9; j++) // O(N^2) 완전 탐색
    {
        if (arr[i] + arr[j] == x)
        {
            spy[0] = i;
            spy[1] = j;
        }
    }
 
    for (int i = 0; i < 9; i++)
    {
        if (i == spy[0] || i == spy[1]) continue;
        cout << arr[i] << '\n';
    }
}

---

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

6603번: 로또

앞 문제는 2가지를 고르는 모든 조합을 2중 반복문으로 처리했습니다.

이번엔 6가지를 고르라고 하는데, 어떻게 해야 될까요?

어렵게 생각할 필요 없습니다. 복잡하게 할 필요 없이, 6중 반복문을 이용하면 됩니다.

 

\(k\)가 최대 13이기 때문에, 가능한 최대 경우의 수는 \(_{13}C_6 = 1716\)가지이므로, 충분히 시간안에 돌아간다는 사실도 알 수 있습니다.

 

#include <iostream>
using namespace std;
 
int k;
int s[13];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    while (true)
    {
        cin >> k;
        if (k == 0) break;
 
        for (int i = 0; i < k; i++) cin >> s[i];
        for (int a = 0; a < k; a++) for (int b = a + 1; b < k; b++)
            for (int c = b + 1; c < k; c++) for (int d = c + 1; d < k; d++)
                for (int e = d + 1; e < k; e++) for (int f = e + 1; f < k; f++)
                {
                    cout << s[a] << ' ' << s[b] << ' '
                        << s[c] << ' ' << s[d] << ' '
                        << s[e] << ' ' << s[f] << '\n';
                }
 
        cout << '\n';
    }
}

---

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

1182번: 부분수열의 합

\(N\)개의 수 중 몇 가지를 골라 합이 \(S\)가 경우를 세어야 합니다.

 

이번엔 \(N\)개의 수 중에 몇 가지를 골라야 할지 알 수 없습니다.

 

\(N\)가지의 모든 수에 대해, 각 수를 고르거나/고르지 않는 2가지를 선택한다고 합시다.

그러면 마지막 \(N\)번째 수를 선택하고 나서 지금까지 고른 수들을 다 더했을 때, \(S\)가 되는지 확인 하면 됩니다.

 

각 수에 대해 고른다/고르지 않는다 2가지의 경우가 있으니 모든 경우의 수는 \(2^N\)가지이고, \(N\)이 최대 20이므로 충분히 시간안에 돌아감을 알 수 있습니다.

 

이것을 반복문만으로 구현하는 것은 조금 무리가 있으니, 재귀함수를 이용해 구현해 봅시다.

 

#include <iostream>
using namespace std;
 
int n, s;
int arr[21];
 
int ans = 0; // 답
void DFS(int idx, int cur_sum) // 현재 arr[idx]를 보고있고, 지금까지의 합은 cur_sum이다.
{
    if (idx == n) // 기저 조건
    {
        if (cur_sum == s) ans++; // 지금까지의 합이 s면, 한 가지 경우를 찾아냈다.
        return;
    }
 
    DFS(idx + 1, cur_sum); // arr[idx]를 선택하지 않는 경우
    DFS(idx + 1, cur_sum + arr[idx]); // arr[idx]를 선택하는 경우
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> s;
    for (int i = 0; i < n; i++) cin >> arr[i];
 
    DFS(0, 0);
 
    if (s == 0) ans--; // s가 0이면 모든 원소를 전부 고르지 않는 경우도 포함된다.
    cout << ans;
}

 

비트마스킹을 이용한다면, 반복문만을 이용해 모든 조합을 만들어 낼 수 있으므로 더 간단하게 짤 수 있습니다.

 

#include <iostream>
using namespace std;
 
int n, s;
int arr[21];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> s;
    for (int i = 0; i < n; i++) cin >> arr[i];
 
    int ans = 0;
    for (int st = 1; st < (1 << n); st++) // 비트마스킹으로 모든 부분집합을 탐색한다.
    {
        int cur_sum = 0;
        for (int i = 0; i < n; i++)
        {
            if (st & (1 << i)) cur_sum += arr[i];
            // i번째 비트가 켜져있다면, i번째 원소를 고른다는 뜻이다.
        }
 
        if (cur_sum == s) ans++;
    }
 
    cout << ans;
}

 

---

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

10819번: 차이를 최대로

지금까지는 모든 조합에 대해 완전 탐색을 했다면, 이번엔 모든 순열에 대해 완전 탐색을 해야 합니다.

 

\(N\)이 최대 8이므로 \(N!\)가지의 모든 순열을 만든 다음, 문제에 나오는 식을 계산해서 그중 최대값을 찾으면 됩니다.

 

역시 재귀함수를 이용해 구현해 봅시다.

 

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
 
int n;
int a[8];
 
int ans = 0; // 답
bool isSelected[8]; // i번째 원소를 선택했는지 여부를 저장
int cur_a[8]; // 현재 만들어진 순열
 
void DFS(int idx) // 현재 cur_a[idx]를 만들고 있다.
{
    if (idx == n) // 기저 조건
    {
        int res = 0;
        for (int i = 1; i < n; i++)
            res += abs(cur_a[i] - cur_a[i - 1]);
        // 지금까지 만든 순열의 함수값을 만든다.
 
        ans = max(ans, res);
        // res가 더 크다면 ans를 갱신한다.
 
        return;
    }
 
    for (int i = 0; i < n; i++)
    {
        if (isSelected[i]) continue; // 이미 고른 수는 고르지 않는다.
 
        cur_a[idx] = a[i];
        isSelected[i] = true;
 
        DFS(idx + 1);
 
        isSelected[i] = false;
    }
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
 
    DFS(0);
 
    cout << ans;
}

 

현재 순열의 다음 순열을 반환해주는 next_permutation 함수를 이용하면, 다음과 같이 간단하게 구현할 수도 있습니다.

 

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
 
int n;
int a[8];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
 
    int ans = 0;
    sort(a, a + n); // 오름차순 정렬
 
    do
    {
        int res = 0;
        for (int i = 1; i < n; i++)
            res += abs(a[i] - a[i - 1]);
 
        ans = max(ans, res);
    } while (next_permutation(a, a + n)); // 다음 순열을 만드는 함수
 
    cout << ans;
}

 

---

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

2580번: 스도쿠

 

스도쿠를 완전 탐색으로 풀 수 있을까요?

 

다음과 같은 방식으로 완전 탐색을 한다고 생각해봅시다.

맨 위 빈 칸부터 차례로 

 

칸이 최대 81개이므로, 최대 \(9^{81} \approx 1.966 \times 10^{77}\)가지의 수를 확인해 봐야합니다.

이 풀이로는 시간 제한 1초안에 돌아가는 것은 어림도 없어 보입니다.

 

 

이번엔 퇴각 검색 (Backtracking)과 가지치기에 대해 배워봅시다.

스도쿠의 어떤 빈 칸에 어떤 수를 넣었는데 이미 모순이 생겼다고 가정해 봅시다.

그러면 이 스도쿠의 답을 계속 만들어 가는 것에 의미가 있을까요?

아닙니다. 모순이 생긴 순간 바로 탐색을 그만 두고, 다음 가능한 경우를 확인하는 것이 효율적일 것입니다.

 

이런식으로 가능한 경우를 탐색하는 도중에, 계속 탐색해봐야 답을 찾을 수 없다고 판단할 수 있다면 그대로 탐색을 중지할 수 있습니다.

이것을 가지치기라고 합니다.

가지치기를 이용해 올바른 스도쿠가 만들어질 수 없다면 이전 단계로 퇴각하여, 다시 올바른 스도쿠를 찾도록 최적화하면 완전 탐색 코드가 훨씬 더 빠른 시간에 돌아가게 됩니다.

 

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
 
int sudoku[9][9];
 
void solve(int x, int y) // x행 y열을 보고 있다.
{
    if (x > 8) // 기저 사례
    {
        // 모든 칸이 다 채워졌다는 것은, 현재 스도쿠에 모순이 없다는 뜻이다.
 
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++) cout << sudoku[i][j] << ' ';
            cout << '\n';
        }
 
        exit(0); // 프로그램 종료
    }
 
    if (sudoku[x][y] != 0) // 이미 숫자가 채워져 있으면, 다음 칸을 본다.
    {
        if (y == 8) solve(x + 1, 0);
        else solve(x, y + 1);
        return;
    }
 
    for (int n = 1; n <= 9; n++)
    {
        bool isValid = true;
 
        for (int j = 0; j < 9; j++) // 현재 행에 n이 존재하는지 확인
            if (sudoku[x][j] == n) isValid = false;
 
        for (int i = 0; i < 9; i++) // 현재 열에 n이 존재하는지 확인
            if (sudoku[i][y] == n) isValid = false;
 
        for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) // 현재 3x3 박스에 n이 존재하는지 확인
            if (sudoku[x / 3 * 3 + i][y / 3 * 3 + j] == n) isValid = false;
 
        if (!isValid) continue;
        // 현재 칸에 n을 넣었을 때 모순이 있다면, 더 진행하지 않는다. (가지치기)
 
        sudoku[x][y] = n;
        // 현재 칸에 n을 넣어본다음 다음으로 넘어간다.
 
        if (y == 8) solve(x + 1, 0);
        else solve(x, y + 1);
 
        sudoku[x][y] = 0;
        // 만약 올바른 스도쿠를 찾지 못했다면, 이전 상황으로 돌아간다.
    }
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    for (int i = 0; i < 9; i++) for (int j = 0; j < 9; j++)
        cin >> sudoku[i][j];
 
    solve(0, 0);
}

---

제 그룹의 문제집에서 연습 문제들을 관리하고 있습니다.

문제집의 문제들을 보고 싶으시다면, 가입 신청을 해 주세요.

 

https://www.acmicpc.net/group/7712

ANZ1217

가입 신청하시면 최대한 빨리 승인해드리겠습니다!