🔎브루트 포스란?
브루트 포스는 말 그대로 무식하게 문제를 푸는 방법을 의미한다. 가능한 모든 경우의 수를 전부 시도해보는 것이다. 즉 브루트 포스의 핵심은 모든 경우의 수를 빠짐없이 탐색해 보는 것이다.
브루트포스 기법은 일반적으로 데이터의 크기가 작거나, 최적화된 알고리즘을 찾기 어렵거나, 알고리즘의 정확성을 검증할 때(정답 확인용) 사용된다.
📌브루트 포스를 구현하는 대표적인 방법과 예시 코드
경우의 수를 어떻게 만들어낼지에 대해서 여러가지 전략들이 존재
1️⃣ 중첩 반복문을 이용한 탐색 반복문을 중첩하여 간단한 문제의 모든 경우를 탐색하는 방식
정수 n(1 ≤ n ≤ 100)이 주어질 때, a + b^2 + c^3 = n 식을 만족하는 (a, b, c)의 개수를 구하라.
단, a, b, c는 1 이상 100 이하인 자연수로 가정하고, a, b, c가 중복될 수 있음
#include <string>
#include <vector>
#include <iostream>
using namespace std;
int main()
{
int n = 100;
int cnt = 0;
for (int a = 1; a <= 100; ++a)
{
for (int b = 1; (b * b) <= n; ++b)
{
for (int c = 1; (c * c * c) <= n; ++c)
{
if (n == a + (b * b) + (c * c * c))
{
cnt++;
}
}
}
}
cout << cnt; // 조건을 만족하는 경우의 개수: 36
return 0;
}
2️⃣ 비트마스크(Bitmask)를 이용한 부분집합 생성 비트 연산을 통해 모든 부분집합을 빠르게 생성
비트 연산을 통해 빠르고 효율적으로 부분집합을 구할 수 있다.
(1 << 요소 개수): 모든 부분집합의 개수
& 비트연산자: 같은 위치의 비트가 (1 & 1)일 때만 1을 반환하고, 나머지는 0이 된다.
12(1100) & 7(0111) 을 계산한다고 하면 0100이 되고, 10진수로 변환하면 4가 된다.
#include <string>
#include <vector>
#include <iostream>
using namespace std;
int main()
{
vector<int> arr = { 1,2,3 };
int n = arr.size();
// 부분집합의 모든 경우의 수 탐색 -> 0 ~ (1 << n)-1
// (1 << n)은 n개 만큼 1를 좌로 옮긴다(쉬프트)
// n == 3 이므로 2진수로 표현하면 1000이 되고 2의3승인 8이된다.
// 즉 (1 << n)은 부분집합의 개수를 의미한다.
for (int i = 0; i < (1 << n); i++)
{
cout << "{";
for (int j = 0; j < n; j++)
{
// i의 j번째 비트가 1인지 확인
// 만약 i가 5라면 (101):
// arr[0] = 1 출력
// arr[1] = 0 패스
// arr[2] = 1 출력
if (i & (1 << j))
{
cout << arr[j] << " ";
}
}
cout << "}\n";
}
return 0;
}
3️⃣ 순열 생성(next_permutation 사용) 모든 순열을 생성하여 탐색할 때 주로 사용한다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
vector<int> arr = { 1, 2, 3 };
do
{
for (int num : arr) cout << num << " ";
cout << '\n';
} while (next_permutation(arr.begin(), arr.end()));
/* 결과
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
*/
return 0;
}
4️⃣ 재귀 호출을 이용한 경로 탐색 DFS(깊이 우선 탐색)를 이용하여 가능한 모든 경로를 탐색
n x m 격자에서, 오른쪽 혹은 아래쪽으로만 이동할 수 있을 때, (0,0)에서 (n-1,m-1)까지 가는 모든 경우의 수
#include <vector>
#include <iostream>
using namespace std;
int DFS(int x, int y, int n, int m)
{
if (x >= n || y >= m) return 0;
if (x == n - 1 && y == m - 1) return 1;
int cnt = 0;
if (x + 1 < n) cnt += DFS(x + 1, y, n, m);
if (y + 1 < m) cnt += DFS(x, y + 1, n, m);
return cnt;
}
int main()
{
int n = 3, m = 3;
cout << DFS(0, 0, n, m);
return 0;
}
5️⃣ 백트래킹을 사용하되, 조건을 만족하지 않는 경우를 가지치기(pruning)하여 탐색 속도를 높이는 방법
배열의 요소의 합이 5가 되는 모든 경우를 출력
#include <iostream>
#include <vector>
using namespace std;
void backtrack(vector<int>& nums, vector<int>& subset, int idx, int target, int sum)
{
if (sum == target)
{
for (int num : subset) cout << num << " ";
cout << endl;
return;
}
for (int i = idx; i < nums.size(); i++)
{
if (sum + nums[i] <= target)
{
subset.push_back(nums[i]);
backtrack(nums, subset, i + 1, target, sum + nums[i]);
subset.pop_back();
}
}
}
int main()
{
vector<int> nums = { 1, 2, 3, 4 };
vector<int> subset;
int target = 5;
backtrack(nums, subset, 0, target, 0);
/* 결과
1 4
2 3
*/
return 0;
}