Brute Force Search(완전 탐색)

Brute Force Search

단순하게 컴퓨터의 계산 능력을 이용하여 모든 경우의 수를 구하여 문제를 해결하는 방법이다.

즉, 완전! 모든 경우를 탐색하는 것이다.

 

즉, 다른 하나의 특정 알고리즘이라고 하기보다는 하나의 탐색 기법(방법)으로  이해하면 된다. 알고리즘 보다는 좀 더 넓은 분류로 볼 수 있는것으로 다음 알고리즘 등이 있다.

 

1. 단순 완전 탐색 : 반복문과 조건문을 통해 처음부터 끝까지 탐색
2. 비트마스크 : 이진수 표현을 이용
3. 재귀
4. 순열
5. 백트래킹
6. BFS / DFS

문제를 해결함에 있어서 각 알고리즘에 특성에 맞게 선택하여 문제를 해결하면 된다.

완전 탐색의 특징

일반적으로 완전 탐색을 실전에서 사용하는 경우는 많겠지만 대표적으로 알고리즘 문제를 풀 때 완전탐색을 경험하는 경우가 많을 것이다. 물론 그외 실무에서도 종종 확인할 수 있겠지만, 문제에서 완전탐색의 한계가 실무에서도 적용되기에 완전탐색의 기법을 선택하는데 여러 문제가 있을 수 있다.

 

하지만, 시간 공간적 자원의 보장이 모두 충독할 경우 모든 경우를 확인하기에 매우 확실한 정확도가 보장된다는 점에서 정확도가 중요한 작업에서는 해당 기법을 사용 할 수 있다.

데이터의 크기가 작다

일단 데이터의 크기가 작아야한다. 이유는 시간적 이슈 때문이다.

완전탐색을 하기에는 시간적 조건이 문제가 되는 경우들이 있다 그렇기 때문에 일반적으로 데이터의 크기가 작을때, 완전탐색을 하게 된다.

답의 범위가 작고, 임의의 답을 선택시 문제 조건을 만족하는지 확인(역추적)할 수 있다.

데이터 크기가 일반적으로 작다보니 답의 범위가 적게 나온다. 하지만, 종종 데이터의 범위로 나오는 답의 범위는 매우 늘어날 수 있지만 조건에 따라 답의 조건을 제한할 수 있다.

 

그 경우 반대로 답을 조건에 만족하느냐를 기준으로 탐색을 진행할 수 있다.

 

예를들어 주어진 데이터는 작지만 데이터의 조합이 매우 많으나 문제에서 요구하는 조건에 의해 정답의 범위가 작게 설정될 때,

반대로 정답이 될수있는 범위내에서 조건을 만족하는 답을 찾는 것이다.

여러문제 조건중 조건 하나를 우선 고정시키면 풀이가 간단해진다.

2번과 달리 조건을 고정 시켜버린다.

Problem - 1400B - Codeforces

아무래도 조건이 많아지면 많아질수록 완전탐색하는 데에 있어서 어려움이 발생한다.

이유는 조건에 따라 가지수가 바뀌기 때문이다. 이런경우 가능한 경우에 조건을 고정해버릴 수 있다.

 

우선 하나의 조건을 고정하여 문제를 해결한 후 좀더 범위를 좁게한 후에 문제를 해결하는 것이다.

 

결론

위에서 이런저런 가능성을 나열하긴 했지만 brute force는 결국 주어진 조건에 만족하는 범위를 모두 탐색하여 알맞는 답을 찾는 문제가 될것이다.

 

경우에 따라 단순 반복을 통해 문제를 해결하는 것이 효율 적일 수 도있을 것이고, 재귀를 이용하여 탐색하는 것이 효율적일 수 있을 것이다.

 

혹은 그래프를 탐색하게 된다면 BFS/DFS를 이용하여 탐색하게 될 것이다. 이렇듯 주어진 조건에 맞춰 완전 탐색하는 것이 Brute Force Search의 기본 골자가 되는 해결기법이고 그안에서 효율적인 알고리즘들을 선택하여 풀어가면 될 것이다.

---

1. rebro.kr/59

완전 탐색 (Brute-Force Search / Exhaustive Search) 알고리즘