브루트 포스(Brute Force)

🔎브루트 포스란?

브루트 포스는 말 그대로 무식하게 문제를 푸는 방법을 의미한다. 가능한 모든 경우의 수를 전부 시도해보는 것이다. 즉 브루트 포스의 핵심은 모든 경우의 수를 빠짐없이 탐색해 보는 것이다.

브루트포스 기법은 일반적으로 데이터의 크기가 작거나, 최적화된 알고리즘을 찾기 어렵거나, 알고리즘의 정확성을 검증할 때(정답 확인용) 사용된다.

 

 

📌브루트 포스를 구현하는 대표적인 방법과 예시 코드

경우의 수를 어떻게 만들어낼지에 대해서 여러가지 전략들이 존재

 

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;
}