가능한 모든 경우의 수를 전부 탐색하여 해답을 찾는 방식
직역하자면 "무식한 힘", "완전 탐색" 정도의 의미로 해석될 수 있으며,
그 이름처럼 효율성보다는 명확하고 직관적인 해결 방법을 강조한다.
핵심 아이디어:
- 문제에서 제시된 조건을 만족하는 모든 경우를 하나하나 시도해 본다.
- 각각의 시도가 해답인지 확인하고, 해답을 찾으면 종료한다.
- 만약 모든 경우를 탐색했는데도 해답을 찾지 못하면, 해답이 없는 것으로 결론 내린다.
장점:
- 직관적이고 이해하기 쉽다. 알고리즘 설계가 비교적 간단하다.
- 해답이 반드시 존재한다면 100% 찾을 수 있다. (완전 탐색이기 때문에 누락되는 경우가 없다.)
- 복잡한 알고리즘이나 수학적 지식이 없어도 적용 가능하다.
단점:
- 효율성이 매우 낮다. 가능한 경우의 수가 많아질수록 수행 시간이 기하급수적으로 늘어날 수 있다.
- 입력 크기가 크거나 탐색 공간이 넓은 문제에는 적용하기 어렵다. (시간 초과 발생 가능성이 높다.)
언제 사용될까?
- 문제의 크기가 작거나 가능한 경우의 수가 적을 때
- 다른 효율적인 알고리즘이 떠오르지 않거나 구현하기 어려울 때
- 정확성을 최우선으로 해야 할 때
- 다른 알고리즘의 해답을 검증하는 용도로 사용될 때