6장. 무식하게 풀기

본 포스팅은 《구종만, 『알고리즘 문제 해결 전략』, 인사이트》 를 참고하여 만들어졌습니다.

6.1 도입

 

전산학에서 무식하게 푼다(Brute-Force)는 말은 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미한다. 이렇게 가능한 방법을 전부 만들어 보는 알고리즘들을 가리켜 흔히 완전 탐색(Exhaustive Search)이라고 부릅니다. 얼핏 보면 이런 것을 언급할 가치가 있나 싶을 정도로 간단한 방법이지만, 완전 탐색은 사실 컴퓨터의 장점을 가장 잘 이용하는 방법입니다. 실제 프로그래밍 대회에서도 프로그램을 빠르고 정확하게 구현하는 능력을 검증하기 위해 입력의 크기를 작게 제한한 문제들이 흔히 출제되며, 완전 탐색은 더 빠른 알고리즘의 기반이 되기도 하기 때문에 완전 탐색에 대해 잘 익혀 둘 필요가 있습니다.

 

---

6.2 재귀 호출과 완전 탐색

1) 재귀호출

컴퓨터가 수행하는 많은 작업들은 대개 작은 조각들로 나누어 볼 수 있습니다. 우리가 들여다보는 범위가 작아지면 작아질수록 각 조각들의 형태가 유사해지는 작업들을 많이 볼 수 있습니다. 이런 작업을 구현할 때 유용하게 사용되는 개념이 바로 재귀함수, 혹은 재귀호출입니다. 재귀함수란 자신이 수행할 작업을 유사한 형태의 여러 주각으로 쪼갠 뒤 그 중 한 조각을 수행하고 나머지를 자기 자신을 호출해 실행하는 함수를 가리킵니다.

 

#include <iostream>
using namespace std;

//sum from 1 to n
int sum(int n){
	int sum=0;
	for(int i=0;i<=n;i++){
		sum+=i;
	}
	return sum;
}

int recursiveSum(int n){
	if(n==1) return 1;
	return n+recursiveSum(n-1);
}

int main() {
	
	cout<< "Loop sum : "<<sum(10)<<endl;
	cout<< "Recursive sum : "<< recursiveSum(10)<<endl;
	
	return 0;
}

 recursiveSum에서  if문에 주목하자. 재귀함수를 작성 할 때는 만드시 base case(기저 사례)를 정의해야하며, 함수가 반복되어 호출되면서 점점 base case에 가까워져야 한다!

 

(1) 재귀호출을 이용한 예시 : 중첩 반복문 대체하기

0번부터 차례대로 번호 매겨진 n개의 원소 중 네 개를 고르는 모든 경우를 출력하는 코드를 작성해보자.

예를들어  n=7이라면 (0,1,2,3), (0,1,2,4), (0,1,2,5) ... (3,4,5,6)의 모든 경우를 출력하는 것이다.

 

반복문을 이용하면 어렵지 않게 해결 할 수 있다.

 

#include <iostream>
using namespace std;

int main() {
	
	int n;
	cin >> n;
	
	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;
				}
			}
		}
	}
	
	return 0;
}

같은 작업을 재귀함수로 바꿔봅시다.

 

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

void pick(int n, vector<int>& pickedList, int pickCount) {
	
	//base case print
	if (pickCount == 0) {
		cout << "( ";
		for (vector<int>::iterator i = pickedList.begin(); i != pickedList.end(); i++) {
			cout << *i << " ";
		}
		cout << ")" << endl;
	}

	int newItem = pickedList.empty() ? 0 : pickedList.back() + 1;

	for (int i = newItem; i < n; i++) {
		pickedList.push_back(i);
		
		//Recursive Call
		pick(n, pickedList, pickCount - 1);
		
		pickedList.pop_back();
	}
}

int main() {

	vector<int>& pickList =  * (new vector<int>());
	int n;

	cin >> n;

	pick(n, pickList, 4);
	
	return 0;
}

 

(2) 예제1 : 보글 게임

https://algospot.com/judge/problem/read/BOGGLE

algospot.com :: BOGGLE

#include <string>

extern int** board;
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) {
	
	//base case 1  : out of range
	if (!inRange(y, x)) {
		return false;
	}

	//base case 2 : not match
	if (board[y][x] != word[0]) {
		return false;
	}

	//base case 3 : find word!
	if (word.size() == 1) {
		return true;
	}

	//recursive call
	for (int d = 0; d < 8; d++) {
		int nextY = y + dy[d], nextX = x + dx[d];
		if (hasWord(nextY, nextX, word.substr(1))) {
			return true;
		}
	}

	//can not find word
	return false;

}

