Chapter 6 - Bruteforce
- Bruteforce는 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법이다.
- Bruteforce는 기저사례(Base case)를 포함한 재귀함수(Recursive function)를 이용한다.
- 모든 재귀함수는 ‘더 이상 쪼개지지 않는’ 최소한의 작업에 도달하면 답을 곧장 내야한다.
- 모든 재귀함수는 범위를 초과하거나 오류라고 판단하는 조건에 해당하면 답을 곧장 내야한다.
Ex 01 - 보글게임 (BOGGLE, 下)
-
[STEP 1] - Bruteforce를 써야함을 떠올리기 위한 단서
- 임의의 좌표 (y, x)에서 해당하는 단어를 찾기 위해서는 8방향 모두 검사해야 된다는 점
- 5x5 격자로 범위가 한정되어 있다는 점
-
[STEP 2] - 기저사례(Base case) 를 설정한다.
- 임의의 좌표 (y, x)에 해당하는 단어가 원하는 i번째 단어가 아닌 경우 탐색 실패
- 좌표 (y, x)가 격자를 넘어서는 경우 탐색 실패
- 좌표 (y, x)가 (n-1, n-1)까지 도달했다면 탐색 성공
-
[STEP 3] - 코드 작성
#include <iostream>
#include <vector>
using namespace std;
static int C = 0;
static vector<string> board(5);
static const vector<int> dx{ -1, -1, -1, 1, 1, 1, 0, 0 }; // x축 방향 변위
static const vector<int> dy{ -1, 0, 1, -1, 0, 1, -1, 1 }; // y축 방향 변위
bool isRange(int y, int x) { return (0 <= y && y < 5) && (0 <= x && x < 5); }
bool hasWord(int y, int x, const string& word) {
if (!isRange(y, x)) return false; // [기저 1] - 범위 벗어남
if (board[y][x] != word[0]) return false; // [기저 2] - 원하는 글자 아닌 경우
if (word.size() == 1) return true; // [기저 3] - 단어 찾은 경우
for (int dir = 0; dir < 8; ++dir) // 8방향에 대해 재귀를 돌린다.
if (hasWord(y + dy[dir], x + dx[dir], word.substr(1)))
return true;
return false;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> C;
while (C--) {
for (int i = 0; i < 5; ++i) cin >> board[i]; // 5x5 격자 생성
int N{ 0 }; cin >> N;
vector<string> word(N);
for (int i = 0; i < N; ++i) cin >> word[i]; // 찾을 N개 단어 입력받음
cout << '\n';
bool flag = false;
for (int i = 0; i < N; ++i) {
cout << word[i] << " ";
flag = false;
for (int y = 0; y < 5; ++y) {
for (int x = 0; x < 5; ++x) {
if (hasWord(y, x, word[i])) { // 단어를 찾았다면,
flag = true;
break;
}
}
if (flag) break;
}
if (flag) cout << "YES\n";
else cout << "NO\n";
}
}
}+ 3가지 기저사례를 코드로 작성하고, 함수의 가장 첫 부분에 배치해서 쓸데없이 변수가 낭비되지 않도록 막는다.
+ Bruteforce는 재귀가 기본이다. 8방향을 비교해야하므로 8번 재귀를 돌아야한다.
+ 알고스팟의 BOGGLE 문제는 본 코드로는 ‘수행시간’ 내에 풀 수 없다.Ex 02 - 소풍 (PICNIC, 下)
-
가능한 모든 조합의 수를 계산하는 가장 기본적인 방법은 bruteforce를 이용하는 것이다.
-
학생의 수 n은 최대 10명이고 모두 친구인 경우 9x7x5x3x1 = 945가지이므로 bruteforce 방법이 유효하다.
-
중복 counting을 피하기 위해 규칙을 정하자. ->
낮은 번호 학생에서 높은 학생으로 가면서 짝을 짓기 -
코드를 작성한다.
#include <iostream> #include <vector> using namespace std; int countingPairs(const vector<vector<bool>> friends, vector<bool>& taken) { int firstFind{ -1 }; // 짝이 이뤄지지 않은 제일 첫 학생의 인덱스 번호를 구한다. for (int i = 0; i < taken.size(); ++i) { if (taken[i] == false) { firstFind = i; break; } } if (firstFind == -1) return 1; // 기저조건 - 모두 짝이 이뤄진 경우 int ret{ 0 }; for (int i = firstFind + 1; i < taken.size(); ++i) { // 짝이 정해져있지는 않지만 친구가 있다면, 처리가 필요함. if (!taken[i] && friends[firstFind][i]) { taken[firstFind] = taken[i] = true; // true로 고정시키고, ret += countingPairs(friends, taken); // 재귀 호출 taken[firstFind] = taken[i] = false; // false로 바꿔주고 다른 경우 탐색 } } return ret; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N{ 0 }; cin >> N; while (N--) { int studentNum{ 0 }, pairNum{ 0 }; cin >> studentNum >> pairNum; vector<vector<bool>> friends(studentNum, vector<bool>(studentNum)); for (int i = 0; i < pairNum; ++i) { int x{ 0 }, y{ 0 }; cin >> x >> y; friends[x][y] = friends[y][x] = true; // x와 y가 짝이면 y와 x도 짝임. } vector<bool> taken(studentNum, false); // i번째 학생의 짝 여부 int ans = countingPairs(friends, taken); cout << ans << '\n'; } }-
Bruteforce를 사용하기 전에 반드시 답의 상한이 얼마나 될지 예측하고 얼마나 오래 걸릴지 계산해야한다!
-
특정 경우의 수를 고정 시키고 재귀를 돌린 뒤 원상복귀 시켜줘서 다른 경우를 탐색하도록 하는 패턴을 파악하자!
-
Ex 03 - 게임판 덮기 (BOARDCOVER, 下)
-
난도 ‘하’지만 해법을 떠올리지 못하면 정말 어려운 BF 문제다.
-
Height와 width가 최대 20이고 흰 칸은 최대 50칸이므로 bruteforce는 유효한 전략이다.
-
[기저 조건 1] - 한 블럭은 무조건 3칸을 차지하므로 흰 칸이 3의 배수가 되지 않는 경우 무조건 실패다.
-
[기저 조건 2] - 블럭이 차지하는 3칸 중 한 칸이라도 검은 칸이거나 다른 블럭과 겹칠경우 무조건 실패다.
-
[기저 조건 3] - 남은 흰 칸이 존재하지 않는 경우 무조건 성공이다.
-
코드를 작성하자.
#include <iostream> #include <vector> using namespace std; constexpr int coverType[4][3][2] = { // 블럭 배치 가능한 경우 4가지 (y, x) {{0, 0}, {1, 0}, {0, 1}}, // ┌ 모양 {{0, 0}, {0, 1}, {1, 1}}, // ┐ 모양 {{0, 0}, {1, 0}, {1, 1}}, // └ 모양 {{0, 0}, {1, 0}, {1, -1}} // ┘ 모양 }; /* Bruteforce 시행 전, 흰 칸의 개수가 3의 배수인지 먼저 검사한다. */ bool initCheck(const vector<vector<int>>& gameBoard) { int count = 0; for (int y = 0; y < gameBoard.size(); ++y) for (int x = 0; x < gameBoard[0].size(); ++x) if (gameBoard[y][x] == 0) count++; return (count % 3 == 0); } /* 기준 좌표 (y, x)에 블럭을 놓는다. delta = 1이면 블럭을 놓고, -1이면 블럭을 제거한다. */ bool set(vector<vector<int>>& board, int y, int x, int type, int delta) { bool ok = true; for (int i = 0; i < 3; ++i) { const int newY = y + coverType[type][i][0]; const int newX = x + coverType[type][i][1]; if (newY < 0 || newY >= board.size() || newX < 0 || newX >= board[0].size()) ok = false; // 인덱스 범위 초과 시 false; else if ((board[newY][newX] += delta) > 1) ok = false; // 이미 블럭이 있는 경우 } return ok; } int cover(vector<vector<int>>& board) { int y = -1, x = -1; for (int i = 0; i < board.size(); ++i) { for (int j = 0; j < board[i].size(); ++j) { if (board[i][j] == 0) { y = static_cast<int>(i); x = static_cast<int>(j); break; } } if (y != -1) break; } if (y == -1) return 1; int ret = 0; for (int type = 0; type < 4; ++type) { if (set(board, y, x, type, 1)) ret += cover(board); set(board, y, x, type, -1); } return ret; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int C = 0; cin >> C; vector<int> ans; while (C--) { int height = 0, width = 0; cin >> height >> width; vector<vector<int>> gameBoard(height, vector<int>(width)); char ch; for (int y{ 0 }; y < height; ++y) { for (int x{ 0 }; x < width; ++x) { cin >> ch; gameBoard[y][x] = ((ch == '.') ? 0 : 1); } } if (initCheck(gameBoard)) ans.push_back(cover(gameBoard)); else ans.push_back(0); } for (int i = 0; i < ans.size(); ++i) cout << ans[i] << '\n'; }-
블럭을 놓을 수 있는 경우의 수가 4가지 임을 떠올릴 수 있어야 한다.
-
고정 - 재귀 - 해제 패턴을 따르므로 set() 함수의 delta 매게변수를 떠올릴 수 있어야 한다. delta값에 따라서 블럭을 고정시키거나 해제할 수 있다.
-
Ex 04 - 시계 맞추기 문제
-
스위치를 누를 때 마다 +3씩 되는 덧셈이 기조이므로 교환법칙이 성립한다는 것을 깨달아야한다. 즉, 스위치를 누르는 순서는 중요하지 않다.
-
같은 스위치를 4번 누르는 것은 해당 스위치를 누르지 않은 것과 동일하다. 따라서 한 스위치는 0~3번만 눌린다.
-
스위치는 총 10개이므로 전체 경우의 수는 4^10^ = 약 100만이므로 bruteforce 방법은 유효하다.
-
코드를 작성해보자.
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; const static int INF = 9999; const vector<vector<bool>> switches{ {1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1}, {1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0}, {1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1}, {0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1}, {0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1}, {0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0} }; /* 재귀가 끝났을 때, 모든 시계가 12시를 가리키고 있는지 검사한다. */ bool isCorrect(const vector<int>& clk) { for (int i = 0; i < 16; ++i) if (clk[i] != 12) return false; return true; } /* 스위치를 눌렀다면 연결된 시계가 3시간 증가한다. */ void push(vector<int>& clk, int switchNum) { for (int i = 0; i < 16; ++i) { if (switches[switchNum][i]) { // 연결된 시계를 clk[i] += 3; // 3시간 증가시켜주고, if (clk[i] == 15) clk[i] = 3; // 15시라면, 3시로 바꿔준다. } } } int solve(vector<int>& clk, int switchNum) { // 재귀가 끝났다면 검사해준다. 성공했다면 0을 반환, 실패했다면 INF 반환. if (switchNum == 10) return (isCorrect(clk)) ? 0 : INF; int ret = INF; for (int i = 0; i < 4; ++i) { // 스위치는 0~3번만 눌린다. ret = min<int>(ret, i + solve(clk, switchNum + 1)); // 0~9번 스위치 재귀 push(clk, switchNum); // 0, 1, 2, 3번 스위치를 누른다. } return ret; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int C = 0; cin >> C; while (C--) { vector<int> clk(16); for (int i = 0; i < 16; ++i) cin >> clk[i]; int ans = solve(clk, 0); if (ans != INF) cout << ans << '\n'; else cout << -1 << '\n'; } }- 이 문제는 고정 - 재귀 - 해제 패턴을 따르지 않는다는 점이 특징이다. 왜냐하면 4번 누름 = 0번 누름이기 때문에 해제를 해주는 것은 불필요한 과정이기 때문이다.
- 0~9번 스위치에 대해 push() 하고, for loop가 4회 돌면서 각 경우의 수를 모두 탐색하게 된다.
마치며
- Bruteforce를 사용하기 전, 반드시 수행시간, 메모리와 상한을 계산해서 유효성을 검사하자.
- Bruteforce는 재귀가 원칙이다. 재귀를 사용하기 위해서는 모든 경우의 수에 대해 동일한 과정을 수행할 수 있는지 없는지를 따져야 한다.
- 고정 - 재귀 - 해제 패턴을 따르는지 혹은 따르지 않는 문제인지 구별할 수 있어야 한다.
- 기저 사례를 정확히 뽑아내는 힘을 길러야 한다.
임베디드 시스템 공학자를 지망하는 컴퓨터공학+전자공학 복수전공 학부생입니다. 타인의 피드백을 수용하고 숙고하고 대응하며 자극과 반응 사이의 간격을 늘리며 스스로 반응을 컨트롤 할 수 있는 주도적인 사람이 되는 것이 저의 20대의 목표입니다.