[완전탐색] 알고리즘 - 완전탐색(Brute Force)

완전 탐색 (Brute Force)

가능한 모든 경우의 수를 탐색하면서 요구 조건에 충족되는 결과를 가져오는 알고리즘 이다.

해가 존재한다는 가정을 세우고 완전 탐색하기 때문에 무조건 정답을 찾을 수 있다.

복잡한 알고리즘을 생각하지 않고 모든 경우를 단순히 살펴본다고 볼 수 있다.

완전 탐색 알고리즘을 풀 때는 탐색해야할 전체 데이터 개수가 100만개 이하일 때 완전 탐색을 사용해야한다.

 

완전 탐색 종류

1. 선형 구조를 전체 탐색하는 순차 탐색

2. 비선형 구조를 전체 탐색하는 DFS(깊이 우선 탐색), BFS(너비 우선 탐색)

 

 

사용 조건

1. 문제에 대한 해결책이 잘 정의 되어 있어야 한다.

- 해결책이 정의되어 있어야 브루트 포스를 사용한 해결책이 올바른 방법인지 확인할 수 있다.

 

2. 문제를 해결할 수 있는 풀이의 수가 제한되어 있어야한다.

- 모든 경우의 수를 탐색해야 하므로 고려해야할 수가 무한하거나 너무 많으면 효율적이지 않다.

 

 

구현 기법

1. 반복문 사용

• 단순 Brute-Force로 for문과 if문 등으로 모든 case를 설정하여 답을 찾아내는 방식이다. 

2. 재귀 사용

• 재귀 함수를 통해 문제를 만족하는 경우들을 만들어나가는 방식이다. 
• 경우의 수가 각 원소가 포함되거나 포함되지 않는 두가지 선택지를 가질 때 사용된다.

3. 비트 마스크

• 2진수 (비트)를 사용하는 방식이다.
• 경우의 수가 각 원소가 포함되거나 포함되지 않는 두가지 선택지를 가질 때 사용된다.

4. 순열

• 완전 탐색의 대표적인 유형이다. 
• 순열에 원소를 하나씩 채워가는 방식이다. 재귀함수를 사용하여 구현할 수 있다.

5. BFS/DFS

• 너비 우선 탐색, 깊이 우선 탐색을 완전탐색과 결합해 사용할 수 있다. 
• 주로 길찾기 문제에 많이 사용된다.

 

 

장점

알고리즘 설계와 구현이 쉽다.

 

단점 

알고리즘 실행 시간이 오래걸린다. (높은 시간 복잡도)

메모리 효율성이 떨어진다.