완전 탐색, 백트래킹

완전 탐색 (brute force, exhausitive key search)

완전 탐색은 모든 경우의 수를 탐색하는 알고리즘입니다. (즉, 노가다)

경우의 수란? 순열 또는 조합을 의미합니다.
그래서 완전 탐색은 보통 조합/순열 + 로직(DFS/BFS) 로 이루어져 있습니다.

 

 

그럼 언제, 완전탐색을 사용해도 될까요? 아주 명확하고 간단하게 정리하면 다음과 같습니다.

시간복잡도가 1억 미만일 때!

 

즉, 대략 총 계산 횟수가 1억 미만이면 완전탐색으로 풀면 됩니다. (대부분 시간 제한이 1초이므로)

그러나 1억 이상인 경우에는? 다른 방법이 떠오르지 않으면 완전 탐색을 사용하긴 하되, 의심하긴 해야합니다.

 

 

 

완전탐색의 구현 방법 2가지 (반복문 vs 재귀함수)

만약 2가지 방법 모두로 풀 수 있다면, 무조건 반복문으로 푸는게 좋습니다. 

시간복잡도나 실행 시 차지하는 메모리 양(보통 스택)의 측면에서 재귀함수가 훨씬 뒤떨어지기 때문입니다.

 

그럼 언제 재귀로 풀어야할까요?

행위는 반복하긴 하지만, 매개변수만 수정해서 넘기면 될 것 같을 때 (or 반복문으로 구현하기가 힘들 때)

 

예를 들어, nC1, nC2, nC3 등의 경우의 수를 다 생각해야 한다면 반복문이 아니라 재귀 함수로 하는게 나을겁니다.

 

 

반복문으로 푸는 완전탐색 문제

Q) 동훈이는 1004라는 숫자를 굉장히 좋아한다. 이를 '천사의 숫자' 라고 표현한다.
이때, 1번째 천사의 숫자는 1004이고, 2번째 천사의 숫자는 11004, 3번째 천사의 숫자는 21004 이다.
입력으로 N이 주어졌을 때, N번째 천사의 수를 구하라. N은 100 이하로만 주어진다.

 

정답 코드는 아래와 같습니다.

 #include<bits/stdc++.h>
 using namespace std;
 int cnt, n;
 int main() {
     cin >> n;
     int i = 1004;
     while(true){
         string a = to_string(i);
         if(a.find("1004") != string::npos){
             cnt++;
             if(n == cnt){
                 cout << a << '\n';
                 break;
             }
         }
         i++;
    }
     return 0;
 }

 

 

 

재귀 함수로 푸는 완전탐색 문제

Q) 입력으로 숫자의 개수 N이 주어지고, 다음 N개의 줄에 숫자를 공백을 두고 입력을 받는다.
이때, 이 숫자 몇 개(1 ~ N)를 골라 더했을 때 그 합이 소수가 되는 총 경우의 수를 구하라.

 

입력:

10

24 35 38 40 49 59 60 67 83 98

 

출력: 176

 

이런 종류의 문제는 단순하게 반복문으로 풀기 어렵습니다.

문제에 대한 답안 코드는 아래와 같습니다.

#include<iostream>
#include <vector>
using namespace std;

int n, temp;
vector<int> v;

//return 값 - 소수 : 1 , 소수가 아닌 수 : 0
bool check(int n) {
	if (n <= 1) return 0; 
	if (n == 2) return 1; 
	if (n % 2 == 0) return 0;
	for (int i = 3; i * i <= n; i++) { //홀수이지만, 무언가의 제곱수면 소수가 아님
		if (n % i == 0) return 0;
	}
	return 1; //모든 과정을 통과하면 소수
}

int go(int idx, int sum) {
	if (idx == n) {
		//cout << "SUM " << sum << "\n";
		return check(sum);
	}
	//현재 보고 있는 값을 더하고 넘어가거나, 더하지 않고 넘어간걸 나눠서 계산한 뒤,
	//그 합이 소수인지 판단하는 과정
	return go(idx + 1, sum + v[idx]) + go(idx + 1, sum);
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> temp;
		v.push_back(temp);
	}
	cout << go(0, 0) << "\n";
	return 0;
}

 

 

 

---

백트래킹 (back tracking)

백트래킹 = 완전탐색 + 가지치기  라고 생각하시면 됩니다.

즉, 최대한 불필요한 탐색을 피하면서 완전 탐색을 하는 방식을 백트래킹이라고 합니다. 

 

가지치기(Pruning)

백트래킹의 핵심 기법 중 하나로, 현재 탐색하고 있는 경로가 목표 해에 도달할 가능성이 없다고 판단되면 더 이상 그 경로를 탐색하지 않고 되돌아가는(backtracking) 방법입니다.

 

바로 예시를 통해 봅시다 !

Q) N과 N개의 자연수가 주어진다. 여기서 몇 개의 숫자를 골라 합을 mod11 했을때 나오는 가장 큰 수를 구하라.

 

입력:

10

24 35 38 40 49 59 60 67 83 98

 

출력: 10

 

문제의 답안은 아래와 같습니다.

#include<iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, temp, ret, cnt;
vector<int> v;
const int mod = 11;

void go(int idx, int sum) {
	if (ret == 10) return; //가지치기의 핵심 코드! (백트래킹 적용)
	if (idx == n) {
		ret = max(ret, sum % mod);
		//cnt++; //디버깅에 필요한 값 (호출 횟수 파악해보려고)
		return;
	}
	go(idx + 1, sum + v[idx]);
	go(idx + 1, sum);
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> temp;
		v.push_back(temp);
	}
	go(0, 0);
	cout << ret << "\n";
	//cout << cnt << "\n"; //디버깅을 위한 코드
	return 0;
}

 

근데 이 코드에서 핵심은, 

if (ret == 10) return; //가지치기의 핵심 코드! (백트래킹 적용)

 

이 한 줄입니다. 이 한줄 덕분에, 실제 호출 횟수가 2^10 = 1024에서 10으로 기하급수적으로 줄게 됩니다.

mod N을 했을 때 최대값은 N-1 이니까, 그 값이 이미 나왔다면 나머지 모든 재귀 함수를 return 해버려서 최대한 덜 탐색하고 완전탐색을 마무리하는 방식입니다.

 

아주 좋지 않나요?