왜 완전 탐색이 필요한가
알고리즘 문제를 처음 만나면 가장 먼저 해야 할 일은 "답이 될 수 있는 후보가 무엇인가?"를 찾는 것이다. 후보를 찾았다면 그다음 질문은 단순하다. "이 후보를 전부 확인하면 답을 구할 수 있는가?"
이렇게 가능한 모든 경우를 빠짐없이 검사하는 방법을 완전 탐색이라고 한다. 영어로는 브루트 포스(brute force)라고도 부른다. 말 그대로 힘으로 밀어붙이는 방식이다.
예를 들어 배열 [2, 7, 4, 1]에서 두 수를 골라 합이 8이 되는지 확인한다고 하자. 가능한 두 수의 조합을 모두 보면 된다.
2 + 7 = 92 + 4 = 62 + 1 = 37 + 4 = 117 + 1 = 84 + 1 = 5
이 중 7 + 1이 8이므로 답은 "있다"이다. 이 방법은 세련되어 보이지 않을 수 있다. 하지만 중요한 장점이 있다. 모든 후보를 확인했기 때문에 조건을 만족하는 답이 있다면 반드시 찾는다.
완전 탐색은 복잡한 알고리즘을 배우기 전 반드시 익혀야 하는 기본기다. 처음부터 빠른 방법을 떠올리려고 하면 문제 구조를 놓치기 쉽다. 먼저 느리더라도 정확한 방법을 만들면, 그다음에 어디가 느린지 보이고 개선 방향도 잡힌다.
AI 생성 이미지
완전 탐색이 느려지는 이유
완전 탐색은 정답을 보장하지만, 후보가 많아지면 시간이 급격히 늘어난다. 앞의 예시처럼 숫자 4개에서 두 수를 고르는 경우는 6번만 확인하면 된다. 하지만 숫자가 1,000개라면 가능한 쌍은 훨씬 많아진다.
두 수의 쌍을 모두 확인하는 코드는 보통 반복문이 두 겹이다.
for i from 0 to n - 1:
for j from i + 1 to n - 1:
arr[i]와 arr[j]를 확인한다첫 번째 원소는 뒤에 있는 거의 n개의 원소와 비교하고, 두 번째 원소는 그보다 조금 적게 비교한다. 실제 쌍의 개수는 n × (n - 1) / 2개이지만, 입력이 커질수록 대략 n²에 비례해서 늘어난다. 그래서 시간 복잡도는 O(n²) 로 본다.
입력이 작을 때는 괜찮다. n = 100이면 가능한 쌍은 4,950개로, 컴퓨터가 처리하기에 보통 큰 부담이 아니다. 하지만 n = 100,000이면 가능한 쌍이 약 50억 개에 가까워진다. 이 정도면 모든 쌍을 비교하는 일은 현실적으로 어렵다. 완전 탐색을 사용할 때는 항상 입력 크기를 함께 봐야 한다.
핵심은 이렇다.
후보 수가 적으면 완전 탐색은 단순하고 강력하다.
후보 수가 많으면 정답은 보장하지만 시간이 부족할 수 있다.
그래서 완전 탐색은 "첫 번째 풀이"이자 "개선의 기준점"이 된다.
조건문과 반복문으로 후보 검사하기
완전 탐색의 기본 재료는 조건문과 반복문이다.
반복문은 후보를 하나씩 꺼내는 역할을 한다. 조건문은 그 후보가 원하는 답인지 검사하는 역할을 한다.
for 후보 in 모든_후보:
if 후보가_조건을_만족한다면:
답을 갱신하거나 반환한다배열에서 짝수의 개수를 세는 문제도 아주 단순한 완전 탐색이다.
count = 0
for x in arr:
if x % 2 == 0:
count = count + 1
return count여기서는 배열의 모든 원소가 후보이고, x % 2 == 0이 검사 조건이다. 모든 원소를 한 번씩 확인하므로 시간 복잡도는 O(n)이다.
완전 탐색이라고 해서 항상 느린 것은 아니다. 후보가 배열의 원소 하나씩이라면 O(n)으로 충분히 빠를 수 있다. 느려지는 지점은 후보가 "두 개의 조합", "세 개의 조합", "모든 구간"처럼 많아질 때다.
예제 1: 두 수의 합 찾기
문제는 다음과 같다.
배열
arr와 목표값target이 주어졌을 때, 서로 다른 두 수를 골라 합이target이 되는 경우가 있는지 확인하라.
가장 직접적인 생각은 "두 수를 고르는 모든 경우를 확인하자"이다.
작은 입력으로 보자.
arr = [2, 7, 4, 1]
target = 8arr[0]인 2와 뒤의 수들을 차례대로 더해 본다. 그다음 arr[1]인 7과 뒤의 수들을 더해 본다. 이미 앞에서 확인한 쌍을 다시 볼 필요는 없다. 2 + 7을 봤다면 7 + 2는 같은 쌍이다.
의사코드는 다음과 같다.
n = length(arr)
for i from 0 to n - 1:
for j from i + 1 to n - 1:
if arr[i] + arr[j] == target:
return true
return false여기서 j를 i + 1부터 시작하는 이유가 중요하다.
같은 원소를 두 번 쓰지 않기 위해서다.
이미 확인한 쌍을 다시 확인하지 않기 위해서다.
만약 j를 0부터 시작하면 arr[i] + arr[i]처럼 같은 위치의 값을 두 번 사용하는 실수가 생길 수 있다. 또 2 + 7과 7 + 2를 둘 다 확인하게 되어 불필요한 반복이 늘어난다.
이 풀이는 시간 복잡도가 O(n²)이다. 숫자의 개수가 아주 많다면 더 빠른 방법이 필요할 수 있다. 하지만 문제를 처음 풀 때는 이 방식이 좋은 출발점이다. 정답 조건이 명확하고, 실수만 조심하면 정확하다.
예제 2: 모든 쌍 비교하기
두 원소의 관계를 확인해야 하는 문제는 많다. 예를 들어 다음과 같은 문제를 생각해 보자.
배열에서 값이 같은 두 원소의 쌍이 몇 개인지 구하라.
입력이 [1, 2, 1, 3, 2]라면 같은 값을 가진 쌍은 다음과 같다.
첫 번째
1과 세 번째1두 번째
2와 다섯 번째2
따라서 답은 2이다.
이 문제도 모든 쌍을 확인하면 된다.
count = 0
n = length(arr)
for i from 0 to n - 1:
for j from i + 1 to n - 1:
if arr[i] == arr[j]:
count = count + 1
return count여기서 반복문의 의미를 말로 풀면 이렇다.
i번째 원소를 기준으로 잡는다.그 뒤에 있는 원소
j들을 하나씩 확인한다.두 값이 같으면 쌍을 하나 찾은 것이므로
count를 1 증가시킨다.모든 기준 원소에 대해 반복한다.
이 구조는 알고리즘 문제에서 매우 자주 등장한다. "모든 두 개를 비교한다", "모든 쌍을 만든다", "서로 다른 두 항목의 관계를 본다"라는 말이 나오면 먼저 이중 반복문을 떠올릴 수 있다.
단, 이중 반복문을 무조건 피해야 하는 것은 아니다. 입력 크기가 작다면 충분히 좋은 풀이가 될 수 있다. 예를 들어 n이 100 정도라면 O(n²)은 대체로 부담이 크지 않다. 하지만 n이 100,000이라면 다른 접근을 고민해야 한다.
예제 3: 모든 부분 구간 확인하기
이번에는 구간을 확인하는 문제를 보자.
배열에서 연속된 부분 구간의 합 중 가장 큰 값을 구하라.
배열이 [3, -1, 2]라면 가능한 연속 구간은 다음과 같다.
[3]→ 합 3[3, -1]→ 합 2[3, -1, 2]→ 합 4[-1]→ 합 -1[-1, 2]→ 합 1[2]→ 합 2
가장 큰 합은 4이다.
완전 탐색으로는 시작 위치와 끝 위치를 모두 정하면 된다.
best = 아주_작은_값
n = length(arr)
for start from 0 to n - 1:
for end from start to n - 1:
sum = 0
for k from start to end:
sum = sum + arr[k]
if sum > best:
best = sum
return best이 코드는 세 겹 반복문이다.
start는 구간의 시작 위치를 고른다.end는 구간의 끝 위치를 고른다.k는 그 구간 안의 값을 더한다.
가능한 모든 연속 구간을 확인하므로 정답은 맞다. 하지만 시간 복잡도는 O(n³)이다. 입력이 조금만 커져도 느려진다.
여기서 완전 탐색의 장점이 다시 나타난다. 느리지만 정확한 코드를 먼저 만들었기 때문에, 어느 부분이 반복되는지 보인다. 위 코드에서는 같은 합을 여러 번 다시 계산한다.
예를 들어 start가 고정되어 있다면 end를 한 칸씩 늘릴 때마다 새로 추가된 값만 더하면 된다.
best = 아주_작은_값
n = length(arr)
for start from 0 to n - 1:
sum = 0
for end from start to n - 1:
sum = sum + arr[end]
if sum > best:
best = sum
return best이 코드는 여전히 모든 구간을 확인한다. 즉 완전 탐색의 성격은 유지한다. 하지만 구간 합을 매번 처음부터 다시 계산하지 않으므로 반복문이 두 겹으로 줄어든다. 시간 복잡도는 O(n²)이다.
이처럼 완전 탐색은 단순히 느린 풀이가 아니다. 정확한 기준 풀이를 만든 뒤, 중복 계산을 줄이는 방향으로 개선할 수 있는 출발점이다.
불필요한 후보 건너뛰기: 간단한 가지치기
완전 탐색은 모든 후보를 보는 방법이지만, 정말로 볼 필요가 없는 후보까지 확인할 필요는 없다. 조건상 절대 답이 될 수 없는 후보를 미리 제외하는 생각을 가지치기라고 한다.
가지치기는 나무의 가지를 자르는 모습에서 온 말이다. 탐색해야 할 경우가 나무처럼 뻗어 나갈 때, 답이 될 가능성이 없는 가지는 더 내려가지 않는다는 뜻이다.
앞에서 j를 i + 1부터 시작하게 한 것도 넓게 보면 탐색 범위를 줄인 예라고 볼 수 있다.
for i from 0 to n - 1:
for j from i + 1 to n - 1:
...이렇게 하면 같은 쌍을 두 번 확인하지 않는다. 2 + 7을 확인했다면 7 + 2는 건너뛰는 것이다. 엄밀히 말하면 이것은 가지치기라기보다 중복 후보를 만들지 않는 반복 범위 설정에 가깝지만, 핵심은 같다. 정답에 영향을 주지 않는 불필요한 검사를 줄이는 것이다.
또 다른 예를 보자.
양수로만 이루어진 배열에서 연속 구간의 합이
target이 되는 구간이 있는지 확인하라.
모든 수가 양수라면 구간을 오른쪽으로 늘릴수록 합은 커지기만 한다. 따라서 현재 합이 이미 target보다 커졌다면, 같은 시작 위치에서 끝 위치를 더 늘려도 답이 될 수 없다.
for start from 0 to n - 1:
sum = 0
for end from start to n - 1:
sum = sum + arr[end]
if sum == target:
return true
if sum > target:
break
return false여기서 break는 안쪽 반복문을 멈춘다. 현재 시작 위치에서는 더 볼 필요가 없기 때문이다.
하지만 가지치기는 조심해서 써야 한다. 위 방법은 배열의 모든 값이 양수일 때만 안전하다. 음수가 섞여 있다면 현재 합이 target보다 커졌다가 뒤에서 음수를 만나 다시 작아질 수 있다. 그 경우 break를 하면 답을 놓칠 수 있다.
가지치기의 기준은 감이 아니라 논리여야 한다.
이 후보가 정말 답이 될 수 없는가?
뒤에서 어떤 값이 나와도 결과가 바뀌지 않는가?
문제 조건이 이 판단을 보장하는가?
이 세 가지를 확인할 수 있을 때만 후보를 건너뛰어야 한다.
완전 탐색으로 먼저 풀고 개선하기
실전에서 완전 탐색은 다음 순서로 사용하면 좋다.
답이 될 수 있는 후보를 정의한다.
모든 후보를 만드는 반복문을 작성한다.
조건문으로 정답 후보인지 검사한다.
시간 복잡도를 계산한다.
입력 크기에 비해 느리면 중복 계산이나 불필요한 후보를 줄인다.
예를 들어 두 수의 합 문제를 다시 보자. 처음에는 모든 쌍을 확인하는 O(n²) 풀이를 만든다. 그다음 입력 크기가 크다면 "이미 본 값을 기억하면 더 빠르게 찾을 수 있지 않을까?" 같은 생각으로 넘어갈 수 있다. 이 아이디어는 뒤에서 해시를 배울 때 더 자세히 다룬다.
부분 구간 문제도 마찬가지다. 처음에는 모든 구간을 만들고 합을 계산한다. 그다음 같은 합을 반복해서 계산한다는 사실을 발견하면, 누적해서 더하는 방식으로 O(n³)을 O(n²)로 줄일 수 있다. 더 나아가 특정 문제에서는 더 빠른 알고리즘도 가능하다.
중요한 것은 처음부터 완벽한 풀이를 찾으려 하지 않는 것이다. 완전 탐색으로 정확한 풀이를 만들면 문제의 구조가 보인다. 어떤 후보가 많은지, 어떤 계산이 반복되는지, 어떤 조건에서 멈출 수 있는지 알 수 있다.
자주 틀리는 부분
완전 탐색에서 가장 흔한 실수는 반복 범위다. 배열의 마지막 인덱스는 n - 1이다. i + 1처럼 다음 위치를 볼 때는 범위를 넘지 않는지 확인해야 한다.
두 번째 실수는 중복 검사다. 두 수의 쌍을 볼 때 i와 j를 모두 0부터 시작하면 같은 쌍을 두 번 세거나, 같은 원소를 두 번 사용하는 문제가 생길 수 있다. 서로 다른 두 원소를 고르는 문제라면 보통 j를 i + 1부터 시작한다.
세 번째 실수는 답을 찾은 뒤에도 계속 반복하는 것이다. "존재하는가?"를 묻는 문제라면 하나를 찾는 순간 return true를 해도 된다. 반대로 "몇 개인가?"를 묻는 문제라면 모든 후보를 끝까지 확인해야 한다. 문제의 출력이 존재 여부인지, 개수인지, 최댓값인지에 따라 반복을 멈출 수 있는 시점이 달라진다.
네 번째 실수는 안전하지 않은 가지치기다. sum > target이면 멈추는 코드는 모든 수가 양수일 때만 안전하다. 조건이 보장되지 않으면 후보를 건너뛰면 안 된다.
마지막으로, 완전 탐색이 느리다는 이유만으로 무조건 나쁜 풀이로 생각하지 않아야 한다. 작은 입력에서는 가장 단순하고 실수하기 어려운 풀이가 좋은 선택일 수 있다. 알고리즘을 배울 때 완전 탐색은 문제를 이해하는 첫 번째 도구다. 가능한 모든 경우를 직접 만들어 보고, 그다음 더 빠른 방법을 찾는 습관이 실력을 만든다.
이 노트는 보도·비평·교육·연구 목적으로 작성되었습니다. 저작권 문의가 있으시면 에서 알려주세요.