1. 완전탐색
모든 경우의 수를 탐색하는 알고리즘으로,
순열or조합or기타 다양한 경우의 수를의사결정트리로 나타내고반복문orDFSorBFS로 완전 탐색하는 유형이다.
(1) 사용하는 경우
전체 경우의 수를 다 검사해봐도 연산량 고려했을때 시간 제한을 통과하는 경우
(2) 의사결정트리
문제 해결을 위한 모든 선택지를 트리 형태로 표현한 것
문제를 완전 탐색으로 접근할때 -> 문제를 의사결정트리로 만드는게 매우 매우 매우 중요하다.
(3) 구현 방법
✍ 반복문
for문 또는 반복문을 이용해 주어진 범위를 모두 검사하는 방법
- 반복문으로 완전 탐색 구현이 가능하면, 재귀말고 반복문을 쓰는것이 좋다 (반복문으로 구현하는 방식의 코스트가 더 적다)
#include <iostream>
using namespace std;
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = 5;
for(int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
}✍ DFS
DFS를 이용해 주어진 범위를 모두 검사히는 방법
- 반복문보다 코스트가 크다 (시간이 오래 걸린다)
- 재귀로 구현하는 경우
- 반복문으로 구현하기 힘든 경우
- 매개변수가 수정되며 반복되는 경우
- nC1, nC2, nC3 .. 등 이런 경우의 수를 다 생각해야 하는 경우
✍ A. 조합의 의사결정트리를 DFS로 완전 탐색 - 누적
vector<int> v={1,2,3,54,8,34,54,70,46};
int sum=0;
int go(int idx, int sum) {
if(idx==n) {
//검사하거나 등등해서 조건에 부합하면 return 1하고 아니면 return0 하는식으로 누적(카운트)
}
return go(idx+1, sum + v[idx]) + go(idx+1, sum); //sum에 고른 수들을 누적
}- v: 입력받은 숫자들이 저장되어있는 벡터
- idx: 포함 or 불포함 여부를 결정할 인덱스
- idx가 n이되면 조합 1개가 완성된것이므로 적절한 로직을 수행한 후 결과에따라 return한다.
✍ B. 조합의 의사결정트리를 DFS로 완전 탐색 - 갱신
vector<int> v;
int sum=0;
void go(int idx, int sum) {
if(idx==n) {
//값 비교해서 최댓값 갱신하거나...등등의 로직
}
go(idx+1, sum + v[idx]);
go(idx+1, sum);
}✍ C. 그래프를 DFS로 완전 탐색
그래프를 완전탐색하는 경우에는 원상복구 기능이 들어가야한다.
이전 탐색이 다음 탐색에 영향을 주면 안되기때문이다.
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[10]; // 인접 리스트
int visited[10];
vector<int> path;
void go(int here) {
// 현재 경로 출력
if(path.size() == n) {
for (int x : path) cout << x << " ";
cout << "\n";
return;
}
for (int there : adj[here]) {
if (visited[there]) continue;
visited[there] = 1;
path.push_back(there);
go(there);
visited[there] = 0; // 🔥 백트래킹
path.pop_back(); // 🔥 백트래킹
}
}
int main() {
// 간단한 그래프
adj[1] = {2, 3};
adj[2] = {4};
adj[3] = {4};
adj[4] = {};
// 시작 노드 1
visited[1] = 1;
path.push_back(1);
go(1);
}위의 코드를 보자.
노드에 방문할때마다 visited[]에 방문 표시 및 path 벡터에 원소로 노드를 추가해준다.
이후 go()를 통해 한번 더 재귀를 수행해서 위의 과정을 반복하다가,,
return이 되면 가장 최근에 방문한 노드를 visited[]에 미방문 처리하고, path 벡터에서도 삭제해줌으로써 다음 탐색에 주는 영향을 제거하고, 독립적으로 다음 경로를 탐색할 수 있게된다.
void go(int here) {
// 현재 경로 출력
if(path.size() == n) {
for (int x : path) cout << x << " ";
cout << "\n";
return;
}
for (int there : adj[here]) {
if (visited[there]) continue;
visited[there] = 1;
path.push_back(there);
go(there);
visited[there] = 0; // 🔥 백트래킹
path.pop_back(); // 🔥 백트래킹
}
}이 go()의 코드 블럭을 외워두면 편할 것 같다.
2. 완전 탐색에 적용하는 기술 1 - 백트래킹
상태를 원상복구하며 다른 경우 탐색하는 방식
3. 완전 탐색에 적용하는 기술 2 - 프루닝(pruning, 가지치기)
현재 탐색하는 경로가 조건에 부합할 가능성이 없으면 더이상 탐색하지 않고 되돌아가는 방식
기존 완전탐색은 불필요한 부분까지 전부 탐색해버리지만, 가지치기(Pruning)을 적용하면 알고리즘의 효율성이크게 향상된다.
#include <bits/stdc++.h>
using namespace std;
int n = 4, target = 10;
int arr[4] = {2, 4, 6, 8};
int cnt = 0;
void dfs(int idx, int sum) {
// 🔥 Pruning: 이미 target 넘으면 더 볼 필요 없음
if (sum > target) return;
if (idx == n) {
if (sum == target) cnt++;
return;
}
dfs(idx + 1, sum + arr[idx]);
dfs(idx + 1, sum);
}
int main() {
dfs(0, 0);
cout << "경우의 수: " << cnt << endl;
}
위와 같이 if (sum > target) return;을 통해서 이미 합이 target을 넘으면 더이상 해당 경로의 탐색을 진행하지않고 return해버린다.