//check the range
bool inRange(int y, int x) {
	for (int i = 0; i < 8; i++) {
		if (x + dx[i] >= 5 || x + dx[i] <= -1 || y + dy[i] >= 5 || y + dy[i] <= -1) {
			return false;
		}
	}
	return true;
}

Tip!

• Error Case를 Base Case로 처리해서 코드를 간결하게 만든다!
• 무식하게 재귀호출을 이용하여 모든 경우를 조사한다! 하지만 이때 시간복잡도를 계산해보면 단어의 길이가 n이라 할 때 O(8^n)이 되기 때문에 단어의 길이가 길다면 해당 알고리즘을 이용할 수 없다!

(3) 시간 복잡도 분석

완전 탐색 알고리즘의 시간 복잡도는 답이 가능한 후보들을 모두 만들어보기 때문에 시간복잡도를 계산하기 위해서는 가능한 후보의 수를 전부 세어 보기만 하면 된다!

 

(4) 완전 탐색 레시피

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

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

재귀 호출을 공부하면서 짚고 넘어가야 할 중요한 개념 중의 하나로 '문제'와 '부분문제'의 정의가 있다. 재귀 호출을 논의할 때 '문제'란 항상 수행해야 할 작업과 그 작업을 적용할 자료의 조합을 의미한다. 가령, {1,2,3}과 {3,2,1}을 정렬하는 문제는 서로 다른 문제이다. 문제를 구성하는 조각들 중 하나를 빼, 문제의 일부를 만들 수 있는데, 이런 문제들을 원래 문제의 부분문제라고 한다. 가령 {1,3,2}를 정렬하는 경우 1은 정렬이 끝났기 때문에 1을 때어내고 {3,2}를 정렬시킨다면 {3,2}를 정렬하는 문제를 부분문제라고 할 수 있을 것이다.

 

---

6.3 문제 : 소풍

https://algospot.com/judge/problem/read/PICNIC

algospot.com :: PICNIC

 

재귀 호출을 이용해 문제를 해결해려면 우선 각 답을 만드는 과정을 여러 개의 조각으로 나누어야 합니다. 여기서는 전체 문제를 n/2개의 조각으로 나눠서 한 조각마다 두 학생을 짝지어 주는 것으로 한다. 이때 문제의 형태는 아직 짝을 찾지 못한 학생들의 명단이 주어질 때 친구끼리 둘씩 짝짓는 경우의 수를 계산하라가 됩니다. 명단에서 서로 친구인 두 학생을 찾아 이들을 짝지어주고나면 남은 학생들을 짝지어 주는 문제도 원래 문제와 같은 형태가 되니까요.

 

중복으로 세는 문제

//잘못된 재귀호출 : 중복된 경우를 세는 경우

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

//taken[i] = i번째 학생이 짝을 이미 찾았으면 true, 아니면 false
int countPairings(bool taken[10]) {
	//base case : 모든 학생이 짝을 찾았으면 한 가지 방법을 찾았으니 종료한다.
	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;
}

코드를 자세히 들여다 보면 두 가지 문제점을 찾을 수 있다.

1. 같은 학생쌍을 두 번 짝지어 준다. 가령, (0,1) 과 (1,0)을 따로 세고 있다.
2. 다른 순서로 학생들을 짝지어 주는 것을 서로 다른 경우로 세고 있다. 가령 (0,1) , (2,3)을 짝지어 주는 것과 (2,3) 후에 (0,1)을 짝지어주는 것을 완전히 같은 방법인데 다른 방법으로 세고 있다.

실직적으로 같은 답을 중복으로 세는 이런 상황은 경우의 수를 다룰 때 굉장히 흔하게 마주치게 된다. 이 상황을 해결하기 위해 선택할 수 있는 좋은 방법은 항상 특정 형태를 갖는 답만을 세는 것입니다. 흔히 사용하는 방법으로는 같은 답 중에서 사전순으로 가장 먼저 오는 답 하나만을 세는 것이 있습니다. 가령 (2,3), (0,1)이나 (1,0),(2,3)은 세지 않지만 (0,1), (2,3)을 세는 것이죠. 이 속성을 강제하기 위해서는 각 단계에서 남아있는 학생들 중 가장 번호가 빠른 학생의 짝을 찾아 주도록 하면 됩니다.c 

 

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

//taken[i] = i번째 학생이 짝을 이미 찾았으면 true, 아니면 false
int countPairings(bool taken[10]) {
	//base case : 모든 학생이 짝을 찾았으면 한 가지 방법을 찾았으니 종료한다.
	int firstFree = -1;

	for (int i = 0; i < n; i++) {
		if (!taken[i]) {
			firstFree = i;
			break;
		}
	}

	if (firstFree == -1) return 1;

	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;
}

