‘무식하게 푼다(brute-force)’ 는 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미합니다.
이렇게 가능한 방법을 전부 만들어 보는 알고리즘을 완전 탐색이라고 부릅니다.
재귀 호출
재귀 함수(recursive function)란 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수를 가리킵니다.
재귀 호출의 기초적인 성질을 이해하기 위해 가장 간단한 반복문을 재귀 함수로 바꿔 구현해 봅시다.
int sum(int n){ // 반복함수
int ret=0;
for(int i=1;i<=n;i++)
ret+=i;
return ret;
}
int recursiveSum(int n){ //재귀 함수
if(n==1) return 1; // 더이상 쪼개지지 않을 때 - base case
return n+recursiveSum(n-1);
}
모든 재귀 함수는 ‘더 이상 쪼개지지 않는’ 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야 합니다. 이때 쪼개지지 않는 가장 작은 작업들을 가리켜 재귀 호출의 기저 사례(base case)라고 합니다.
예제: 보글 게임 (문제 ID: BOGGLE, 난이도: 하)
https://algospot.com/judge/problem/read/BOGGLE
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 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], nextX = x+ dx[direction];
//다음 칸이 범위 안에 있는지, 첫 글자는 일치하는지 확인할 필요가 없다
if(hasWord(nextY, nextX, word.substr(1)))
return true;
}
return false;
}
시간 복잡도 분석
시간복잡도를 계산하기 위해서는 가능한 후보의 수를 전부 세어 보기만 하면 됩니다. 단어의 길이가 N이라 할 때 O(8^N)이 되므로 단어의 길이가 짧은 경우에만 완전 탐색으로 해결할 수 있습니다.
완전 탐색 레시피
- 완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에 정확히 비례합니다. 최대 크기의 입력을 가정했을 때 답의 개수를 계산하고 이들을 모두 제한 시간 안에 생성할 수 있을지를 가늠합니다.
- 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눕니다. 각 선택은 답의 후보를 만드는 과정의 한 조각이 됩니다.
- 그중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성합니다.
- 조각이 하나밖에 남지 않은 경우, 혹은 하나도 남지 않은 경우에는 답을 생성했으므로, 이것을 기저 사례로 선택해 처리합니다.
재귀 호출을 공부하면서 짚고 넘어가야 할 중요한 개념 중의 하나로 문제(problem)와 부분 문제(subproblem)의 정의가 있습니다. 재귀 호출을 논의할 때 '문제'란 항상 수행해야 할 작업과 그 작업을 적용할 자료의 조합을 의미합니다.
문제: 소풍(문제 ID: PICNIC, 난이도: 하)
https://algospot.com/judge/problem/read/PICNIC
// 친구 관계를 저장하는 2차원 배열
bool areFriends[10][10];
// 학생들이 짝지어졌는지 여부를 저장하는 배열
bool taken[10];
// 학생들을 짝지어주는 재귀 함수
int countPairings(int n) {
// 아직 짝지어지지 않은 첫 번째 학생을 찾음
int firstFree = -1;
for (int i = 0; i < n; ++i) {
if (!taken[i]) {
firstFree = i;
break;
}
}
// 기저 사례: 모든 학생이 짝지어졌으면 한 가지 방법을 찾았으니 종료한다.
if (firstFree == -1) return 1;
int ret = 0;
// 첫 번째 학생과 짝지을 친구를 찾음
// fistFree 이후의 학생 중에서
for (int pairWith = firstFree + 1; pairWith < n; ++pairWith) {
// 짝지어지지 않았고, 친구 관계가 있는 학생을 찾음
if (!taken[pairWith] && areFriends[firstFree][pairWith]) {
// 두 학생을 짝지음
taken[firstFree] = taken[pairWith] = true;
// 다음 상태로 재귀 호출
ret += countPairings(n);
// 짝을 원래 상태로 되돌림
taken[firstFree] = taken[pairWith] = false;
}
}
return ret;
}
문제 : 게임판 덮기(문제 ID: BOARDCOVER, 난이도: 하)
https://algospot.com/judge/problem/read/BOARDCOVER
// 블록의 4가지 모양을 정의
const int coverType[4][3][2]{
{ {0,0}, {1,0}, {0,1} }, // 0번 타입: ┌─
{ {0,0}, {0,1}, {1,1} }, // 1번 타입: ─┐
{ {0,0}, {1,0}, {1,1} }, // 2번 타입: └─
{ {0,0}, {1,0}, {1,-1} } // 3번 타입: ─┘
};
//board의 (y,x)를 type번 방법으로 덮거나, 덮었던 블록을 없앤다
//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 ny = y + coverType[type][i][0];
const int nx = x + coverType[type][i][1];
// 블록이 게임판을 벗어나는 경우
if (ny < 0 || ny >= board.size() || nx < 0 || nx >= board[0].size()) {
ok = false;
}
else if ((board[ny][nx] += delta) > 1) {
// 블록이 중복 배치된 경우
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[0].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;
// 4가지 블록 배치 시도
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;
}
출처 : 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략
'알고리즘' 카테고리의 다른 글
| [알고리즘] 시간 복잡도 (1) | 2024.12.23 |
|---|