알고리즘 문제 해결 전략(3)

무식하게 풀기 - 완전 탐색

재귀 호출과 완전 탐색
재귀 함수
자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고,
나머지를 자기 자신을 호출해 실행하는 함수
모든 재귀함수는 '더이상 쪼개지지 않는' 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야 한다.
쪼개지지 않는 가장 작은 작업 == 기저 사례
for(int i = 0; i < n; ++i)
for(int j = i+1; j < n; ++j)
for(int k = j+1; k < n; ++k)
for(int l = k+1; l < n; ++l)
cout << i << " " << j << " " << k << " " << l << endl;

n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘
// n: 전체 원소의 수
// picked: 지금까지 고른 원소들의 번호
// toPick: 더 고를 원소의 수일때, 앞으로 toPick개의 원소를 고르는 모든 방법을 출력한다.
void pick(int n, vector<int>& picked, int toPick) {
//기저 사례: 더 고를 원소가 없을 때 고른 원소들을 출력한다.
if(toPick == 0) {printPicked(picked); return;}
//고를 수 있는 가장 작은 번호를 계산한다.
int smallest = picked.empty() ? 0 : picked.back() + 1;
//이 단계에서 원소하나를 고른다.
for(int next = smallest; next < n; ++next) {
picked.push_back(next);
pick(n, picked, toPick - 1);
picked.pop_back();
}
}

ex) 보글게임
상하좌우 / 대각선으로 인접한 칸들의 글자들을 이어서 단어를 찾아내는 것
hasWord(y, x, word) = 보들 게임판의 (y, x)에서 시작하는 단어 word의 존재 여부를 반환
문제의 분할
hasWord()가 하는 일을 가장 자연스럽게 조각내는 방법은 각 글자를 하나의 조각으로 만드는 것이다. 함수 호출시에 단어의 시작 위치를 정해 주기 때문에, 문제의 조각들 중 첫 번째 글자에 해당하는 조각을 간단하게 해결할 수 있다. 그 이후에는 시작위치와 인접한 여덟 칸을 모두 시도하면서 답을 찾으면 된다.
기저 사례의 선택
1. 위치 (y, x)에 잇는 글자가 원하는 단어의 첫 글자가 아닌 경우 항상 실패
2. (1번 경우에 해당하지 않을 경우)원하는 단어가 한글자인 경우 항상 성공
Tip: 입력이 잘못되거난 범위에서 벗어난 경우도 기저 사례로 택해서 맨 처음에 처리
const int dx[8] = {-1, -1, -1, 1, 1, 1, 0, 0};
const int dy[8] = {-1, 0, 1, -1, 0, 1, -1, 1};
//5X5의 보글 게임 판의 해당 위치에서 주어진 단어가 시작하는 지를 반환
bool hasWord(int y, int x, const string& word) {
// 기저 사례 1: 시작 위치가 범위 밖이면 무조건 실패
if(!inRange(y,x)) return false;
// 기저 사례 2: 첫 글자가 일치하지 않으면 실패
if(board[y][x] != word[0]) return false;
// 기저 사례 3: 단어 길이가 1이면 성공
if(word.size() == 1) return true;
// 인접한 여덟 칸을 검사한다.
for(int direction = 0; direction < 8; ++direction) {
int nextY = y + dy[direction], next = x + dx[direction];
//다음 칸이 범위 안에 있는지, 첫 글자는 일치하는지 확인할 필요가 없다.
if(hasWord(nextY, nextX, word.substr(1)))
return true;
}
return false;

}

완전 탐색 레시피
1. 완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에
정확히 비례한다. 그러므로 최대 크기의 입력을 가정했을 때 답의 개수를 계산하고 이들을 모두 제한 시간 안에 생성할 수 있을지를 가늠한다.
2. 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눈다.
3. 그중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성
4. 조각이 하나밖에 남지 않으 경우, 혹은 하나도 남지 않은 경우에는 답을 생성했으므로, 그섯을 기저 사례로 선택해 처리한다.

이론적 배경 : 재귀 호출과 부분 문제


문제 : 소풍 (문제 ID: PICNIC, 난이도: 하)
         int n;
bool areFriends[10][10];

    // 아직 짝을 찾지 못한 학생들의 명단이 주어질 때 친구끼리 둘씩 짝짓는 경우의 수를      // 계산하라.
int countPairings(bool taken[10]) {
//기저 사례: i번째 학생이 짝을 이미 찾았으면 true, 아니면 false
bool finished = true;
for (int i = 0; i < n; i++) if (!taken[i]) finished = false;
if (finished) return 1;

int ret = 0;
// 서로 친구인 두 학생을 찾아 짝을 지어준다.
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (!taken[i] && !taken[j] && areFriends[i][j]) {
taken[i] = taken[j] = true;
ret += countPairings(taken);
taken[i] = taken[j] = false;
}
return ret;
}


int n;
bool areFriends[10][10];