---

6.4 문제 : 게임판 덮기

https://algospot.com/judge/problem/read/BOARDCOVER

algospot.com :: BOARDCOVER

이 문제도경우의 수를 세는 것이니만큼, 게임판을 덮을 수 있는 모든 경우를 생성하는 완전탐색을 이용해 해결할 수 있습니다. 우선 입력으로 주어진 게임 판에서 흰 칸의 수가 3의 배수가 아닐 경우에는 무조건 답이 없으니 이 부분을 따로 처리하도록 한다. 이외의 경우에는 흰 칸의 수를 3으로 나눠서 내려놓을 블록의 수 N을 얻은 뒤, 문제의 답을 생성하는 과정을 N조각으로 나눠 한 조각에서 한 블록을 내려놓도록 합니다. 재귀함수는 주어진 게임판에 블록을 한 개 내려놓고 남은 흰 칸들을 재귀 호출을 이용해 덮도록 하면 된다.

 

 그러나 이런 식으로는 경우의 수를 셀 수 없다. 블록을 놓는 순서는 이 문제에서 중요하지 않은데, 방금 설명한 방식으로는 같은 배치도 블록을 놓는 순서에 따라 여러 번 세기 때문이다!

 

소풍 예제에서와 같이 특정 순서를 설정함으로 이런 문제를 해결 할 수 있는데, 가장 간편한 방법은 재귀 호출의 각 단계마다 아직 빈 칸 중에서 가장 윗 줄, 그 중에서도 가장 왼쪽에 있는 칸을 덮도록 하는 것입니다.

 

#include<vector>
extern vector<vector<int>>& board;

//주어진 칸을 덮을 수 있는 네 가지 방법
//블럭을 구성하는 세 칸의 상대적 위치 (dx,dy)의 목록

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} }
};

//board의 (y,x)를 type번 방법으로 덮거나, 덮었던 블록을 없앤다.
//delta=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 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[1].size(); j++) {
			if (board[i][j] == 0) {
				y = i;
				x = j;
				break;
			}
		}
		if (y != -1) break;
	}

	//base case : 모든 칸을 채웠으면 1을 반환한다.
	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);
		}
		
		//덮여있던 블럭을 치운다. delta=-1로 설정
		set(board, y, x, type, -1);
	}

	return ret;
}

 

---

6.5 최적화 문제

 

지금까지 다뤘던 문제와는 달리 문제의 답이 하나가 아니라 여러 개이고, 그 중에서 어떤 기준에 따라 가장 좋은 답을 찾아 내는 문제들을 통칭해 최적화 문제(Optimization Problem)라고 부릅니다. 최적화 문제를 해결하는 방법에는 여러가지가 있지만 그 중 가장 기초적인 것이 완전 탐색이다. 완전 탐색은 최적화 문제를 풀기 위한 가장 직관적인 방법이다. 가능한 답을 모두 생성해 보고 그 중 가장 좋은 것을 찾아내면 되기 때문이다.

 

예제 : 여행하는 외판원 문제 (TSP)

가장 유명한 최적화 문제 중 하나로 여행하는 외판원 문제(Traveling Salesman Problem, TSP)가 있다. 어떤 나라에 n개의 큰 도시가 있는데, 한 영업 사원이 한 도시에서 출발해서 다른 도시들을 전부 한 번씩 방문한 뒤 시작 도시로 돌아오려고 한다. 문제를 단순화하기 위해 모든 도시들은 직선도로로 연결되어 있다고 한다. 이때 가능한 모든 경로 중 가장 짧은 경로를 어떻게 찾아낼 수 있을까?

완전 탐색으로 문제를 풀기 위한 첫 번째 단계는 시간 안에 답을 구할 수 있을지 확인하는 것이다. n개의 도시를 모두 나열하는 방법은 n!임으로 시간 복잡도는 O(n!)이 된다. 도시의 갯수가 많다면 완전 탐색으로 문제를 풀 수 없지만 10개정도의 도시는 충분히 해결가능하다!

 

#include<vector>
#include<limits>
#define MAX 10

int n; //도시의 수
double dist[MAX][MAX]; //두 도시 간의 거리를 저장하는 배열

//path: 지금까지 만든 경로
//visited: 각 도시의 방문 여부
//currentLength: 지금까지 만든 경로의 길이
//나머지 도시들을 모두 방문하는 경로들 중 가장 짧은 것의 길이를 반환한다.

