블루트포스

⊙ 학습 목표

코드스니펫

 

블루트포스란?

블루트포스(Brute Force)는 가능한 모든 경우의 수를 하나도 빠짐없이 전부 시도해보는 것이다. 

블루트포스 기법은 보통 자료의 크기가 작거나, 최적화된 알고리즘을 떠올리기가 어려울 때, 혹은 정답이 정말 맞는지 확인하기 위해 사용되곤 한다.

 

하지만 n이 매우 커진다면 시간복잡도가 매우 커서 시간초과가 발생할 수도 있다.

예를 들어 n개의 원소의 부분집합의 개수는 2^n이고 순열의 개수는 n!(팩토리얼)이다. n이 10 정도만 되어도 블루트포스로 충분히 구현할만 하지만 그보다 훨씬 더 큰 수가 n이 된다면 시간 복잡도가 매우 커지기 때문에 이는 주의해야 한다. 그래서 제한사항을 확인해보고 블루트포스로 풀이할 수 있을지 생각해봐야 한다.

 

---

 

블루트포스 사용 전략

블루트포스를 사용하여 문제를 풀기 위해서는 한 가지만 해내면 된다. 모든 경우의 수를 어떻게 탐색할지 방법을 찾아내는 것이다 문제마다 그 방법이 다르겠지만 예를 들어서 몇 가지 살펴보려고 한다. 그래서 그 방법으로 사용할 전략들은 아래와 같다.

1. 중첩 반복문을 활용한 직접 생성
2. bitmasking을 활용한 부분집합 생성
3. STL의 nex_permutation등을 활용한 순열 생성
4. 백트래킹

 

중첩 반복문

작은 설명

for (int i = 1; i <= 3; i++) {
    for (int j = 1; j <= 3; j++) {
        for (int k = 1; k <= 3; k++) {
            cout << i << " " << j << " " << k << "\n";
        }
    }
}

 

bitmasking

작은 설명

 

아래 코드도 마찬가지로 1, 2, 3의 부분집합을 모두 구하는 코드이다. 단 bitmasking을 사용하였다.

void solution1(int num)
{
	vector<int> arr = { 1, 2, 3 };
	int n = arr.size();

	for (int i = 0; i < (1 << n); i++) {
		cout << "{ ";
		for (int j = 0; j < n; j++) {
			if (i & (1 << j)) {
				cout << arr[j] << " ";
			}
		}
		cout << "}\n";
	}
}

for문의 조건에 들어가있는 (1<<n), 그리고 if(i&(1<<j))가 조금 생소해 보여서 코드를 해석하기가 어려웠다.

 

이 코드에서 n=3이다. 그럼 (1<<3)이 무슨뜻인지 알아보자. 비트 연산자 <<는 비트를 왼족으로 이동하는 shift 연산이다. 따라서 지금은 숫자 1 2진수에서 비트를 왼쪽으로 3번 이동한 것으로 이진수 1000이 되게 된다. 즉 (1<<3) = 1000 = 8이다. 결국 바깥 for문은 0부터 7까지 반복하는 평범한 반복문인 것이다.

 

내부의 for문은 0부터 2까지 3번 반복하게 되어 있다. 그 안에 있는 if문을 보면 i & (1 << j)를 조건으로 하고 있다. j가 변함에 따라 (1<<j)는 001, 010, 100으로 변한다. 그리고 i는 0부터 7까지 변하게 된다. i의 값의 변화와 각 값을 2진법으로 나타내면 아래와 같다.

i값(10진수)	i값(2진수)
0	000
1	001
2	010
3	011
4	100
5	101
6	110
7	111

 

 

---

 

배운 내용 정리

• 내용