[Algorithm] 브루트 포스 (Brute Force)

1. 브루트 포스란?

브루트 포스는 직역하면 '무식한 힘'으로 모든 조건을 탐색하여 요구 조건에 맞는 결과만을 가져오는 알고리즘입니다. 어떤 방식으로든 모든 경우의 수를 탐색한다면, 브루트 포스 알고리즘을 사용했다고 할 수 있습니다.

모든 경우의 수를 탐색하기 때문에 언제나 최적해를 찾을 수 있다는 장점이 있지만, 영역, 조건에 따라 시간복잡도가 기하급수적으로 증가할 수 있다는 단점도 가지고 있습니다.

2. 종류

선형구조 - 순차탐색
비선형구조 - DFS(깊이우선탐색), BFS(너비우선탐색)

이번 포스팅에는 선형구조인 순차탐색을 다루겠습니다.

3. 순차탐색

순차탐색은 아래와 같은 방법으로 문제를 해결합니다.

1. 주어진 문제를 선형구조로 바꾼다.
2. 자료들을 구조에 맞는 방법으로 해를 구할 때까지 탐색한다.
3. 탐색된 해를 문제 출력 조건에 맞게 출력한다.

이 알고리즘을 사용할 시 시간복잡도가 매우 크게 증가합니다.

4. 문제풀이

대표적인 순차탐색 문제인 블랙잭을 풀어보겠습니다.
https://www.acmicpc.net/problem/2798
C++

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
#pragma warning (disable:4996)

int main(void) {
	int N, M, res, save, save_gap, gap, min, max;
	int* card;
	bool flag = true;
	scanf("%d %d", &N, &M);
	card = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &card[i]);
	}
	// 오름차순 정렬
	sort(card, card + N);

	min = card[0] + card[1] + card[2];
	max = card[N - 1] + card[N - 2] + card[N - 3];
	save_gap = M - min;
	// 카드 3장의 최대합이 정답일 경우
	if (max <= M) {
		res = max;
	}
	// 카드 3장의 최대합이 오답일 경우
	else {
		for (int i = 0; i < N - 2; i++) {
			for (int j = i + 1; j < N - 1; j++) {
				for (int k = j + 1; k < N; k++) {
					save = card[i] + card[j] + card[k];
					gap = M - save;
					// 연속된 3장의 카드의 gap 값이 0보다 작을 경우 모든 시뮬레이션 종료
					if ((i + 1 == j) && (j + 1 == k) && (gap < 0)) {
						flag = false;
						break;
					}
					if (gap < 0) continue;
					else {
						if (gap < save_gap) {
							//printf("\ngap: %d\nsave_gap: %d\n", gap, save_gap);
							//printf("[%d]\n<%d %d %d>\ni: %d\nj: %d\nk: %d\n\n", save, card[i], card[j], card[k], i, j, k);
							res = save;
							save_gap = gap;
						}
					}
				}
				if (flag == false) break;
			}
			if (flag == false) break;
		}
	}
	printf("%d\n", res);
	free(card);
}