알고리즘 기법 - 브루트 포스(전체탐색) 알고리즘

요즘 백준 문제를 꾸준히 풀고 있는데, 알고리즘 분류에 브루트 포스라고 나와 있는 걸 봤다. 브루트 포스가 뭐지?

 

우리의 코딩 선생님 지피티한테 물어보자

🔍 브루트 포스(Brute Force) 알고리즘이란?

브루트 포스(완전 탐색, Brute Force)는 모든 경우의 수를 전부 탐색하여 정답을 찾는 알고리즘이야.
쉽게 말해, 가능한 모든 방법을 시도하는 알고리즘이야.

✅ 특징

• 단순하고 직관적 → 이해하기 쉽고 구현이 간단함.
• 최적해를 보장 → 모든 경우를 다 탐색하므로 정답을 100% 찾을 수 있음.
• 시간이 오래 걸릴 수 있음 → 경우의 수가 많아지면 O(N!) 등 시간복잡도가 커질 가능성이 높음.

---

🔹 브루트 포스의 동작 방식

1. 모든 경우의 수를 고려
2. 각 경우를 하나씩 확인하면서 정답인지 체크
3. 가장 적절한 정답을 선택

---

✨ 브루트 포스 예제

🚀 1. 숫자 맞추기 (완전 탐색 예제)

숫자 42를 맞추는 문제에서 1부터 100까지 전부 탐색한다고 해보자.

python

복사편집

target = 42 for num in range(1, 101): # 1부터 100까지 모든 숫자 확인 if num == target: print("정답:", num) break

• 모든 숫자를 하나씩 확인하면서 정답을 찾음.
• 최악의 경우 100번 비교해야 함 (O(N)).

brute : 무식한 force : 힘 이라는 뜻, 한마디로 무식하게 가능한 모든 경우의 수를 탐색하면서 요구조건에 충족되는 결과만을 가져온다.

 

알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다.

 

선형 구조를 전체적으로 탐색하는 순차탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS),와 너비 우선 탐색(NFS)이 가장 기본적인 도구이다.