Brute Force
중첩 반복문 대체하기
n개의 원소에서 m개를 고르는 모든 조합을 찾는 알고리즘을 쌩 반복문으로 짜면 m중 중첩문이 된다. 하지만 다음과 같이 작업을 쪼개면 재귀로 풀 수 있다.
- 원소들의 총 개수(= n)
- 더 골라야 할 원소들의 개수
- 지금까지 고른 원소들의 번호
void pick(int n, vector<int>& picked, int to_pick) {
// base case: no more to pick
if (to_pick == 0) {
do_something(picked);
return;
}
int smallest = picked.empty() ? 0 : picked.back() + 1;
for (int next = smallest; next < n; next++) {
picked.push_back(next);
pick(n, picked, to_pick - 1);
picked.pop_back();
}
}
보글 게임
const int dx[8] = {-1, -1, -1, 1, 1, 1, 0, 0};
const int dy[8] = {-1, 0, 1, -1, 0, 1, -1, 1};
bool has_word(int y, int x, const string& word) {
if (!in_range(y, x)) {
return false;
}
if (board[y][x] != word[0]) {
return false;
}
if (word.size() == 1) {
return true;
}
for (int dir = 0; dir < 8; dir++) {
int ny = y + dy[dir], nx = x + dx[dir];
if (has_word(ny, nx, word.substr(1))) {
return true;
}
}
return false;
}