정의
완전 탐색(Complete Search)이란 무엇인가
완전 탐색은 정답이 될 수 있는 모든 후보(상태)를 빠짐없이 확인하여 해를 찾는 알고리즘 패러다임입니다.
구현 관점에서 완전 탐색은 보통 후보 생성(Generate)과 후보 검증(Check)으로 분해됩니다.
완전 탐색 = Generate(후보를 전부 만들기) + Check(정답 조건 검증)
예: “분해합(생성자)”은 후보 x를 만들고 d(x)=N인지 검사하는 전형적인 완전 탐색입니다.
핵심 메시지
완전 탐색의 본질은 “무식하게 다 해본다”가 아니라,
후보 공간을 정확히 정의하고 검증 비용을 낮추며 불필요한 후보를 과감히 제거하는 설계 능력입니다.
개념 구조
완전 탐색을 “상태 공간 탐색”으로 보는 관점
완전 탐색은 결국 상태(state)의 집합을 순회하는 일입니다.
상태는 “문제에서 우리가 결정해야 하는 값들의 묶음”이며, 완전 탐색은 이 상태들을 모두 방문해 조건을 확인합니다.
상태(state)
정답을 구성하는 “선택의 결과” (예: (i, j), 순열, 부분집합, 경로 등)
전이(transition)
상태에서 다음 상태로 가는 규칙 (예: 한 칸 이동, 하나 더 선택)
목표 검사(goal test)
현재 상태가 정답인지 판정 (예: 합=K, 조건 만족)
이 관점으로 보면, “브루트포스/완전탐색/DFS/BFS/백트래킹”은 모두 상태 공간을 어떻게 순회하느냐의 차이로 정리할 수 있습니다.
설계 감각
완전 탐색의 성능은 “상한(Bound)”으로 결정된다
완전 탐색이 가능한지 판단할 때는 딱 한 줄로 정리됩니다.
총 연산량 = 후보 개수 × (후보 1개 검증 비용)
1
후보 개수를 줄인다 (Prune)
수학적 하한/상한, 불가능 조건, 정렬 후 조기 종료 등으로 “볼 필요 없는 후보”를 제거합니다.
2
검증 비용을 줄인다 (Fast Check)
누적합, 해시, 비트마스크, 캐시 등을 써서 한 후보를 O(1)~O(log n)에 가깝게 검사합니다.
3
조기 종료(Early Exit)
“최소/최대”를 찾는 문제는 정렬 또는 순회 순서를 설계해 첫 해답에서 종료합니다.
예: 분해합은 자리수 합 ≤ 9×digits라는 상한으로 탐색 시작점을 줄이고(Prune),
첫 생성자를 찾는 순간 종료(Early Exit)하여 완전 탐색을 “충분히 빠르게” 만듭니다.
대표 유형
완전 탐색 문제를 분류하는 5가지 프레임
완전 탐색은 “그냥 반복문”이 아니라, 문제의 후보 구조에 따라 패턴이 갈립니다.
1) 고정 범위 순회
1..N, 모든 (i,j), 모든 좌표 등 “정해진 범위”를 다 봅니다.
2) 조합(Combination)
n개 중 k개 선택. 순서가 중요하지 않음. 보통 DFS/재귀로 구현.
3) 순열(Permutation)
n개를 나열. 순서가 중요. visited 배열/스왑/next_permutation 사용.
4) 부분집합(Subsets)
각 원소를 “선택/비선택”하는 2^n 상태. 비트마스크가 잘 맞습니다.
5) 경로/이동(DFS/BFS)
격자/그래프에서 가능한 경로를 탐색. 상태가 커지면 방문 처리/최단거리로 제약.
구현 템플릿
Java로 쓰는 완전 탐색 3종 템플릿
1) 고정 범위 완전 탐색 (for-loop)
// 1..N 후보를 전부 검사하면서 조건을 만족하는 첫 해답(또는 최적값)을 찾는 형태
for (int x = 1; x <= N; x++) {
if (check(x)) {
// answer 업데이트 or break (조기 종료)
}
}2) 조합/부분집합 완전 탐색 (DFS/재귀)
// idx번째 원소를 선택/비선택으로 분기(부분집합 2^n)
static void dfs(int idx) {
if (idx == n) {
// 현재 선택 상태로 check()
return;
}
pick[idx] = true; // 선택
dfs(idx + 1);
pick[idx] = false; // 비선택
dfs(idx + 1);
}3) 순열 완전 탐색 (visited)
// n개 중에서 순서를 고려해 나열 (n!)
static void perm(int depth) {
if (depth == n) {
// 배열 perm[]로 check()
return;
}
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
visited[i] = true;
permArr[depth] = arr[i];
perm(depth + 1);
visited[i] = false;
}
}
실전 체크포인트
완전 탐색을 “정답으로 만드는” 7가지 습관
1
후보 공간을 먼저 쓰고 시작
“정답 후보가 무엇인지”를 한 줄로 정의하면 구현이 안정됩니다.
2
검증 함수를 분리
check(state)를 분리하면 디버깅이 쉬워지고 최적화 포인트가 보입니다.
3
상한을 숫자로 계산해보기
n=20이면 2^n≈1,048,576 같은 감각이 완전 탐색 판단을 지배합니다.
4
Pruning 조건을 문장으로 만들기
“이 상태에서 더 내려가도 절대 정답이 불가능하다”를 조건식으로 옮깁니다.
5
중복 상태 제거
정렬 + 스킵, visited, set 등을 사용해 “같은 상태를 두 번 보지 않기”.
6
조기 종료를 설계
최소/최대 문제는 “답이 나오면 끝” 구조를 만들면 체감 성능이 급상승합니다.
7
안 되면 “상태”를 바꾼다
같은 문제라도 상태를 바꾸면 후보 수가 급감합니다(좌표→차이, 값→인덱스 등).
요약
체크리스트로 마무리
CHECK
✅ 완전 탐색 = 후보 생성 + 후보 검증
✅ 성능 판단 = 후보 수 × 검증 비용
✅ 핵심 기술 = Pruning(범위/불가능 제거) + Fast Check + Early Exit
✅ 대표 패턴 = 범위 순회 / 부분집합 / 조합 / 순열 / 경로 탐색
728x90