브루트 포스(brute force)

Goal

• brute force에 대해서 설명할 수 있다.

---

브루트 포스(brute force)란?

완전 탐색(exhaustive search) 알고리즘 기법으로,

가능한 모든 경우의 수를 탐색하면서 문제 요구 조건을 만족 시키는지 확인하는 방법이다.

 

*brute : 무식한, *force : 힘

즉, 무식하게 모든 경우에 대해 확인해 나가는 방법이다.

이 알고리즘은 자원이 충분하다면 100% 문제 해결이 가능한 알고리즘이다.

하지만 시간적 제한과 같이 자원의 제약이 있을 경우 적합하지 않을 수 있다. 

 

완전 탐색 방법

선형 구조 : 순차 탐색

비선형 구조 : 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

 

*BFS, DFS에서 search는 일반적으로 생각하는 특정 값을 찾기 위한 탐색이 아니라, 순회(traversal)의 의미로 사용된다.

 

탐색 속도 향상 방법

후보 해(해가 될 가능성이 있는 모든 조합)에 대한 공간을 줄임으로써 탐색 속도를 향상 시킬 수 있다.

 

완전 탐색은 탐색 비용이 크기 때문에 자원 제한이 걸려 있는 문제를 풀 때, 최대한 불필요한 후보 해를 줄여 나가는 것이 중요하다.

 

후보 해를 줄여나가는 방법 중 하나로 백트래킹(backtracking)을 사용할 수 있다.

 

완전 탐색의 예시

1) 선형 구조에서의 완전 탐색 예시

서로 다른 100개의 자연수가 있을 때 500보다 큰 자연수의 개수를 구하시오. 

 

2) 비선형 구조에서의 완전 탐색

문제 : {a,b,c,d} 집합에서 두 개의 원소로 이루어진 부분 집합을 찾아라

구현 코드

#include<cstdio>
#include<vector>

using namespace std;

vector<char> S = { 'a','b','c','d' }; // 집합

void printPicked(vector<int>& picked)
{
	for (size_t i = 0; i < picked.size(); i++)
	{
		printf("%c ", S[picked[i]]);
	}
	printf("\n");
}

// n : 전체 원소 수
// picked : 지금까지 고른 원소들의 번호
// toPick : 더 고를 원소의 수
void findCombination(int n, vector<int>& picked, int toPick)
{
	if (toPick == 0)
	{
		printPicked(picked);
		return;
	}

	// 고를 수 있는 가장 작은 번호
	int smallest = picked.empty() ? 0 : picked.back() + 1;

	for (int next = smallest; next < n; next++)
	{
		picked.push_back(next);
		findCombination(n, picked, toPick - 1);
		picked.pop_back();
	}
}

int main()
{
	vector<int> picked;
	findCombination(4, picked, 2);

    return 0;
}

 

References

https://hcr3066.tistory.com/26?category=1055760

https://en.wikipedia.org/wiki/Brute-force_search#Implementing_the_brute-force_search