알고리즘이라고 하면 뭔가 수학적이고 세련된 공식을 써서 문제를 우아하게 해결하는 장면이 떠오르시나요? 하지만 컴퓨터 과학에서 가장 기본이 되면서도 가장 강력한 문제 해결 방법은 의외로 "무식하게 다 해보기"입니다. 이를 전문 용어로 완전 탐색, 영어로는 브루트 포스(Brute Force)라고 부릅니다. 'Brute(짐승)'와 'Force(힘)'의 합성어로, 머리를 쓰는 대신 압도적인 계산 능력으로 밀어붙인다는 뜻입니다. "비효율적인 거 아니야?"라고 생각할 수 있지만, 컴퓨터의 연산 속도를 믿고 정답을 100% 보장하는 가장 확실한 방법이기도 합니다.
1. 브루트 포스(Brute Force)란?
브루트 포스는 발생할 수 있는 모든 경우의 수를 하나도 빠짐없이 전부 확인하여 정답을 찾는 기법입니다. 가장 쉬운 예로 4자리 비밀번호로 잠긴 자물쇠를 푼다고 생각해 봅시다. - 0000부터 9999까지 총 10,000가지의 번호를 일일이 다 돌려본다면 언젠가는 반드시 열리겠죠? 이것이 브루트 포스입니다. 운이 좋으면 0001에서 열릴 것이고, 운이 나쁘면 9999에서 열리겠지만, "절대로 못 여는 경우는 없다"는 것이 핵심입니다.
2. 완전 탐색의 종류와 구현 방법
단순히 `for` 문만 돌리는 것이 완전 탐색의 전부는 아닙니다. 문제의 유형에 따라 다양한 방식으로 모든 경우를 쥐 잡듯이 뒤져야 합니다.
2-1. 단순 반복문 (Iteration)
가장 기본적인 형태입니다. for 루프나 while 루프를 사용하여 문제에서 요구하는 조건에 맞는 값을 찾을 때까지 순회합니다.
// 예: 배열에서 합이 100이 되는 두 수 찾기
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (arr[i] + arr[j] === 100) return [i, j];
}
}
2-2. 순열(Permutation)과 조합(Combination)
"카드 3장을 뽑아서 만들 수 있는 숫자 중 소수는?" 같은 문제처럼 순서가 중요하거나(순열), 순서가 중요하지 않은(조합) 모든 경우의 수를 나열해야 할 때 사용됩니다. 보통 재귀 함수를 이용해 구현합니다.
2-3. 재귀 호출 (Recursive Call)
부분 집합을 구하거나, 각 단계에서 선택지가 갈라지는 경우(예: 암호 만들기) 재귀를 통해 트리 형태로 모든 가능성을 뻗어 나가며 탐색합니다.
3. 완전 탐색은 언제 사용해야 할까?
브루트 포스는 만능키지만, 치명적인 단점은 속도입니다. 입력 데이터(N)가 커질수록 계산 횟수가 기하급수적으로 늘어납니다.
3-1. 사용 가능한 조건 (데이터의 크기)
알고리즘 문제를 풀 때 입력 제한을 먼저 확인해야 합니다. - 일반적으로 컴퓨터는 1초에 약 1억 번의 연산을 수행한다고 가정합니다. - 시간 복잡도가 $O(N^2)$이라면, N이 10,000일 때 1억 번($10,000^2$)이 되어 1초가 걸립니다. - 만약 N이 100,000이라면? $O(N^2)$ 브루트 포스로는 절대 풀 수 없습니다(시간 초과). - 따라서 완전 탐색은 N이 작을 때(보통 1,000 이하, 혹은 경우의 수가 수백만 단위일 때)만 사용해야 합니다.
4. 브루트 포스의 의의
많은 개발자가 "완전 탐색은 하수나 쓰는 방법"이라고 착각하지만, 실제로는 그렇지 않습니다. 1. 정확도 100%: 놓치는 케이스 없이 무조건 정답을 찾습니다. 2. 최적화의 기준: 일단 완전 탐색으로 정답을 구하는 코드를 짜고, 그 후에 시간을 줄이는 방향(DP, 그리디 등)으로 개선하는 것이 알고리즘 문제 해결의 정석입니다. 3. 암호학의 적: 보안 시스템을 설계할 때는 공격자가 브루트 포스 공격을 해도 뚫는 데 수백 년이 걸리도록 경우의 수를 늘리는 것이 목표입니다.
1. 완전 탐색(Brute Force)은 가능한 모든 경우의 수를 전부 검사하여 정답을 찾는 방법입니다.
2. 구현이 단순하고 정답을 반드시 도출하지만, 데이터가 많으면 시간이 너무 오래 걸립니다.
3. 문제의 입력 크기(N)가 작을 때 가장 먼저 고려해야 하는 강력한 해결책입니다.