Brute-Force
브루트 포스는 모든 경우를 전부 시도해 보는 접근법을 말합니다. 만약 경우의 수가 유한하다면 항상 브루트 포스로 답을 찾을 수 있음을 보장할 수 있습니다. 일반적으로 구현이 매우 간단하고 직관적이기 때문에 가장 먼저 떠올리는 풀이법이기도 합니다. 하지만 경우의 수가 너무 많아지면 제한 시간 내에 답을 찾지 못할 수 있습니다. 따라서 브루트 포스를 사용할 때는 경우의 수가 얼마나 되는지, 시간복잡도가 얼마인지 잘 계산해 보는 것이 중요합니다. 브루트 포스로도 충분히 동작할 것 같다면 굳이 더 복잡한 알고리즘을 사용할 필요가 없고, 더 빠른 알고리즘이 필요하다면 어떻게 시간을 줄여야 할 지 방향을 잡을 수 있기 때문에 좋은 출발점이 됩니다.
실무에서라면 최대한 효율적인 알고리즘을 사용하는 것이 좋지만, 대회나 코딩 테스트에서는 빠르게 문제를 푸는 것도 중요하기 때문에 간단하게 풀 수 있다면 간단하게 푸는 것도 좋은 방법입니다.
브루트 포스는 반복을 통해서 모든 경우를 탐색하는 방식으로 구현합니다. 반복문을 통해 구현할 수도 있고 재귀를 통해 구현할 수도 있습니다. 문제로 살펴보도록 하겠습니다.
2798번: 블랙잭
2798번: 블랙잭입니다. \( N \)개의 카드 중 3개를 골라 합이 최대한 \( M \)에 가깝게 만드는 것이 목표입니다. 마땅히 모든 경우의 수를 탐색해 보는 것 말고는 적당한 방법이 떠오르지 않습니다. 3개를 모두 고르는 시간복잡도를 계산해 봅시다. 이 문제에서 \( 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;
}
브루트 포스는 모든 경우를 탐색하는 것이긴 하지만 중복되는 방문이나 불필요한 방문을 최대로 줄일 수 있으면 좋습니다.
참고로 파이썬에서는 꽤 유용한 라이브러리가 많아서 다음과 같은 코드도 가능합니다. 혹시 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 \)의 조합을 탐색하는 경우의 수는 \( x, y \)가 -999부터 999까지 있으므로 \( 1999 \times 1999 = 3,996,001 \)가지 경우가 있고 약 4백만번 반복이면 1초안에 충분히 동작합니다.
모든 경우를 탐색해도 문제를 풀 수 있지만 조금 더 효율적으로 문제를 풀 수 있는 방법은 없을까요? \( x \)를 임의의 수로 정했을 때 각각 \( y \)를 하나씩 구할 수 있습니다. 이렇게 구한 두 \( y \)가 같다면 해를 찾은 것입니다. 즉, \( x \)를 -999부터 999까지 하나씩 정하고, 각 \( x \)에 대해 \( y = \frac{c - a \cdot x}{b} \)와 \( y = \frac{f - d \cdot x}{e} \)를 계산해 두 값이 같은지 확인하면 됩니다. 이런 경우 1999번 반복만 하면 되니까 훨씬 빠릅니다. 대신 구현이 조금 더 복잡해집니다. 여기서는 모든 경우를 탐색하는 코드만 작성해 두었습니다. 다른 버전도 직접 작성해 보세요.
#include <bits/stdc++.h>
using namespace std;
int main() {
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;
}
}
}
}