#4 Brute Force & Backtracking

Brute Force

가능한 모든 해의 후보를 체계적으로 나열한 뒤, 각각의 후보가 진짜 답인지를 차례대로 확인하는 방법

 

예를 들어 어떤 수 N을 소인수분해 하는 과정을 모두 출력하는 프로그램을 구현한다고 가정하면 

다음과 같은 코드를 짤 수 있습니다.

int N;
void chk(int i);
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	cin >> N;

	for (int i = 2; i <= N; i++) {
		chk(i);
	}

	return 0;
}
void chk(int i) {
	while (N % i == 0) {
		cout << i << '\n';
		N /= i;
	}
}

i가 2부터 시작해서 N까지 가면서 나누어 떨어질때까지 계속 차례대로 확인하는 기법입니다.

그렇게 되면 시간 복잡도는 O(N) 이 됩니다.

 

하지만 이러한 알고리즘은 짝수를 계속해서 나눈다는 점에서 비효율적입니다. 짝수는 2만 계속 나누면 소인수분해를 할 수 있습니다. 굳이 4나 6 등을 또 나눌 필요는 없습니다. 다시 코드를 수정하면

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	cin >> N;

	chk(2);
	for (int i = 1; 2*i+1 <= N; i++) {
		chk(2*i+1);
	}

	return 0;
}

먼저 2로 소인수분해를 한 다음 i를 2*i +1 로 설정하여 홀수만 소인수분해 하도록 설정하였습니다.

따라서 i는 3,5,7,9... 로 진행하게 됩니다. 

시간복잡도는 O(N/2)로 줄어들게 됩니다. 

 

이렇게 알고리즘을 효율적으로 변경할 수 도 있습니다.

---

 Backtracking (퇴각검색)

가능한 후보들중 유망한 후보가 아니면 곧바로 다음 후보를 검색하는 기법

 

bruteforce기법에서 약간의 최적화를 한 것이다.

일반적으로 재귀함수를 이용해 다음 후보를 계산한다.

유망하지 않은 후보라면 그 이후의 함수 호출은 하지 않는다.

예시 문제

백준 9663 (N-Queen) c++

---

Brute Force VS Backtracking

Backtracking은 보통 재귀함수를 이용해 탐색합니다.

Backtracking은 유망하지 않은 후보에 대해 이후의 후보를 전부 탐색하지 않습니다.

Brute Force 기법은 가능한 모든 해를 열거하는 방식의 총칭입니다.