// Wrong의 해결 방안: 각 단계에서 남아 있는 학생들 중 가장 번호가 빠른 학생의 짝을 찾아 주도록 하면 된다.
// 아직 짝을 찾지 못한 학생들의 명단이 주어질 때 친구끼리 둘씩 짝짓는 경우의 수를 계산하라.
int countPairings(bool taken[10]) {
// 남은 학생들 중 가장 번호가 빠른 학생을 찾는다.
int firstFree = -1;
for (int i = 0; i < n; ++i) {
if (!taken[i]) {
firstFree = i;
break;
}
}
//기저사례: 모든 학생이 짝을 찾았으면 한 가지 방법을 찾았으니 종료한다.
int ret = 0;
// 서로 친구인 두 학생을 찾아 짝을 지어준다.
for (int pairWith = firstFree + 1; pairWith < n; ++pairWith) {
if (!taken[pairWith] && areFriends[firstFree][pairWith]) {
taken[firstFree] = taken[pairWith] = true;
ret += countPairings(taken);
taken[firstFree] = taken[pairWith] = false;
}
}
return ret;
}

#include <vector>
//주어진 칸을 덮을 수 있는 네가지 방법
//블록을 구성하는 세칸의 상대적 위치
const int coverType[4][3][2] = {
{{0,0},{1,0},{0,1}},
{{0,0},{0,1},{1,1}},
{{0,0},{1,0},{1,1}},
{{0,0},{1,0},{1,-1}}
};
//게임판 밖으로 나가거나, 겹치거나, 검은 칸을 덮을 때 false를 반환
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 ny = y + coverType[type][i][0];
const nx = x + coverType[type][i][1];
if (x < 0 || ny > board.size() || y < 0 || nx > board[0].size())
ok = false;
}

return ok;
}
//board의 모든 빈 칸을 덮을 수 있는 방법의 수를 반환한다.
//board[i][j] = 1 이미 덮인 칸 혹은 검은 칸
//board[i][j] = 0 아직 덮이지 않은 칸
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 = i;
x = j;
break;
}
if (y != -1) break;
}
}
//기저 사례: 모든 칸을 채웠으면 1을 반환한다.
if (y == -1) return 1;
int ret = 0;
for (int type = 0; type < 4; ++type) {
//만약 board[i][j]를 type형태로 덮을 수 있으면 재귀 호출한다.
if (set(board, y, x, type, 1))
ret += cover(board);
//덮었던 블록을 치운다.
set(board, y, x, type, -1);
}
return ret;
}

최적화 문제
문제의 답이 하나가 아니라 여러 개이고, 그 중에서 어떤 기준에 따라 가장 '좋은' 답을 찾아내는 문제 -- n개의 사과 중에서 r개를 골라서 무게의 합을 최대화하는 문제
최적화 문제를 해결하는 방법:
동적계획법, 조합 탐색, 최적화 문제를 결정 문제로 바꿔 해결하는 기법


int n; // 도시의 수
double dist[MAX][MAX]; // 두 도시 간의 거리를 저장하는 배열
//path: 지금까지 만든 경로
//visited: 각 도시의 방문 여부
//currentLength: 지금까지 경로의 길이
//나머지 도시들을 모두 방문하는 경로들 중 가장 짧은 것의 길이를 반환한다.
double shortestPath(vector<int>& path, vector<bool>& visited, double currentLength) {
//기저 사례: 모든 도시를 다 방문했을 때는 시작 도시로 돌아가고 종료한다.
if (path.size() == n)
return currentLength + dist[path[0]][path.back()];
double ret = INF; // 매우 큰 값으로 초기화
// 다음 방문할 도시를 전부 시도해 본다.
for (int next = 0; next < n; ++next) {
if (visited[next]) continue;
int here = path.next();
path.push_back();
path.push_back(next);
visited[next] = true;
//나머지 경로를 재귀 호출을 통해 완성하고 가장 짧은 경로의 길이를 얻는다.
double cand = shortestPath(path, visited, currentLength + dist[here][next]);
ret = min(ret, cand);
visited[next] = false;
path.pop_back();
}
return ret;
}

const int INF = 9999, SWITCHES = 10, CLOCKS = 16;
//linked[i][j] = 'x': i번 스위치와 j번 시계가 연결되어 있다.
//linked[i][j] = '.': i번 스위치와 j번 시계가 연결되어 있지 않다.
const char linked[SWITCHES][CLOCKS + 1] = {
"xxx............",
"...x...x.x.x...",
"....x.....x...xx",
"x...xxxx........",
"......xxx.x.x...",
"x.x...........xx",
"...x..........xx",
".xxxxx..........",
"...xxx...x...x.."
};
//모든 시계가 12시를 가리키고 있는지 확인한다.
bool areAligned(const vector<int>& clocks);
//swtch번 스위치를 누른다.
void push(vector<int>& clocks, int swtch) {
for (int clock = 0; clock < CLOCKS; ++clock)
if (linked[swtch][clock] == 'x') {
clocks[clock] += 3;
if (clocks[clock] == 15) clocks[clock] = 3;
}
}
//clocks: 현재 시계들의 상태
//swtch: 이번에 누를 스위치의 번호가 주어질 때, 남은 스위치들을 눌러서 clocks를 12시로 맞출 수 있는 최소 횟수를 반환한다.
//만약 불가능하다면 INF 이상의 큰 수를 반환한다.
int solve(vector<int>& clocks, int swtch) {
if (swtch == SWITCHES) return areAligned(clocks) ? 0 : INF;
//이 스위치를 0번 누르는 경우부터 세 번 누르는 경우까지를 모두 시도한다.
int ret = INF;
for (int cnt = 0; cnt < 4; ++cnt) {
ret = min(ret, cnt + solve(clocks, swtch + 1));
push(clocks, swtch);
}
//push(clocks, swtch)가 네 번 호출되었으니 clocks는 원래와 같은 상태가 된다.
return ret;

}