BruteForce
- 모든 데이터, 경우의 수를 일일이 확인하여 해를 구하는 알고리즘
알고리즘의 기본적인 목표는 주어진 데이터를 탐색하여 해를 구하는 것이다. 알고리즘 설계는 데이터를 어떻게 탐색할 것인가에 대해 초점이 맞추어져 있는데, 이 때 데이터를 탐색하는 가장 기본적인 방법이 바로 Bruteforce이다.
Bruteforce는 주어진 탐색 공간의 원소들을 일일이 탐색하며 해가 될 수 있는지 확인하는 기법이다. 데이터를 모두 탐색하기 때문에, 설정된 탐색 공간(데이터가 표현되는 공간)의 크기에 따라 알고리즘의 효율성이 결정된다고 볼 수 있다. Bruteforce 알고리즘은 크게 2가지 과정으로 동작하며, 해를 구하기 위해 반드시 필요한 기본 과정들이다.
- 탐색 공간의 원소를 하나씩 탐색하기( 반복문, 재귀 등 )
- 각각의 원소가 해가 될 수 있는지 판별하기( 조건 )
이러한 방식의 탐색은 모든 경우를 다 확인하며 해를 구하기 때문에 근사해를 구하는 알고리즘들과는 달리 정확한 해를 구할 수 있다는 특징을 가지며, 최악의 경우에 모든 데이터를 탐색하기 때문에 그만큼의 수행 시간(때로는 비효율적인)이 요구된다. 따라서 데이터가 표현되는 탐색 공간을 어떻게 구성하는지도 알고리즘에 영향을 줄 수 있다.
Bruteforce 기법의 간단한 예로, 서로 다른 2개의 주사위를 던져서 두 눈의 합이 5가 되는 가능한 순서쌍을 모두 탐색하는 문제가 존재한다.
|
1
2
3
4
5
6
|
for(int i=1; i<=6; i++){
for(int j=1; j<=6; j++){
if(i+j==5) printf("(%d, %d)\n", i, j);
}
}
예시 1-1 : 두 눈의 합이 5인 순서쌍 구하기
|
cs |
다른 방식의 구현 또한 존재한다. 위 문제 상황에서 두 주사위에서 나타난 눈의 값을 각각 $i, j$라고 했을 때, $i + j = 5$이므로 $i$가 하나로 정해지면 그에 따라 $j$도 하나로 정해지므로 $i$를 결정하는 것만으로도 그에 대응하는 유일한 해를 구할 수 있게 된다.
|
1
2
3
4
5
6
7
|
for(int i=1; i<=6; i++){
int j=5-i;
if(j>0){
printf("(%d, %d)\n", i, j);
}
}
예시 1-2 : 더 효율적인 알고리즘
|
cs |
위 알고리즘은 특정한 $i$에 대해 대응하는 $j$가 유일하게 결정된다는 성질을 이용해 $j$에 대한 탐색이 필요 없음을 정당화하여 더 적은 연산횟수로 알고리즘을 개선한 방법이다. 이들은 같은 Brutefoce 기법을 이용했음에도 불구하고 데이터를 $(i, j)$ 꼴의 순서쌍으로 표현한 첫 번째 알고리즘과는 달리, $i$에 대해 $j$가 대응하는 형태로 표현한 두 번째 알고리즘이 더욱 효율적으로 동작한다. 이들의 시간복잡도를 비교하면 O($N^{2})$에서 O($N$)으로 개선되었음을 알 수 있다. 이처럼 데이터를 어떻게 설계하느냐에 따라 탐색 공간의 크기가 결정되고, 탐색 공간의 크기에 비례하게 연산 횟수가 결정되므로 시간복잡도를 개선할 수 있게 된다.
탐색 공간
탐색 공간은 데이터가 표현되는 공간으로 이는 집합을 의미할 수도 있으며, 선형적인 형태의 Array나 Graph의 형태로 표현될 수 있다. 위에서 언급한 주사위 문제에 대해서는 탐색 공간이 다음과 같이 나타날 수 있다.
같은 해를 구하는 알고리즘이라 하더라도 탐색 공간을 어떻게 구성하는지에 따라서 알고리즘의 효율성이 달라질 수 있다. 만약 친구 간 연결관계에 대한 탐색 문제라면 탐색 공간이 Graph로 결정될 것이다. 위와 같이 우리는 임의로 탐색 공간을 설정할 수 있게 되는데, 이 때 탐색 과정에서는 인자(parameter)가 존재한다. 탐색에서의 인자는 탐색 공간에서의 위치를 의미한다. 예를 들어 2차원 좌표 평면을 탐색한다면 탐색 인자는 각 좌표를 나타내는 $x$와 $y$이다. 위 문제로 예를 들어보면, Code 1에서의 인자는 두 주사위의 눈 수 $i$, $j$가 되고, Code 2에서는 주사위의 첫 번째 눈 수인 $i$만이 탐색 인자가 될 것이다. 결국 인자의 갯수가 탐색 공간의 크기를 결정하게 되는 요인으로 작용하므로, 인자를 줄일 수 있도록 문제(탐색 공간)를 재정의하는 것이 중요하다. 이는 Parametric Search에서 더욱 자세하게 다룰 것이다.
Implementation
Bruteforce Algorithm을 구현하는 방법은 탐색 공간의 형태에 의해 결정된다. 탐색 공간이 Array와 같은 선형 공간이라면 반복문을 활용한 순차 탐색을 통해 구현할 수 있고, 탐색 공간이 다차원 공간 혹은 비선형 공간(Graph 등)이라면 재귀 탐색을 통해 구현할 수 있다. ( 다차원 공간은 반복문으로도 가능하지만, 입력 받는 N에 의해 차원이 바뀐다면 재귀 탐색으로 구현한다. )
다음의 문제를 반복문 기반, 재귀 기반의 탐색으로 구현하는 코드를 각각 소개한다. 아래 구현들은 Bruteforce 기법에서 형태가 거의 유지되므로, 이 구현을 잘 익혀두는 것이 큰 도움이 될 것이다.
8자리 이하의 자릿수를 가지는 0 이상인 정수 중, 각 자리 수가 모두 다른 정수를 모두 구하시오.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
int upper = 1e9;
int arr[10]; // arr[i] : i가 존재하는 갯수
for(int i=0; i<upper; i++){
int num = i, isSolution = 1;
while(num){
arr[num%10]++; // 각 자리의 숫자를 counting
num /= 10;
}
for(int j=0; j<10; j++){
// j가 num에서 2개 이상 존재하면 해가 될 수 없다
if(arr[j] > 1) isSolution = 0;
}
if(isSolution) printf("%d\n", i);
for(int j=0; j<10; j++) arr[j] = 0;
}
|
cs |
(Code 1) 가능한 경우를 0부터 1씩 증가시키며 반복문을 통해 탐색한다. 이 때, 해가 될 수 있는지 판단하기 위해 arr을 이용해 0, 1, 2, ..., 9의 개수를 세어 그 개수가 1 이하인지 확인한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
int l = 0, r = 1e9;
int arr[10];
void f(int x)
{
// x가 해가 되는지 판별
if(l<=x && x<r){
int num = x, isSolution = 1;
while(num){
arr[num%10]++;
num /= 10;
}
for(int i=0; i<10; i++){
if(arr[i] > 1) isSolution = 0;
}
for(int i=0; i<10; i++) arr[i] = 0;
if(isSolution) printf("%d\n", x);
}
if(x>=r) return;
for(int i=0; i<=9; i++){
f(x*10 + i);
}
}
|
cs |
(Code 2) 재귀 함수 f(x)에 존재하는 인자 x가 탐색 변수로, x에 10을 곱하고 한 자리 자연수를 더해 재귀호출을 해주는 과정을 통해 숫자의 자릿수를 늘려가며 탐색한다. x가 $[l, r)$에 속해있을 때는 각 자리 수가 서로 다른지 확인하여 해가 될 수 있는지 확인한다.
Bruteforce 기법은 알고리즘 설계 측면에서 가장 단순한 기법이기 때문에 효율적인 알고리즘이 되기는 어렵다. 하지만 모든 해를 구해야 하는 경우에는 Bruteforce 기법이 유일한 방법이기 때문에 구현 방법을 익히는 것이 중요하다. 또한 Bruteforce 기법을 통한 알고리즘 설계는 문제를 더 명확하게 만들 수 있다. 일반적으로 문제 해결(Problem Solving) 측면에서의 알고리즘 설계는 주어진 $N$의 제한에 따라 시간복잡도를 설정하고, 알고리즘을 구상하는 방식으로 진행되는데, 이 때 완전 탐색을 통해 시간복잡도의 상한을 잡고, 이를 개선시키는 방향으로 알고리즘을 구성할 수 있다. 이러한 이유로 Bruteforce 기법과 탐색 공간의 설계가 큰 중요성을 가진다.
Problems
반복 탐색 3문제, 재귀 탐색 1문제로 구성
BOJ 2798 블랙잭: 카드 3장의 합이 M을 넘지 않으면서 M에 최대한 가까운 값이 되도록 하는 카드의 합을 구하는 문제로, 카드 3장을 3중 반복문으로 일일이 정해주고 M과 세 수의 합을 비교하여 답을 구할 수 있다. 이 때 탐색 공간은 정해야 하는 카드 3장의 인덱스 값 순서쌍인 $(i, j, k)$ $(1 ≤ i, j, k ≤ M)$으로 결정된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n, m;
int arr[10001];
int main()
{
scanf("%d %d", &n, &m);
for(int i=0; i<n; i++){
scanf("%d", &arr[i]);
}
int mx=0;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
for(int k=0; k<n; k++){
if(i!=j && j!=k && k!=i){
if(arr[i]+arr[j]+arr[k]<=m){
mx=max(mx, arr[i]+arr[j]+arr[k]);
}
}
}
}
}
printf("%d\n", mx);
return 0;
}
|
cs |
BOJ 18111 마인크래프트: 땅의 높이를 모두 맞추어야한다. 이 때 우리는 최종 결과가 모든 땅이 같은 높이를 가지게 되는 상태라는 것을 알고 있으므로, 답을 정해주었을 때에 따른 결과가 어떻게 될지를 확인하면 된다. 즉, 땅의 최종 높이를 일일이 바꾸어 보며 그에 따른 결과를 구한다. 반복문을 이용해 땅의 높이를 정해주고 땅의 높이에 따른 결과 값들을 비교해서 min value를 구하면 답이 된다. 이 때 탐색 공간은 '높이'라는 상수값에 N, M size의 map이 대응되는 꼴이 될 것이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#include <iostream>
using namespace std;
int n, m, k, x=0x7fffffff, y;
int arr[501][501];
int mn=0x7fffffff, idx=0;
int main()
{
scanf("%d %d %d", &n, &m, &k);
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
scanf("%d", &arr[i][j]);
x=min(x, arr[i][j]);
y=max(y, arr[i][j]);
}
}
for(int h=x; h<=y; h++){
int t=0, remove=0, build=0;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(arr[i][j]>h){ remove+=(arr[i][j]-h); }
else if(arr[i][j]<h){ build+=(h-arr[i][j]); }
}
}
t=2*remove+build;
if(remove+k>=build && mn>=t){
mn=t;
idx=h;
}
}
printf("%d %d\n", mn, idx);
return 0;
}
|
cs |
BOJ 1107 리모컨 : 채널을 이동하는 방법이 2가지로 나뉠 것이다. 첫 번째 방법은 문제 예제에 나와 있듯이 "숫자 버튼으로 임의의 수를 만들고, 그 후 +/-만을 이용해 도달하는 방법" ( ex. 5455++(예제 1) )이고, 두 번째 방법은 "100에서 시작해서 +/-만으로 이동하는 방법"이다.
숫자 버튼으로 임의의 수를 만드는 과정은 2번 이상 필요하지 않다. 왜냐하면 숫자 버튼으로 수를 만드는 것을 2번 이상 하는 것은 1번만으로 가능하기 때문이다. 따라서 이동하는 방법은 위와 같이 2가지 밖에 없다.
두 번째 방법의 이동 횟수는 $ | N-100 | $이고, 첫 번째 방법의 이동 횟수의 최솟값만을 구하면 된다.
이 때 우리는 Bruteforce 기법을 이용하는데, 0부터 1,000,000까지 일일이 탐색하면서 "숫자 버튼으로 $i$를 만들 수 있는가?"를 확인한 후, 가능하다면 답을 | $i$ - $N$ |과 비교하여 최솟값으로 갱신한다.
탐색 범위의 상한이 50만이 아닌 이유는 다음과 같다. 만약 $N = 500,000$이고 이용 가능한 숫자가 오직 6, 0 뿐이라면 60,000에서 +를 쓰는 것보다 600,000에서 -를 사용하는 것이 이득이기 때문이다. 즉, 숫자 버튼으로 만드는 임의의 수가 50만을 넘어갈 수 있기 때문이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
#include <iostream>
#include <algorithm>
using namespace std;
int N, M, k;
int ban[10]; // i가 사용 불가능한 숫자 버튼이라면 ban[i] = 1
int ans;
// 숫자 버튼을 누르는 횟수(n의 길이)를 반환
int length_int(int n)
{
int cnt = 0;
if(n==0) return ban[0]==1 ? -1 : 1;
// n의 각 자리 수를 확인하며 숫자 버튼으로 만들 수 있는지 확인
while(n){
if(ban[n%10]) return -1;
n/=10, cnt++;
}
return cnt;
}
int main()
{
scanf("%d %d", &N, &M);
for(int i=0; i<M; i++){
scanf("%d", &k);
ban[k]=1;
}
// 100에서 +/-를 이용하는 경우
ans = abs(N-100);
for(int i=0; i<=1000000; i++){
int l=length_int(i);
if(f){
ans=min(ans, l+abs(N-i));
}
}
printf("%d\n", ans);
return 0;
}
|
cs |
BOJ 1759 암호 만들기 : 규칙은 3가지이다. 암호문의 길이가 L이고, 모음의 갯수가 1개 이상, 자음의 갯수가 2개 이상인 것이다. 그러면 임의의 문자열을 만들고, 그 문자열이 위 3가지 조건을 만족하는지만 확인하면 된다. 임의의 문자열을 만드는 방법은 다음과 같다.
- 재귀 함수의 탐색 인자를 x로 하여, x는 입력받은 문자열의 인덱스 값을 나타낸다.
- x의 값을 증가시키면서 각각의 x에 대해, x번째 문자를 고른 경우, 고르지 않은 경우를 재귀 탐색한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int MAX_C = 15;
int L, C;
char s[MAX_C];
/*
현재 보고 있는 s의 인덱스가 x
[0, x)의 인덱스까지 고른 자음의 개수 : y
[0, x)의 인덱스까진 고른 모음의 개수 : z
*/
vector<char> arr;
void f(int x, int y, int z)
{
// 현재 보고 있는 인덱스가 C(다 탐색함)
if(x == C){
if(arr.size() != L || y<2 || z<1) return;
for(char &i : arr) printf("%c", i);
printf("\n");
return;
}
// 탐색은 2가지 방향으로 가능하다.
// 1. x번째 문자를 고르고 다음으로 넘어간다.
// 2. x번째 문자를 고르지 않고 다음으로 넘어간다.
int p = 0;
if(s[x] == 'a' || s[x] == 'e' || s[x] == 'i' || s[x] == 'o' || s[x] == 'u') p = 1;
else p = -1;
arr.push_back(s[x]);
f(x+1, (p == -1) + y, (p == 1) + z);
arr.pop_back();
f(x+1, y, z);
}
int main()
{
scanf("%d %d ", &L, &C);
for(int i=0; i<C; i++){
scanf("%c", &s[i]);
getchar();
}
sort(s, s+C);
f(0, 0, 0);
return 0;
}
|
cs |
'Algorithm' 카테고리의 다른 글
| 그래프란? (0) | 2021.02.11 |
|---|---|
| [ DP ] 동적 계획법 (Dynamic Programming) (0) | 2021.02.11 |
| [ Sort ] 다양한 정렬 방법 (0) | 2021.02.11 |
| [ Search ] 백트래킹 (BackTracking) (0) | 2021.02.11 |
| [ Search ] 이분탐색(Binary Search), Parametric Search (0) | 2021.02.11 |