알고리즘 문제를 접하다 보면 '최적화'나 '효율성'이라는 단어에 강박을 갖기 쉽습니다. 하지만 컴퓨터 과학의 역사에서 가장 오래되고, 가장 확실하며, 때로는 가장 강력한 문제 해결 방법은 바로 "무식하게 다 해보기"입니다. 이를 전문 용어로 완전 탐색, 영어로는 브루트 포스(Brute Force)라고 부릅니다. '짐승(Brute)'과 '힘(Force)'의 합성어인 이 알고리즘은 지능적인 전략보다는 컴퓨터의 압도적인 연산 속도를 믿고 밀어붙이는 방식입니다. 보안 시스템을 뚫으려는 해커부터 복잡한 퍼즐을 푸는 인공지능까지, 모든 알고리즘의 기초가 되는 완전 탐색의 세계를 탐구해 보겠습니다.
1. 완전 탐색(Brute Force)이란?
브루트 포스는 문제 해결을 위해 가능한 모든 경우의 수를 빠짐없이 탐색하여 정답을 찾아내는 기법입니다. "설마 이렇게 다 세어봐도 될까?" 싶은 방법이지만, 컴퓨터의 연산 능력이 비약적으로 발전한 현대에는 의외로 실용적인 접근법이기도 합니다.
1-1. 자물쇠와 비밀번호의 비유
가장 직관적인 예시는 4자리 비밀번호로 잠긴 자물쇠를 여는 상황입니다. 비밀번호는 `0000`부터 `9999`까지 총 10,000가지 중 하나입니다. 만약 비밀번호를 모른다면 어떻게 해야 할까요? 1. `0000`을 입력해 본다. (실패) 2. `0001`을 입력해 본다. (실패) 3. ... 계속 반복 ... 4. `9999`까지 입력해 본다. 이 과정을 거치면 시간이 얼마나 걸리든 "반드시(100%)" 자물쇠를 열 수 있습니다. 이것이 브루트 포스의 핵심 철학인 완전성(Completeness)입니다.
2. 완전 탐색의 구현 기법들
단순히 `for` 문만 돌리는 것이 전부는 아닙니다. 문제의 유형에 따라 다양한 방식으로 모든 가능성을 확인해야 합니다.
2-1. 단순 반복문 (Iteration)
가장 기본적인 형태로, `for`나 `while` 루프를 사용하여 조건에 맞는 답을 찾을 때까지 순회합니다. 배열 내의 특정 값을 찾거나, 구간의 합을 구하는 등 1차원적인 문제에 주로 사용됩니다.
2-2. 순열(Permutation)과 조합(Combination)
서로 다른 N개 중에서 R개를 선택하여 나열하는 경우의 수를 모두 확인해야 할 때 쓰입니다. 예를 들어, "여행지 5곳 중 3곳을 골라 방문하는 최단 경로"를 구한다면, 방문 순서가 중요하므로 순열을 사용해 모든 경로를 만들어보고 거리를 비교해야 합니다. 반면 "로또 번호 생성"처럼 순서가 중요하지 않다면 조합을 사용합니다.
2-3. 재귀 호출 (Recursive Call)
비트마스크(Bitmask)나 백트래킹(Backtracking)의 기초가 되는 방식입니다. 함수가 자기 자신을 호출하며 트리(Tree) 형태로 모든 가능성을 뻗어 나갑니다. 부분 집합을 구하거나, 미로 찾기 같은 문제에서 유용합니다.
3. 언제 사용해야 할까? (시간 복잡도의 한계)
브루트 포스는 정답을 보장하지만, 치명적인 단점은 실행 시간입니다. 데이터의 크기($N$)가 커질수록 연산 횟수가 기하급수적으로 늘어납니다.
3-1. 입력 제한 확인하기
코딩 테스트에서 브루트 포스를 쓸 수 있는지 판단하려면 입력 데이터의 크기를 봐야 합니다. 통상적으로 컴퓨터는 1초에 약 1억 번($10^8$)의 연산을 수행합니다.
- $O(N)$: $N$이 1억 이하일 때 사용 가능.
- $O(N^2)$: $N$이 10,000 이하일 때 사용 가능 ($10,000^2 = 1억$).
- $O(N!)$ 또는 $O(2^N)$: $N$이 20 이하일 때만 사용 가능.
만약 $N$이 10만을 넘어가는데 $O(N^2)$ 브루트 포스를 쓴다면, 시간 초과(Time Limit Exceeded)로 탈락하게 됩니다. 따라서 브루트 포스는 N이 작을 때 가장 강력한 무기입니다.
4. 브루트 포스의 의의
많은 개발자가 "완전 탐색은 무식한 방법"이라며 무시하곤 합니다. 하지만 알고리즘 설계의 정석은 "일단 완전 탐색으로 정답을 구하는 코드를 짜고, 그 후에 최적화(DP, 그리디 등)하는 것"입니다. 정확한 답을 내는 기준점(Base logic)이 되어주기 때문입니다. 또한, 암호학에서는 공격자가 브루트 포스로도 뚫을 수 없도록 만드는 것이 보안 설계의 핵심 목표이기도 합니다.
1. 완전 탐색은 가능한 모든 경우의 수를 검사하여 100% 정확한 정답을 찾아내는 기법입니다.
2. 구현이 단순하고 직관적이지만, 데이터가 많아지면 실행 시간이 너무 오래 걸립니다.
3. 문제의 입력 크기(N)가 작을 때 가장 먼저 고려해야 하며, 복잡한 알고리즘 설계의 기초가 됩니다.