백준 알고리즘 중급 - 브루트 포스 : 비트마스크 (연습)

근 일주일만의 기록이다.

면접도 준비하고, 바람 좀 쐬느라 늑장을 부렸다.

다시 차근차근, 해오던 거 하자.

정리 시작!

-

* 부분수열의 합 (mid) : 앞에서 재귀로 풀었던 부분수열의 합 문제를 비트마스크를 이용해서 풀어보자.

14225번: 부분수열의 합

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

bool check[2000001];

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

	for (int i = 1; i < (1 << n); i++) {
		int sum = 0;
		for (int j = 0; j < n; j++) {
			if (i&(1 << j)) {
				sum += s[j];
			}
		}
		if(check[sum] == false)
			check[sum] = true;
	}

	for (int i = 1;; i++) {
		if (check[i] == false) {
			cout << i << '\n';
			return 0;
		}
	}
}

- 이중 for문으로 원하는 자리수만큼의 모든 경우를 구하는 요령을 잘 기억해두자. n자리 수의 부분수열을 구하려면, i가 (1<<n) 가지 경우일 때, j가 n 가지 경우인 i & (1<<j)의 값을 구해주면 된다.

- 모든 경우를 bool 배열에 기록하고, 확인해주면 된다.

 

* 가르침 (high) : k개의 글자를 가르칠 때, n개 중에 최대 몇 가지 단어를 읽을 수 있는지 구하는 문제다.

1062번: 가르침

- 일단 anta, tica 라는 글자는 모든 글자의 앞뒤에 포함되어 있다. 최소 a,n,t,i,c 5개는 가르쳐야 된다는 것. 

- 단어 자체를 string으로 입력 받아서 생각하는 것보다는, 26개의 bool 배열을 만들고, 자리수를 생각해주는 것이 계산하기 편할 거다.

- 재귀함수를 사용해서, 해당 인덱스의 글자를 선택할 때와 안 선택할 때로 나눠서 몇 가지 단어를 읽을 수 있는지 계산해준다.

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

int count(int mask, vector<int> &words) {
	int cnt = 0;
	for (int word : words) {
		if ((word & ((1 << 26) - 1 - mask)) == 0) {
			cnt += 1;
		}
	}
	return cnt;
}

int go(int index, int k, int mask, vector<int> &words) {
	if (k < 0) return 0;
	if (index == 26) {
		return count(mask, words);
	}
	int ans = 0;
	int t1 = go(index + 1, k - 1, mask | (1 << index), words);
	if (ans < t1) ans = t1;
	if (index != 'a' - 'a' && index != 'n' - 'a' && index != 't' - 'a'
		&& index != 'i' - 'a' && index != 'c' - 'a') {
		t1 = go(index + 1, k, mask, words);
		if (ans < t1) ans = t1;
	}
	return ans;
}

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

	vector<int> words(n);
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (char x : s) {
			words[i] |= (1 << (x - 'a'));
		}
	}

	cout << go(0, k, 0, words) << '\n';

	return 0;
}

- 각 단어마다 비트마스크를 활용해 자리수를 기록한다. 

- 재귀함수에서 선택하지 않는 경우, 필수로 포함되는 글자 5가지는 제외시킨다. 

- count 함수를 주목하자. 읽을 수 있는지 검사하는 함수인데, 일일이 검사하는 방법도 있지만 시간이 오래 걸리기 때문에 비트마스크를 활용해서 계산한다. 우선 모든 항이 1인 26자리 이진수를 선언하고 거기에 배운 글자가 포함된 mask를 빼준다. 그럼 배운 글자만 0이 될 것이다. 그 수와 단어를 AND 연산해서 0이 나온다면, 모든 글자를 포함하고 있는 것이므로 읽을 수 있는 수다. 이 연산을 꼭 기억해뒀다가 나중에 또 써먹자..

 

* 구슬 탈출 2 (high) : 빨강, 파랑 구슬이 있는 판을 최소 횟수로 기울여서 빨간 구슬만 구멍에 들어가게 하면 된다.

13460번: 구슬 탈출 2

- 일단 보드의 정보를 입력 받는다. 최대 10번까지 시도할 수 있으니까 4^10 가지 경우를 생각할 수 있다. 여기서 몇 가지 의미 없는 경우를 제외 해보자.

- 첫번째로, 같은 방향으로 연속해서 기울이는 경우다. 한번 기울일 때 구슬이 멈출 때까지 기울이므로, 연속해서 기울이는 것은 의미가 없다. 두번째로, 이전과 반대 방향으로 기울이는 경우다. 이전과 반대 방향으로 기울이면 구슬의 위치가 원상복구 되는 것이나 마찬가지이므로 의미가 없다고 할 수 있다. 이 두가지 예외를 제외하면 고려해야 할 경우의 수는 4 (처음엔 아무 방향) * 2^9 = 2^11 가지로 줄어든다는 것을 알 수 있다.

 - 경우를 생각할 때는 크기가 10인 배열에 4진수로 저장해준다. 그래야 비트마스크를 활용해 0, 1, 2, 3 으로 저장한 후 방향을 생각해줄 수 있기 때문이다. 

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

