Brute-Force

브루트 포스는 단순무식하게 모든 경우를 전부 시도해 보는 것을 말합니다. 모든 문제 풀이의 기본이 되고 이론상 시간만 충분하다면 모든 문제를 해결할 수 있음을 보장할 수 있습니다. 물론 이론상 그렇다는 것이고 모든 경우를 탐색하면 우주의 나이보다 오랜 시간이 걸리는 문제도 있습니다. 브루트 포스를 사용하기 전에는 이전에 배운 시간복잡도를 생각해 보고 괜찮다는 판단이 들면 사용해야 합니다.

2798번: 블랙잭

브루트 포스는 말 그대로 그냥 모든 경우를 다 탐색해버리면 되기 때문에 딱히 이론이 필요하지 않습니다. 그래서 문제를 가지고 와서 예시를 보도록 하겠습니다. 2798번: 블랙잭입니다. \( N \)개의 카드 중 3개를 골라 합이 최대한 \( M \)에 가깝게 만드는 것이 목표입니다. 어떤 문제를 풀 때 풀이법이 바로 떠오르지 않는다면 모든 경우의 수를 찾는 브루트 포스부터 생각해 보는 것이 좋습니다. 시간복잡도를 계산해 보고 어떻게 최적화 하면 좋을지 생각해보면 좋습니다. 저 문제에서 \( N \)은 최대 100까지이고, 3개를 고르는 경우의 수는 \( _{100}\mathrm{C}_{3} = \text{161,700} \) 개의 경우가 있고 충분히 동작함을 알 수 있습니다. 참고로 시간복잡도는 \( O(N^3) \)이고, \( N \)이 100일 때 1,000,000이니 충분히 동작함을 확신할 수 있습니다. 이제 코드를 만들어 봅시다. 먼저 코드를 짜보는 것을 추천합니다.

#include <bits/stdc++.h>

using namespace std;
void fio() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); }

int main() {
    fio();

    int n, m;
    cin >> n >> m;
    int a[n];
    for (int i = 0; i < n; i++)
        cin >> a[i];

    int ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            for (int k = j + 1; k < n; k++)
                if (a[i] + a[j] + a[k] <= m)
                    ans = max(ans, a[i] + a[j] + a[k]);

    cout << ans;
}

어떤가요? 생각한대로 됐나요? 브루트 포스는 모든 경우를 탐색하는 것이긴 하지만 중복되는 방문이나 불필요한 방문을 최대로 줄일 수 있으면 좋습니다. 위의 예시에서 흔히 할 수 있는 실수들을 몇가지 짚고 넘어가 보겠습니다.

k > j > i로 만들지 않고 i, j, k가 모두 0부터 시작함.
1. 순서가 중요하지 않은 순열(combination)이기 때문에 (1, 2, 3)이나 (3, 2, 1)은 모두 같은 경우입니다.
2. 또 i, j, k가 서로 같아지게 되는 경우를 놓치기 쉽습니다. 중복을 허용하고 있지 않기 때문에 똑같은 카드를 여러번 쓸 수 있습니다.
ans를 바로바로 갱신하지 않고 배열에 저장하고 가장 큰 값을 출력함.
1. 가장 큰 하나만 정답이 되기 때문에 배열에 저장할 필요가 없습니다.
2. 배열에 append하는 연산은 꽤 비쌉니다.
3. 배열에서 가장 큰 값을 찾는 과정도 \( \,\,\,\,\,O(\text{len}(\text{ans})) \)의 시간복잡도를 가집니다.

참고로 파이썬에서는 꽤 유용한 라이브러리가 많아서 다음과 같은 코드도 가능합니다. 혹시 itertools에 관련해서 더 많은 정보를 얻고 싶다면 제 itertools 가이드를 참고해주세요.

from itertools import combinations

n, m = map(int, input().split())
a = list(map(int, input().split()))

ans = 0
for comb in combinations(a, 3):
    s = sum(comb)
    if s <= m:
        ans = max(ans, s)

print(ans)

19532번: 수학은 비대면강의입니다

19532번: 수학은 비대면강의입니다. 먼저 혼자 풀어보는 것을 추천합니다.

2변수 1차 연립방정식의 해를 찾는 문제인데 \( [-999, 999] \)범위에 유일한 정수해가 있음이 보장되어 있습니다. 덕분에 해가 없거나 너무 크거나 작은 경우를 신경쓰지 않아도 됩니다. 이제 앞 문제에서 해봤던 대로 모든 경우를 탐색하는 경우부터 생각해 봅시다. x, y가 -999부터 999까지 있으므로 \( 1999 \times 1999 = 3,996,001 \)가지 경우가 있고 약 4백만번 반복이면 1초안에 충분히 동작합니다. 이미 문제를 풀 수 있지만 조금 더 효율적으로 문제를 풀 수 있는 방법은 없을까요? x가 정해지면 자동으로 y도 정해지게 됩니다. 식이 2개니까 y도 2개가 나옵니다. 여기서 두 y가 서로 같은 정수이면 그때가 해가 됨을 알 수 있습니다. 이런 경우 1999번 반복만 하면 되니까 훨씬 빠릅니다. 대신 구현이 조금 더 복잡해집니다. 여기서는 첫번째 방법으로 하고 다른 방법은 과제로 맡기겠습니다.

#include <bits/stdc++.h>

using namespace std;
void fio() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); }

int main() {
    fio();

    int a, b, c, d, e, f;
    cin >> a >> b >> c >> d >> e >> f;

    for (int x = -999; x <= 999; x++) {
        for (int y = -999; y <= 999; y++) {
            if (a * x + b * y == c && d * x + e * y == f) {
                cout << x << ' ' << y;
                return 0;
            }
        }
    }
}

이 문제는 간단해서 특별한 코멘트는 필요 없을 것 같습니다. 조건이 만족되자마자 return, exit을 통해 바로 종료해 주었습니다. 없어도 시간 초과를 받지는 않겠지만 불필요한 반복을 최대한 줄이는 연습을 해두면 나중에 도움이 됩니다.

지금은 초반이니만큼 단순한 반복을 통해 모든 경우를 탐색하는 브루트 포스를 알아보았습니다. 브루트 포스는 모든 문제 풀이의 기반이 됩니다. 위에서는 다중 반복문을 통한 탐색만을 살펴보았지만 많은 경우 재귀를 통해 탐색을 진행하기도 합니다. 또, 브루트 포스를 기반으로 불필요한 반복을 최대한 줄여 최적화 해야 하는 고난도 문제도 있으니 연습해 보면 좋겠습니다.

Brute-Force

Brute-Force

2798번: 블랙잭

19532번: 수학은 비대면강의입니다

연습문제