브루트 포스

Brute Force(브루트 포스) 알고리즘

브루트 포스(Brute Force)는 완전 탐색이라고도 하며, 가능한 모든 경우의 수를 탐색하여 해를 찾는 알고리즘 기법이다.

예를 들어 100개의 정수중 5가 존재하는지의 여부를 알아볼 때, 실제로 100개의 수를 모두 조사할 생각으로 반복문을 사용하여 찾고자 하는 값이 나올 때까지 반복해주어야 한다.

브루트 포스의 구현은 반복문 (for, while)으로 구현하는 것이 일반적이다. 하지만 반복문을 중첩시키다 보면 시간 복잡도가 기하급수적으로 늘어나기 때문에 주의가 필요하다. 또한 모든 겅우의 수를 빠뜨리지 않고 탐색하도록 반복문을 작성해주어야 한다.

활용 방법

1차원 탐색 - O(n)

배열에서 최댓값 찾기

c++

int findMax(vector<int>& arr) {
    int maxVal = arr[0];
    for (int i = 1; i < arr.size(); i++) {
        maxVal = max(maxVal, arr[i]);
    }
    return maxVal;
}

2차원 탐색 - O(n²)

예제: 두 수의 합이 target인 쌍 찾기

c++

pair<int, int> sumTwo(vector<int>& arr, int target) {
    int n = arr.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] + arr[j] == target) {
                return {i, j};
            }
        }
    }
    return {-1, -1};
}

예시) 백준 #2798 블랙잭

주어진 카드 중 3장을 골라 합이 21을 넘지 않으면서, 가장 큰 경우를 고르는 문제이다.

c++

//card 배열에는 모든 카드가 들어있다고 가정
int main() {
	for(int i = 0 ; i < n ; i++) {
		for(int j = i+1 ; j < n ; j++) {
			for(int k = j+1 ; k < n ; K++) {
				int sum = card[i]+card[j]+card[k];
				if( sum <= 21) ans = max(ans, sum);
			}
		}
	}
}

for 문을 카드 하나당 하나씩, 총 3중첩을 하여 모두 다른 카드 3장을 골라서 21보다 크지 않은지 확인한다. 만약 크지 않다면 정답을 저장하는 변수 ans와 3장의 합 sum중 더 큰 것을 ans에 저장하게 된다.

두번째와 세번째 반복문의 시작이 각각 i+1, j+1인 이유는 이미 i번째, j번째 카드는 앞에서 선택하였기 때문에 중복을 막기 위함이다. 예를 들어 1,2,4를 선택하는 경우와 4,1,2를 선택하는 경우는 같은 경우의 수이므로 이러한 경우를 배제 시켜줘야 한다.