int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
const int LIMIT = 10;

vector<int> gen(int k) {
	vector<int> a(LIMIT);
	for (int i = 0; i < LIMIT; i++) {
		a[i] = (k & 3);
		k >>= 2;
	}
	return a;
}

 // first: 이동 여부, second: 구멍 빠짐 여부
pair<bool, bool>simulate(vector<string> &a, int k, int &x, int &y) {
	if (a[x][y] == '.') return make_pair(false, false);
	bool moved = false;
	while (true) {
		int nx = x + dx[k];
		int ny = y + dy[k];
		if (a[nx][ny] == '#') {
			return make_pair(moved, false);
		}
		else if (a[nx][ny] == 'R' || a[nx][ny] == 'B') {
			return make_pair(moved, false);
		}
		else if (a[nx][ny] == '.') {
			swap(a[nx][ny], a[x][y]);
			x = nx; y = ny;
			moved = true;
		}
		else if (a[nx][ny] == 'O') {
			a[x][y] = '.';
			moved = true;
			return make_pair(moved, true);
		}
	}
	return make_pair(false, false);
}

int check(vector<string> a, vector<int> &dir) {
	int n = a.size();
	int m = a[0].size();
	int hx, hy, rx, ry, bx, by;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (a[i][j] == 'O') {
				hx = i; hy = j;
			}
			else if (a[i][j] == 'R') {
				rx = i; ry = j;
			}
			else if (a[i][j] == 'B') {
				bx = i; by = j;
			}
		}
	}
	int cnt = 0;
	for (int k : dir) {
		cnt += 1;
		bool hole1 = false, hole2 = false;
		while (true) {
			auto p1 = simulate(a, k, rx, ry);
			auto p2 = simulate(a, k, bx, by);
			if (p1.first == false && p2.first == false) break;
			if (p1.second) hole1 = true;
			if (p2.second) hole2 = true;
		}
		if (hole2) return -1;
		if (hole1) return cnt;
	}
	return -1;
}

bool valid(vector<int> &dir) {
	int l = dir.size();
	for (int i = 0; i + 1 < l; i++) {
		if (dir[i] == 0 && dir[i + 1] == 1) return false;
		if (dir[i] == 1 && dir[i + 1] == 0) return false;
		if (dir[i] == 2 && dir[i + 1] == 3) return false;
		if (dir[i] == 3 && dir[i + 1] == 2) return false;
		if (dir[i] == dir[i + 1]) return false;
	}
	return true;
}

int main()
{
	int n, m;
	cin >> n >> m;
	
	vector<string> a(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];

	int ans = -1;
	for (int i = 1; i < (1 << LIMIT * 2); i++) {
		vector<int> dir = gen(i);
		if (!valid(dir)) continue;
		int cur = check(a, dir);
		if (cur == -1) continue;
		if (ans == -1 || ans > cur) ans = cur;
	}

	cout << ans << '\n';

	return 0;
}

- check 함수를 통해 조건에 맞는 최솟값을 구한다. check 함수 내부의 simulate 함수에서 first는 공의 이동 여부를, second는 구멍에 빠졌는지를 확인한다. 빨간공의 상태를 p1, 파란공의 상태를 p2로 두고 계산하는데, 두 공이 멈출 때까지, 즉 p1.first와 p2.first가 모두 false일 때까지 계속해서 기울이기를 반복한다. 구멍에 빠졌는지 여부도 계속해서 체크해주고 조건에 맞게 빨간공만 빠지면 반복문에서 나와서 최솟값과 비교해 갱신해준다.

- 10가지로 한정되는 방향 경우의 수를 크기가 10인 4진수로 나타내는 아이디어는 꼭 기억해두자. 방향에 따라 생기는 경우의 수를 구해야하는 문제가 많으므로 유용하게 쓸 곳이 많을 것 같다.

 

* 2048 (Easy) [high] : Easy는 개뿔 2048 게임 룰에서 5번을 이동할 때 만들 수 있는 최댓값을 구하는 문제다. 

12100번: 2048 (Easy)

- 우선 보드의 크기 n과 n*n에 들어갈 숫자를 입력해준다. 5가지로 한정되는 방향 경우의 수이므로 아까 구슬 탈출에서 사용했던 방법을 응용하면 된다. 이전 문제와 달리 같은 방향으로 연속할 때, 이전과 반대 방향으로 이동할 때 모두 의미를 가질 수 있으므로 예외를 따로 둘 필요는 없다.

- check 함수에서 생각해줘야 할 것이 많다. 코드를 확인하면서 이야기를 해보자.

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

int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
const int LIMIT = 5;

vector<int> gen(int k) {
	vector<int> a(LIMIT);
	for (int i = 0; i < LIMIT; i++) {
		a[i] = (k & 3);
		k >>= 2;
	}
	return a;
}


