백준 알고리즘 기초 - 브루트 포스 (비트마스크)

영일영일영일영일

브루트 포스 마지막 파트다.

여러모로 쓸모 있는 스킬이지만, 특정 문제에만 적용되고, 속도가 좀 느리다는 단점이 있다.

그래도 정리 해뒀다가 잘 써먹자.

정리 시작!

-

* 비트마스크 : 비트 연산을 사용해서 부분집합을 표현할 때 사용한다.

 - S에 i를 추가 : S |= (1 << i)

 - S에서 i를 제거 : S &= ~(1 << i)

 - S에 i가 있는지 검사 : S & (1 << i)

 - 전체 집합은 (1<<N) - 1 로, 공집합은 0으로 나타낼 수 있다.

 - 1 << N - 1 은 1 << (N - 1) 이라고 봐야한다.

 - 이 정도는 기억하고 기본적인 문제부터 풀어보자

 

* 집합 (low) : 비트마스크의 기본적인 개념을 아는지 확인하는 문제다.

11723번: 집합

#include <iostream>
#include <string>

using namespace std;

int s = 0;

void add(int x) {
	if (s & (1 << x))
		return;
	s |= (1 << x);
}

void remove(int x) {
	if (!(s & (1 << x)))
		return;
	s &= ~(1 << x);
}

bool check(int x) {
	if (s & (1 << x)) 
		return true;
	return false;
}

void toggle(int x) {
	s ^= (1 << x);
}

void all() {
	s = (1 << 21) - 1;
}

void empty() {
	s = 0;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int m, x;
	cin >> m;

	while (m--) {
		string str;
		cin >> str;

		if (str == "add") {
			cin >> x;
			add(x);
		}

		else if (str == "remove") {
			cin >> x;
			remove(x);
		}

		else if (str == "check") {
			cin >> x;
			if (check(x)) {
				cout << 1 << '\n';
			}
			else {
				cout << 0 << '\n';
			}
		}

		else if (str == "toggle") {
			cin >> x;
			toggle(x);
		}

		else if (str == "all") {
			all();
		}

		else if (str == "empty") {
			empty();
		}
	}

	return 0;
}

 - 첨에 시간초과가 떠서 꽤 애를 먹었다. ios_base를 쓰니까 되더라. 효율성이 필요한 문제에서는 꼭 쓰자. 아님 그냥 printf 쓰던지..

 

* 부분수열의 합 (mid) : '비트마스크는 이렇게 쓰는구나' 감을 잡는 문제

1182번: 부분수열의 합

#include <iostream>
using namespace std;

int a[20];

int main() {
	int n, s;
	cin >> n >> s;

	for (int i = 0; i < n; i++)
		cin >> a[i];

	int ans = 0;
	for (int i = 1; i < (1 << n); i++) {
		int sum = 0;
		for (int k = 0; k < n; k++) {
			if (i&(1 << k)) {
				sum += a[k];
			}
		}
		if (sum == s) ans += 1;
	}

	cout << ans << '\n';

	return 0;
}

 - 0부터 1 << n -1 까지 확인한다. 모두 선택을 안 한 것부터 모두 선택한 것까지.. 시간은 좀 걸리지만 모든 경우를 확인할 수 있는 간단한 방법이다. 그리고 해당 위치에 수가 선택 됐는지 차례로 확인한다.

 

* 스타트와 링크 (mid) : 앞에서 풀었던 문제를 비트마스크를 사용해 풀어본다,

14889번: 스타트와 링크

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int s[20][20];

int main() {
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> s[i][j];
		}
	}

	int ans = -1;
	for (int i = 0; i < (1 << n); i++) {
		vector <int> first, second;
		for (int j = 0; j < n; j++) {
			if (i&(1 << j)) first.push_back(j);
			else second.push_back(j);
		}

		if (first.size() != n / 2) continue;
		int t1 = 0, t2 = 0;
		for (int j = 0; j < n / 2; j++) {
			for (int k = 0; k < n / 2; k++) {
				if (j == k) continue;
				t1 += s[first[j]][first[k]];
				t2 += s[second[j]][second[k]];
			}
		}
		int diff = abs(t1 - t2);
		if (ans == -1 || ans > diff) ans = diff;
	}

	cout << ans << '\n';

	return 0;
}

 - 모든 경우를 확인하기 때문에 재귀보다 시간이 훨씬 오래 걸린다. 이렇게도 풀 수 있다는 것만 알아두자.

 

* 종이 조각 (mid) : 아리까리 했는데, 힌트를 보고 바로 방향을 잡았다.

