완전탐색 (Brute Force)
쉽게 풀면
네 자리 숫자로 된 자물쇠 비밀번호를 잊어버렸다고 해봅시다. 가장 확실한 방법은 0000부터 9999까지 만 개의 번호를 하나씩 다 눌러보는 것입니다. 시간은 오래 걸리지만 언젠가는 반드시 정답을 찾아낼 수 있습니다. 완전탐색(브루트포스)은 바로 이런 방식입니다. 문제를 풀 때 "이럴 것 같다"는 요령을 부리지 않고, 가능한 모든 경우를 하나씩 다 만들어보고 그중에서 조건에 맞는 답을 골라내는 것이죠. 아이디어가 단순하고 구현하기 쉬우며 반드시 정답을 찾아낸다는 확실한 장점이 있지만, 경우의 수가 조금만 늘어나도 확인해야 할 대상이 기하급수적으로 늘어나 시간이 매우 오래 걸린다는 단점이 있습니다.
왜 중요한가
완전탐색은 알고리즘 연구에서 새로운 방법의 성능을 가늠하는 출발점 역할을 합니다. 어떤 문제든 완전탐색으로 일단 정답을 구할 수 있기 때문에, 더 빠른 알고리즘이나 근사 기법이 실제로 얼마나 정확하고 효율적인지는 완전탐색 결과와 비교해야 판단할 수 있습니다. 또한 문제의 이론적 난이도(계산 복잡도)를 논할 때도 "완전탐색으로 풀면 얼마나 걸리는가"가 기준점이 되기 때문에, 최적화·조합론·기계학습의 하이퍼파라미터 탐색 등 폭넓은 연구주제와 맞닿아 있습니다.
논문에서는 이렇게 쓰입니다
이 문장은 "새로 만든 빠른 방법이 정말 최선의 답을 내는지 확인하려고, 문제가 작을 때는 모든 경우를 다 따져보는 완전탐색으로 정답을 구해서 비교 기준으로 삼았다"는 뜻입니다. 완전탐색은 느리지만 항상 정확하기 때문에 다른 알고리즘의 정답 여부를 검증하는 기준(baseline)으로 자주 쓰입니다.
기계학습 논문에서는 학습률, 배치 크기 같은 설정값의 후보들을 미리 정해두고 그 모든 조합을 하나씩 다 시도해보는 방식을 완전탐색이라고 부르기도 합니다. 이를 흔히 그리드 서치(grid search)라 하며, 조합의 수가 많아지면 계산 비용이 크게 늘어난다는 한계가 있습니다.
보안·암호학 분야에서는 가능한 모든 키 값을 하나씩 대입해보는 것을 완전탐색 공격(brute-force attack)이라고 합니다. 키 공간이 커질수록 완전탐색으로 뚫는 데 걸리는 시간이 기하급수적으로 늘어나므로, 이 소요 시간이 암호 시스템의 안전성을 가늠하는 지표로 쓰입니다.
조금 더 깊게 보면
완전탐색의 비효율은 대체로 지수 시간(exponential time) 복잡도로 표현됩니다. 문제 크기가 조금만 커져도 확인해야 할 경우의 수가 곱셈적으로 늘어나기 때문인데, 이런 특성 때문에 완전탐색은 이론적으로 문제의 난이도를 규명하는 데도 활용됩니다. 실제 연구에서는 완전탐색을 그대로 쓰기보다, 탐색 범위를 가지치기(pruning)하거나 중복 계산을 제거하는 방식으로 개선한 변형이 흔히 사용되며, 정확도와 계산 시간 사이의 절충(trade-off)을 어떻게 조절했는지가 논문에서 중요하게 다뤄지는 지점입니다.
주의할 점
완전탐색은 정답을 놓치지 않는다는 확실성이 장점이지만, 문제 크기가 커지면 현실적인 시간 안에 계산이 끝나지 않을 수 있습니다. 그래서 실제로는 같은 계산을 반복하지 않도록 저장해두는 동적계획법이나, 가능성이 없는 경로를 미리 잘라내는 백트래킹 같은 기법으로 완전탐색의 속도를 개선해서 사용하는 경우가 많습니다.