int check(vector<vector<int>> &a, vector<int> &dirs) {
	int n = a.size();
	// first : 현재 수, second : 결합 여부
	vector<vector<pair<int, bool>>> d(n, vector<pair<int, bool>>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			d[i][j].first = a[i][j];
		}
	}
	// 0 : down, 1 : up, 2 : left, 3 : right
	for (int dir : dirs) {
		bool ok = false;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				d[i][j].second = false;
			}
		}
		while (true) {
			ok = false;
			if (dir == 0) {
				for (int i = n - 2; i >= 0; i--) {
					for (int j = 0; j < n; j++) {
						if (d[i][j].first == 0) continue;
						if (d[i + 1][j].first == 0) {
							d[i + 1][j].first = d[i][j].first;
							d[i + 1][j].second = d[i][j].second;
							d[i][j].first = 0;
							ok = true;
						}
						else if (d[i + 1][j].first == d[i][j].first) {
							if (d[i][j].second == false && d[i + 1][j].second == false) {
								d[i + 1][j].first *= 2;
								d[i + 1][j].second = true;
								d[i][j].first = 0;
								ok = true;
							}
						}
					}
				}
			}
			else if (dir == 1) {
				for (int i = 1; i < n; i++) {
					for (int j = 0; j < n; j++) {
						if (d[i][j].first == 0) continue;
						if (d[i - 1][j].first == 0) {
							d[i - 1][j].first = d[i][j].first;
							d[i - 1][j].second = d[i][j].second;
							d[i][j].first = 0;
							ok = true;
						}
						else if (d[i - 1][j].first == d[i][j].first) {
							if (d[i - 1][j].second == false && d[i][j].second == false) {
								d[i - 1][j].first *= 2;
								d[i - 1][j].second = true;
								d[i][j].first = 0;
								ok = true;
							}
						}
					}
				}
			}
			else if (dir == 2) {
				for (int j = 1; j < n; j++) {
					for (int i = 0; i < n; i++) {
						if (d[i][j].first == 0) continue;
						if (d[i][j-1].first == 0) {
							d[i][j-1].first = d[i][j].first;
							d[i][j-1].second = d[i][j].second;
							d[i][j].first = 0;
							ok = true;
						}
						else if (d[i][j - 1].first == d[i][j].first) {
							if (d[i][j - 1].second == false && d[i][j].second == false) {
								d[i][j - 1].first *= 2;
								d[i][j - 1].second = true;
								d[i][j].first = 0;
								ok = true;
							}
						}
					}
				}
			}
			else if (dir == 3) {
				for (int j = n-2; j >= 0; j--) {
					for (int i = 0; i < n; i++) {
						if (d[i][j].first == 0) continue;
						if (d[i][j + 1].first == 0) {
							d[i][j + 1].first = d[i][j].first;
							d[i][j + 1].second = d[i][j].second;
							d[i][j].first = 0;
							ok = true;
						}
						else if (d[i][j].first == d[i][j + 1].first) {
							if (d[i][j].second == false && d[i][j + 1].second == false) {
								d[i][j + 1].first *= 2;
								d[i][j + 1].second = true;
								d[i][j].first = 0;
								ok = true;
							}
						}
					}
				}
			}
			if (ok == false) break;
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (ans < d[i][j].first) {
				ans = d[i][j].first;
			}
		}
	}
	return ans;
}

int main()
{
	int n;
	cin >> n;
	
	vector<vector<int>>a(n, vector<int> (n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
		}
	}

	int ans = 0;
	for (int i = 1; i < (1 << LIMIT * 2); i++) {
		vector<int> dir = gen(i);
		int cur = check(a, dir);
		if (ans < cur) ans = cur;
	}

	cout << ans << '\n';

	return 0;
}

- int, bool을 포함한 이차원 pair 배열 d를 선언하고, d[i][j].first에는 현재의 값, d[i][j].second에는 결합 여부를 기록.

- dir이 0일 때, down으로 생각해줬다. 조건에 따라 겹쳐질 수 있는 수가 3개 이상 있으면 아래에 있는 수가 겹쳐진다. 따라서 아래에서부터 경우를 생각해준다. d[i][j]를 위에 있는 수, d[i+1][j]를 아래에 있는 수라고 생각하면, d[i][j].first == 0일 때는 내려서 합칠 수 있는 수가 없으므로 건너 뛰어준다. d[i+1][j].first == 0 일 때는 d[i][j]를 d[i+1][j]로 옮겨준다.

- d[i+1][j].first == d[i][j].first 이고 d[i+1][j].second, d[i][j].second 모두 false일 때는 합칠 수 있는 조건이 되니까, d[i+1][j].first *= 2 해주고, d[i][j].first = 0 해준다. 

- 나머지 세 방향은 이를 다른 방향으로만 생각해주면 되고, 이를 5번 반복해주면 된다.

- 대체 왜 easy인지는 모르겠다.

-

점점 체계적으로 생각하지 않으면 풀 수 없는 문제들이 나온다.

주먹구구식으로는 절대 못 푼다. 어떻게 풀지 미리 생각해보고,

적절한 알고리즘, 자료구조도 생각한 뒤에 문제 풀이를 시작하자.

꾸준히 계속 가자. 정리 끝!