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
'알고리즘 > 알고리즘 이론' 카테고리의 다른 글
분할 정복(Divide and Conquer) (0) | 2020.07.30 |
---|---|
백트래킹(back tracking) (0) | 2020.07.06 |
Prim 알고리즘 (0) | 2020.07.03 |
유클리드 알고리즘(최대 공약수, 최소 공배수) (0) | 2020.07.02 |
모듈로 연산(modulo operation) (3) | 2020.07.02 |