브루트 포스의 의미는 모든 경우의 수를 다 구해서 문제를 해결하는 것이다.
이러한 브루트 포스의 핵심을 요약하자면 다음과 같다.
• 브루트 포스로 문제를 풀기 위해서는 다음과 같은 3가지 단계를 생각해볼 수 있다.
1. 문제의 가능한 경우의 수를 계산해본다.
• 직접 계산을 통해서 구한다. 대부분 손으로 계산해볼 수 있다.
2. 가능한 모든 방법을 다 만들어본다.
• 하나도 빠짐 없이 만들어야 한다.
• 대표적으로 그냥 다 해보는 방법, for문 사용, 순열 사용, 재귀 호출 사용, 비트마스크 사용이 있다.
3. 각각의 방법을 이용해 답을 구해본다.
• 이 단계는 보통은 어렵지 않다. 문제에 나와있는 대로 답을 계산해본다.
• 브루트 포스 문제의 시간 복잡도는 대부분 O(경우의 수 *방법 1개를 시도해보는데 걸리는 시간 복잡도)가 걸린다.
1. 난쟁이 문제
이러한 브루트 포스를 통해 난쟁이 문제를 풀 수 있다.
문제 참고 : https://www.acmicpc.net/problem/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
풀이
#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;
}
'Archived(CSE Programming) > 알고리즘(C++)' 카테고리의 다른 글
비트마스크(BitMask) (0) | 2019.08.12 |
---|---|
재귀함수(Recursive Function) (0) | 2019.08.12 |
순열(Permutation) 구하기 (0) | 2019.08.07 |
에라토스테네스의 체(소수 구하기) (0) | 2019.08.06 |
최대공약수(GCD) & 최소공배수(LCM) 구하기 (0) | 2019.08.05 |