14391번: 종이 조각

 - 각 위치를 가로, 세로로 나눠서 정보를 저장하는 것이 관건이었다. 합의 최댓값이기 때문에 연속된 수는 모두 분할되는 일이 없이 쭉 연결된 수라고 생각해주면 된다.

 - 우선 좀 조잡하지만 스스로의 힘으로 풀어봤다.

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int n, m;
vector <vector<int> > a, check;

int score()
{
	int sum = 0;

	for (int i = 0; i < n; i++) {
		vector<int> s;
		for (int j = 0; j < m; j++) {
			if (check[i][j]) s.push_back(a[i][j]);
			else {
				int k = 1;
				while (s.size()) {
					int v = s.back();
					sum += v*k;
					s.pop_back(); 
					k *= 10;
				}
			}
		}
		int k = 1;
		while (s.size()) {
			int v = s.back();
			sum += v*k;
			s.pop_back();
			k *= 10;
		}
	}

	for (int i = 0; i < m; i++) {
		vector<int> s2;
		for (int j = 0; j < n; j++) {
			if (!check[j][i]) s2.push_back(a[j][i]);
			else {
				int k = 1;
				while (s2.size()) {
					int v = s2.back();
					sum += v*k;
					s2.pop_back();
					k *= 10;
				}
			}
		}
		int k = 1;
		while (s2.size()) {
			int v = s2.back();
			sum += v*k;
			s2.pop_back();
			k *= 10;
		}
	}

	return sum;
}

int main() {
	cin >> n >> m;

	char c[4];
	for (int i = 0; i < n; i++) {
		cin >> c;
		vector<int> tmp;
		for (int j = 0; j < m; j++) {
			tmp.push_back(c[j] - '0');
		}
		a.push_back(tmp);
	}
	
	check = a;
	int ans = 0;
	for (int i = 0; i < (1 << n*m); i++) {
		for(int j=0; j<n*m; j++) {
			if (i&(1<<j)) {
				check[j / m][j%m] = 1; // 가로
			} else
				check[j / m][j%m] = 0; // 세로
		}

		int m = score();
		if (ans < m) ans = m;
	}

	cout << ans << '\n';

	return 0;
}

 - 가로, 세로 정보를 저장하는 이차원 배열을 따로 만들어서 가로면 1, 세로면 0으로 저장했다. 이차원 배열의 항은 아무리 커봤자 16이므로, 그냥 일차원이라고 생각하고 n*m 크기만큼 비트마스크를 사용해서 모든 경우를 계산해준다. 

 - score 함수를 통해 위치 정보를 바탕으로 값의 합을 계산해주면 된다. 근데 중복되는 계산도 많고 좀 지저분하다. 훨씬 깔끔한 정답 코드도 같이 첨부해본다.

#include <iostream>
#include <cstdio>
using namespace std;
int a[4][4];
int main() {
    int n, m;
    scanf("%d %d",&n,&m);
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            scanf("%1d",&a[i][j]);
        }
    }
    int ans = 0;
    // 0: -, 1 : |
    for (int s=0; s<(1<<(n*m)); s++) {
        int sum = 0;
        for (int i=0; i<n; i++) {
            int cur = 0;
            for (int j=0; j<m; j++) {
                int k = i*m+j;
                if ((s&(1<<k)) == 0) {
                    cur = cur * 10 + a[i][j];
                } else {
                    sum += cur;
                    cur = 0;
                }
            }
            sum += cur;
        }
        for (int j=0; j<m; j++) {
            int cur = 0;
            for (int i=0; i<n; i++) {
                int k = i*m+j;
                if ((s&(1<<k)) != 0) {
                    cur = cur * 10 + a[i][j];
                } else {
                    sum += cur;
                    cur = 0;
                }
            }
            sum += cur;
        }
        ans = max(ans,sum);
    }
    cout << ans << '\n';
    return 0;
}

 - i*m+j 로 표현된 k는 항의 순서를 나타낸다. 위에서는 가로, 아래에서는 세로로 분리된 수를 계산해준다.

 - 연속된 수면 지금까지 계산된 수에 10을 곱해서 다음 항을 더해준다. 연속이 아니면 그 전까지 더했던 수를 sum에 더하고 cur 변수를 초기화 한다.

 - 훨씬 빠르고 깔끔한 코드였다.. 좋은 코드를 많이 봐야 실력도 는다....

-

브루트 포스 챕터가 끝났다.

전부다 계산해야 하는 것이기에, 효율성과는 거리가 좀 있지만

백트래킹, 비트마스크 기법 등을 사용해 전부 계산 하더라도 똑똑하게 계산하는 습관을 들이자.

이번 챕터에서도 많이 배웠다. 여기저기 써먹어야겠다.

다음 단원으로 가자!

정리 끝!