[Algorithm] 완전 탐색, 브루트 포스 (Brute Force)

1. 개요

브루트 포스 (Brute Force) 는 모든 경우에 대해서 탐색하며 조건을 충족하는 경우에 한해 결과를 도출하는 방식으로, 탐색 알고리즘의 한 종류이다. 완전 탐색 알고리즘이라고도 한다.

2. 의의

브루트 포스는 모든 경우에 대한 탐색으로 결과의 100%의 정확성을 추구한다.

3. 조건

브루트 포스를 사용하기 위해서는 다음의 조건을 만족하여야 한다.

브루트 포스의 적용 조건

1. 문제 해결 방법 정의
2. 문제 수의 제한

3.1. 문제 해결 방법 정의

해결할 문제의 정확한 정의를 바탕으로 조건이 충족되는 경우를 찾아나가야 한다.

3.2. 문제 수의 제한

해결할 문제의 수가 적당해야 한다.

너무 많은 양의 문제를 해결해야 할 경우, 많은 시간을 소요하는 등의 성능 저하가 발생한다.

4. 종류

4.1. 선형 탐색

반복문 등을 사용하여 선형 구조를 전체 탐색하는 순차 탐색 (Sequential Search)이 있다.

4.2. 비선형 탐색

그래프, 트리와 같은 비선형 구조를 전체 탐색하는 너비 우선 탐색 (BFS) 과 깊이 우선 탐색 (DFS) 이 있다.

4.2.1. 너비 우선 탐색 (Breadth-First Search)

• [Algorithm] 너비 우선 탐색 (Breadth-First Search)

4.2.2. 깊이 우선 탐색 (Depth-First Search)

• [Algorithm] 깊이 우선 탐색 (Depth-First Search)

5. 적용

특정 문제 해결에 필요한 알고리즘을 찾지 못할 때, 브루트 포스의 적용을 고려해볼 수 있다.

---

관련 포스팅

• [Algorithm] 탐색 (Search) 알고리즘
• [Problem] 배낭 문제 (Knapsack Problem)
• [Baekjoon] 1065번 한수 S4

참고자료

• 알고리즘 기법[전체 탐색] - 브루트 포스(brute force)
• [알고리즘] 완전탐색 : 브루트포스 알고리즘 Brute Force Algorithm