[AI][용어] 완전 탐색(Exhaustive Search)
- IT/AI_용어
- 2026. 2. 5.
모든 걸 다 보면 답은 나오지만, 현실은 그렇지 않다.
1. 완전 탐색이란 무엇인가?
완전 탐색은 쉽게 말해 문제를 풀기 위해 가능한 모든 경우를 하나도 빠짐없이 확인하는 방법입니다.
이는 아주 단순한 생각에서 출발합니다.
답인지 아닌지 모든 경우의 수를 하나하나 전부 다 확인해 보면 당연히 답은 나온다.라는 것이죠.
비밀번호 4자리를 잊어버렸을때 찾는 가장 확실한 방법은 0000부터 9999까지 누르는 것을 생각해 보면 쉽게 알 수 있습니다.
그래서 완전 탐색은 가장 직관적이고, 가장 이해하기 쉬우며 논리적으로도 가장 깔끔한 방법입니다.
2. 완전 탐색은 왜 기준이 되는가?
완전 탐색은 좀 더 효율적인 것을 찾고 있는 일반적인 사람들에게 무식한 방법처럼 보입니다.
하지만 의외로 알고리즘 세계에서는 이 방법이 기준이 됩니다.
이유는 단순합니다.
완전 탐색은 가능한 모든 경우를 전부 확인하기 때문에 정답이 있다면 반드시 찾아냅니다. 따라서 이 문제에 답이 있는지 없는지도 확인 가능합니다.
거기에다가 구현도 쉬워서 문제 구조를 처음 이해하기도 적합합니다.
그래서 어떤 문제를 만나면, 알고리즘에서는 보통 완전 탐색으로라도 풀 수 있을까? 확인 한 다음 얼마나 더 효율적으로 풀 수 있을까라는 다음 단계로 넘어갑니다
3. 완전 탐색을 언제 쓰면 좋을까?
모든 것을 확인해보는 완전 탐색이 별로라고 생각할 수도 있겠지만 항상 나쁜 선택은 아닙니다.
오히려 입력 크기가 작거나, 경우의 수가 제한적인 상황, 정답의 정확성이 매우 중요한 상황에서는 효율적인 선택입니다.
예를 들어, 간단한 퍼즐 문제나 소규모 조합 문제나 새로운 알고리즘을 검증하기 위한 기준 모델 같은 경우에서 효과적입니다.
4. 현실에서 쓰기 어려운 이유: 눈덩이처럼 불어나는 경우의 수
하지만 문제가 데이터가 조금만 커지기 시작해도 발생합니다. 이를 흔히 상태 공간 폭발이라고 부르는데 이름처럼 경우의 수가 폭발해 버립니다.
미로 찾기에서 갈림길이 나올 때마다 선택지가 2배씩 늘어난다고 생각해 봅시다. 처음엔 2개, 그다음은 4개, 8개... 어느 순간 우리가 감당할 수 없는 숫자가 됩니다.
5. 우주의 원자보다 많아지는 숫자?
체스를 예로 들어볼까요? 체스의 모든 경우의 수는 10의 120승 정도입니다. 감이 잘 안 오실 겁니다.관측 가능한 우주 전체에 있는 원자의 개수가 10의 80승 정도라고 합니다.
우주의 모든 원자보다 체스 한 판의 경우의 수가 압도적으로 많은 셈입니다.
왜 이렇게 많을까요?
체스에서 먼저 백이 둘 수 있는 경우의 수는 20가지 입니다.20가지입니다. 첫 수를 응수하는 흑이 둘 수 있는 수도 당연히 20가지입니다. 따라서 20X20 단 1수 만에 400가지의 경우의 수가 발생합니다. 3수 후에는 무려 900만 가지의 상황이 가능해집니다.
초당 10억 개의 수를 계산할 수 있는 컴퓨터가 있다 하더라도, 10의 120승개의 경로를 모두 확인하려면 우주의 나이보다 훨씬 긴 시간이 필요합니다.
심지어 바둑의 경우에는 완전 탐색으로 할 경우 10의 360승까지 가기도 합니다.
즉 이론적으로는 답을 찾을 수 있지만 현실적으로는 불가능합니다.
6. 그럼 완전 탐색은 필요가 없을까?
완전 탐색은 모든 탐색 전략의 출발점이기 때문에 꼭 필요합니다.
"전부 다 뒤져보는 건 너무 오래 걸리니까, 이번엔 좀 영리하게 여기만 찾아볼까?" 하는 식의 고급 기법(그리디, DP 등)들은 모두 완전 탐색에서 '비효율'을 걷어내며 탄생했습니다.
기초를 알아야 응용도 할 수 있는 법입니다!
'IT > AI_용어' 카테고리의 다른 글
| [ML][용어] GELU 함수 (0) | 2025.10.10 |
|---|---|
| [ML][용어] tanh 함수(하이퍼볼릭 탄젠트 함수) (0) | 2025.10.10 |
| [ML][용어] One-Hot Encoding (원-핫 인코딩) (0) | 2024.10.25 |
| [ML][용어] Gradient Boosting Machine (GBM) (4) | 2024.10.22 |
| [ML][용어] ReLU 함수 (2) | 2024.10.15 |