double shortestPath(vector<int>& path, vector<bool>& visitedm double currentLength) {
	
	//base case : 모든 도시를 다 방문했을 때는 시작 도시를 돌아가고 종료한다.
	if (path.size() == n) {
		return currentLength + dist[path[0]][path.back()];
	}

	double ret = DBL_MAX; //매우 큰 값으로 초기화

	//다음 방문할 도시를 전부 시도해 본다.
	for (int next = 0; next < n; next++) {
		if (visited[next]) continue;

		int here = path.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;
}

 

---

6.6 시계 맞추기

https://algospot.com/judge/problem/read/CLOCKSYNC

algospot.com :: CLOCKSYNC

 

이 문제는 있는 그대로 풀려고 하면 꽤나 복잡해진다. 그러나 문제의 특성을 이용해 적절히 단순화하면 완전 탐색으로 해결 할 수 있다. 이 문제에서 처음 깨달아야 할 것은 예제 입출력 설명이 유도하는 방향과는 달리 스위치를 누르는 순서는 전혀 중요하지 않다는 것이다. 두 스위치를 누르는 순서를 바꾼다고 해서 그 결과가 바뀌지는 않기 때문이다. 따라서 우리가 계산해야 할 것은 각 스위치를몇 번이나 누를 것이냐 뿐이다. 

이렇게 문제를 바꾼다고 해도 곧장 완전 탐색을 적용할 수는 없다. 완전 탐색 알고리즘을 사용하려면 스위치를 누르는 횟수의 모든 조합을 하나하나 열거할 수 있어야 하는데 각 스위치를 몇 번 누르는지는 상관없고 따라서 그 조합의 수는 무한하기 때문이다. 이때, 어떤 스위치를 네번 누르면 연결된 시계는 모두 제자리로 돌아오게 되는 것을 이용하여 유한하게 바꿀 수 있다. 따라서 어떤 스위치를 4번 이상 누르는 경우는 고려하지 않아도 된다.

 

#include<vector>
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........",
	"x.x...........xx",
	"...x..........xx",
	"....xx.x......xx",
	".xxxxx..........",
	"...xxx...x...x.."
};

// 모든 시계가 12시를 가리키고 있는지 확인한다.
bool areAligned(const vector<int>& clock);

//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;
		}
	}
}

//clock : 현재 시계들의 상태
//swtch : 이번에 누를 스위치의 번호가 주어질 때, 남은 스위치들을 눌러서 clock을 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(clock, swtch + 1));
		push(clocks, swtch);
	}

	//push(clocks,swtch)가 네 번 호출되었으니 clocks는 원래와 같은 상태가 된다.
	return ret;
}

---

6.7 많이 등장하는 완전 탐색 유형

주어진 원소를 만들 수 있는 모든 순열 만들기, 주어진 원소 중 R개를 골라낼 수 있는 방법 만들기 등은 다른 문제의 부분 문제로도 빈번히 출제됩니다. 그러니 입력의 크기에 따라 답의 개수가 어떻게 변하는지를 알고 구현하는 방법을 연습해 두면 좋습니다.

 

모든 순열 만들기

서로 다른 N개의 원소를 일렬로 줄 세우는 것을 순열(permutation)이라고 부른다. 주어진 원소의 모든 순열을 생성해서 풀 수 있는 문제는 꽤 자주 만날 수 있는 편이고, 다른 문제의 부분 문제로 나타나기도 하는 만큼 모든 순열을 생성하는 코드를 한 번 신경써서 작성해 보면 좋습니다. 가능한 모든 순열은 O(n!)의 시간 복잡도를 갖는데 n이 10이 넘어간다면 다른 방법을 생각해야 합니다.

C++ 사용자들은 이런 형태의 문제에서 굉장히 유리한데, 표준 라이브러리인 STL에 포함된 next_permutation() 함수에서 모든 순열을 순서대로 생성하는 작업을 대신해 주기 때문이다. 다른 언어에서는 이와 비슷한 코드를 직접 작성하거나 재귀 호출을 통해 순열을 생성할 수밖에 없습니다.

 

모든 조합 만들기

서로 다른 N개 원소 중에서 R개를 순서 없이 골라낸 것을 조합(Combination)이라고 부릅니다. 

 

2^n가지 경우의 수 만들기

n개의 질문에 대한 답이 예/아니오 중의 하나라고 할 때 존재할 수 있는 답의 모든 조합의 수는 2^n가지입니다. 이 모든 조합들을 생성하는 것은 굉장히 흔한 문제인데, 각 조합을 하나의 n비트 정수로 표현한다고 생각하면 재귀 호출을 사용할 것 없이 1차원 for문 하나로 이 조합들을 간단하게 모두 시도 할 수 있습니다.