브루트 포스(Brute Force)

브루트 포스의 의미는 모든 경우의 수를 다 구해서 문제를 해결하는 것이다.

이러한 브루트 포스의 핵심을 요약하자면 다음과 같다.

• 브루트 포스로 문제를 풀기 위해서는 다음과 같은 3가지 단계를 생각해볼 수 있다.
1. 문제의 가능한 경우의 수를 계산해본다.
• 직접 계산을 통해서 구한다. 대부분 손으로 계산해볼 수 있다.
2. 가능한 모든 방법을 다 만들어본다.
• 하나도 빠짐 없이 만들어야 한다.
• 대표적으로 그냥 다 해보는 방법, for문 사용, 순열 사용, 재귀 호출 사용, 비트마스크 사용이 있다.
3. 각각의 방법을 이용해 답을 구해본다.
• 이 단계는 보통은 어렵지 않다. 문제에 나와있는 대로 답을 계산해본다.
• 브루트 포스 문제의 시간 복잡도는 대부분 O(경우의 수 *방법 1개를 시도해보는데 걸리는 시간 복잡도)가 걸린다.

 

1. 난쟁이 문제

이러한 브루트 포스를 통해 난쟁이 문제를 풀 수 있다.

문제 참고 : https://www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

풀이

#include <iostream>
#define SWAP(x,y,t) (t=x,x=y,y=t)
using namespace std;

int main() {
	// 변수 선언
	int value[9];
	int sum = 0;
	int i, j, temp, fin=0;

	// 입력
	for (i = 0; i <9; i++) {
		cin >> value[i];
		sum += value[i]; // 총합기록
	}

	// 버블 정렬
	for (i = 0; i < 9; i++) {
		for (j = i + 1; j < 9; j++) {
			if (value[i] > value[j])
				SWAP(value[i], value[j], temp);
		}
	}

	// 뽑기
	i = 0;
	while(true){
		for (j = i+1; j < 9; j++) {
			if ((sum - value[i] - value[j]) == 100) {
				fin = 1;
				break;
			}
		}
		// 탈출
		if (fin == 1)
			break;
		i++;
	}

	// 출력
	for (int idx = 0; idx < 9; idx++) {
		// 가짜 난쟁이 출력제외
		if (idx == i || idx == j)
			continue;
		// 출력
		cout << value[idx]<<"\n";
	}

	return 0;
}

2. 날짜 계산 문제

문제 참고 : https://www.acmicpc.net/problem/1476

1476번: 날짜 계산

풀이

#include <iostream>
using namespace std;

int main() {
	int year = 1;
	int e=1, m=1, s=1;
	int E, M, S;

	// 입력받기
	cin >> E >> M >> S;

	// 탐색
	while (true) {
		// 찾음
		if (e == E && m == M && s == S)
			break;

		// 증가
		e = (e + 1) % 16;
		m = (m + 1) % 29;
		s = (s + 1) % 20;
		
		// 0 처리
		if (e == 0)
			e++;
		if (m == 0)
			m++;
		if (s == 0)
			s++;

		year++;
	}

	// 출력
	cout << year;

	return 0;

}