06 무식하게 풀기

Jun·2021년 8월 15일
구종만북알고리즘정리
0

알고리즘 문제해결전략

목록 보기
3/4

계속 수정됩니다.

알고리즘을 고안하기 위해서는 해결할 문제의 특성을 이해하고, 동작 시간과 사용하는 공간 사이의 상충 관계를 이해해야 하며, 적절한 자료 구조를 선택할 줄 알아야 한다.

대부분의 사람들이 쉬운 문제를 어렵게 푸는 실수를 한다.
이런 실수를 피하기 위해 문제를 마주하고 나면 가장 먼저 스스로에게 물어보자.
"무식하게 풀 수 있을까?"

전산학에서 "무식하게 푼다(brute-force)"라는 말은 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미한다.

가능한 방법을 전부 만들어 보는 알고리즘들을 가리켜 흔히 완전 탐색(exhaustive search)이라고 부른다.

재귀 호출과 완전 탐색

재귀 호출

컴퓨터가 수행하는 많은 작업들은 대개 작은 조각들로 나누어 볼 수 있다.
이런 작업을 구현할 때 유용하게 사용되는 개념이 바로 재귀 함수(recursive function) 혹은 재귀 호출(recursion)이다.

재귀 함수란 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수를 가리킨다.

모든 재귀 함수는 '더이상 쪼개지지 않는' 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야 한다. 이때 쪼개지지 않는 가장 작은 작업들을 가리켜 재귀 호출의 기저 사례(base case)라고 한다.

base case를 선택할 때는 존재하는 모든 입력이 항상 base case의 답을 이용해 계산될 수 있도록 신경써야 한다.

int recursiveSum(int n) {
    if(n == 1) return 1; // 더이상 쪼개지지 않을 때
    return n + recursiveSum(n-1);

위 코드에서 만약 n이 1인 경우를 확인하는 것이 아니라 n이 2인지 확인하고, 2라면 3을 반환한다고 가정해 보자.

이렇게 구현하더라도 입력이 2 이상이라면 아무 문제 없이 답을 모두 계산할 수 있지만 1이 입력으로 들어오면 문제가 생긴다.

예제: 중첩 반복문 대체하기

n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘을 구현하자.
중첩 반복문으로 구현하면 다음과 같다.

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 << '\n';

위와 같은 중첩 for문은 골라야 할 원소의 수가 늘어날수록 코드가 길고 복잡해지는데다, 골라야 할 원소의 수가 입력에 따라 달라질 수 있는 경우에는 사용할 수 없다는 문제가 있다.

각 조각에서 하나의 원소를 고르자. 이렇게 원소를 고른 뒤, 남은 원소들을 고르는 작업을 자기 자신을 호출해 떠넘기는 재귀 함수를 작성하자.

남은 원소들을 고르는 '작업'을 다음과 같은 입력들의 집합으로 정의할 수 있다.

  • 원소들의 총 개수
  • 더 골라야 할 원소들의 개수
  • 지금까지 고른 원소들의 번호
#include <iostream>
#include <vector>

using namespace std;

void printElements(vector<int>& elementsToPrint) {
	const int ELEMENT_SIZE = elementsToPrint.size();
	for (int i = 0; i < ELEMENT_SIZE; ++i)
		cout << elementsToPrint[i] << ' ';
	cout << '\n';
}

void printCombination(const int TOTAL_ELEMENT_AMOUNT, vector<int>& elementsToPrint, int remainedElement) {
	if (remainedElement == 0) {
		printElements(elementsToPrint);
		return;
	}

	int starting = elementsToPrint.size() == 0 ? 0 : elementsToPrint.back() + 1;
	
	for (int i = starting; i < TOTAL_ELEMENT_AMOUNT; ++i) {
		elementsToPrint.push_back(i);
		printCombination(TOTAL_ELEMENT_AMOUNT, elementsToPrint, remainedElement - 1);
		elementsToPrint.pop_back();
	}
}

int main() {
	int n, m;
	cin >> n >> m;
	vector<int> elementsToPrint;
	printCombination(n, elementsToPrint, m);
	return 0;
}

이 코드는 텅 빈 답에서 시작해서 매 단계마다 하나의 원소를 추가하는 일을 반복하다가, 하나의 답을 만든 뒤에는 이전으로 돌아가 다른 원소를 추가하는 식으로 모든 답을 생성한다.

이 코드는 중첩 for문과 달리 우리가 n개의 원소 중에서 몇 개를 고르든지 사용할 수 있다.

예제: 보글 게임 (문제 ID: BOGGLE, 난이도: 하)

게임판에서의 현재 위치 (x, y) 그리고 단어 word가 주어질 때 해당 단어를 이 칸에서부터 시작해서 찾을 수 있는가?

hasWord(x, y, word) = 보글 게임판의 (x, y)에서 시작하는 단어 word의 존재 여부를 반환한다.

이 문제를 풀 때 가장 까다로운 점은 다음 글자가 될 수 있는 칸이 여러 개 있을 때 이 중 어느 글자를 선택해야 할지 미리 알 수 없다는 점이다.

간단한 방법은 완전 탐색을 이용해, 단어를 찾아낼 때까지 모든 인접한 칸을 하나씩 시도해 보면 된다.

문제의 분할

hasWord()가 하는 일을 가장 자연스럽게 조각내는 방법은 각 글자를 하나의 조각으로 만드는 것이다.
시작 위치에 쓰여 있는 글자가 단어의 첫 글자와 다르다면 곧장 false를 반환하고 종료한다.
그러고 나면 원래 단어 word에서 첫 글자를 뗀 단어 word[1..]을 격자에서 찾으면 된다.

기저 사례의 선택

  1. 위치 (x, y)에 있는 글자가 원하는 단어의 첫 글자가 아닌 경우 항상 실패
  2. (1번 경우에 해당되지 않을 경우) 원하는 단어가 한 글자인 경우 항상 성공

간결한 코드를 작성하는 유용한 팁으로, 입력이 잘못되거나 범위에서 벗어난 경우도 기저 사례로 택해서 맨 처음에 처리하는 것이다.
그러면 함수를 호출하는 시점에서 이런 오류를 검사할 필요가 없다.

나의 구현

#include <iostream>
#include <vector>

#define BOARD_SIZE	5

using namespace std;

typedef vector<vector<char>> GameBoard;

bool isStartFrom(GameBoard& gameBoard, int x, int y, string& word) {
	return gameBoard[x][y] == word[0];
}

string getRidofFirstCharacter(string& word) {
	return word.substr(1);
}

bool hasWord(GameBoard& gameBoard, int x, int y, string& word) {
	if (word.size() == 0) return true;
	if (x < 0 || y < 0) return false;
	if (!isStartFrom(gameBoard, x, y, word)) return false;
	string seperatedWord = getRidofFirstCharacter(word);
	for (int newX = x - 1; newX <= x + 1 && newX < BOARD_SIZE; ++newX) {
		for (int newY = y - 1; newY <= y + 1 && newY < BOARD_SIZE; ++newY) {
			if (newX == x && newY == y) continue;
			if (hasWord(gameBoard, newX, newY, seperatedWord))
				return true;
		}
	}
	return false;
}

bool findWord(GameBoard& gameBoard, string& word) {
	for (int x = 0; x < BOARD_SIZE; ++x) {
		for (int y = 0; y < BOARD_SIZE; ++y) {
			if (hasWord(gameBoard, x, y, word))
				return true;
		}
	}
	return false;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int C;
	cin >> C;
	while (C--) {
		GameBoard gameBoard(BOARD_SIZE, vector<char>(BOARD_SIZE));
		for (int i = 0; i < BOARD_SIZE; ++i)
			for (int j = 0; j < BOARD_SIZE; ++j)
				cin >> gameBoard[i][j];
		int N;
		cin >> N;
		while (N--) {
			string word;
			cin >> word;
			cout << word << " " << (findWord(gameBoard, word) ? "YES" : "NO");
			cout << '\n';
		}
	}
	return 0;
}

책의 구현

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 flase;
  // 기저 사례 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;
}
  1. 함수의 처음에서 시작 위치의 범위와 첫 글자 일치 여부를 확인하고 있기 때문에 for문 안에서 별도로 확인을 하지 않아도 된다.
  2. 다음 칸의 상대 좌표 목록을 함수 내에 직접 코딩해 넣은 것이 아니라 별도의 변수로 분리했다.

시간 복잡도 분석

최악인 경우는 답이 아예 존재하지 않는 경우인 때가 많다.
예를 들어 A로 가득찬 격자에서, 단어 AAAAAH를 찾는다고 하면, 찾을 가능성이 없지만, 완전 탐색은 그걸 모른다.

마지막 글자에 도달하기 전에는 주변의 모든 칸에 대해 재귀 호출을 하게 된다.
각 칸에는 최대 여덟 개의 이웃이 있고, 탐색은 단어의 길이 NN에 대해 N−1N-1단계 진행된다.
따라서 우리가 검사하는 후보의 수는 최대 8N−1=O(8N)8^{N-1}=O(8^N)이 되고, 이것이 이 알고리즘의 시간 복잡도가 된다.

완전 탐색 레시피

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

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

재귀 호출을 논의할 때 '문제'란 항상 수행해야 할 작업과 그 작업을 적용할 자료의 조합을 의미한다.
{1, 2, 3}을 정렬하는 문제와 {3, 2, 1}을 정렬하는 문제는 서로 다른 문제다.

보글 게임에서는 아홉 가지 정보를 알아야 한다.
1. 현재 위치 (x, y)에 단어의 첫 글자가 있는가?
2. 윗 칸 (y-1, x)에서 시작해서, 단어의 나머지 글자들을 찾을 수 있는가?
3. …

2번 이후의 항목은 원래 문제에서 한 조각을 떼어냈을 뿐, 형식이 같은 또 다른 문제를 푼 결과다.
문제를 구성하는 조각들 중 하나를 뺏기 때문에, 이 문제들은 원래 문제의 일부라고 할 수 있다.
이런 문제들을 원래 문제의 부분 문제라고 한다.

문제: 소풍 (문제 ID: PICNIC, 난이도: 하)

문제 보기
각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지을 수 있는 방법의 수를 계산하는 프로그램을 작성하자.

완전 탐색

가능한 조합의 수를 계산하는 문제를 푸는 가장 간단한 방법은 완전 탐색을 이용해 조합을 모두 만들어 보는 것이다.
재귀 호출을 이용해 문제를 해결하려면 우선 각 답을 만드는 과정을 여러 개의 조각으로 나누어야 한다.
전체 문제를 n2\frac{n}{2}개의 조각으로 나눠서 한 조각마다 두 학생을 짝지어 주는 것으로 하자.
이때 문제의 형태는 '아직 짝을 찾지 못한 학생들의 명단이 주어질 때 친구끼리 둘씩 짝짓는 경우의 수를 계산하라'가 된다.

중복으로 세는 문제

다음과 같은 경우가 있다.

  • 같은 학생 쌍을 두 번 짝지어 준다. 예를 들어 (0, 1)과 (1, 0)을 따로 센다.
  • 다른 순서로 학생들을 짝지어 주는 것을 서로 다른 경우로 세고 있다. 예를 들어 (0, 1) 후에 (2, 3)을 짝지어 주는 것과 (2, 3) 후에 (0, 1)을 짝지어주는 것을 다른 경우로 센다.

실질적으로 같은 답을 중복으로 세는 이런 상황은 경우의 수를 다룰 때 굉장히 흔하게 마주치게 된다.

좋은 방법은 항상 특정 형태를 갖는 답만을 세는 것이다.
흔히 사용하는 방법으로는 같은 답 중에서 사전순으로 가장 먼저 오는 답 하나만을 세는 것이 있다.
예를 들어 (2, 3), (0, 1) 말고 (0, 1), (2, 3)만 세는 것이다.

이 속성을 강제하기 위해서는 각 단계에서 남아 있는 학생들 중 가장 번호가 빠른 학생의 짝을 찾아 주도록 하면 된다.

  1. 가장 번호가 빠른 학생의 짝은 그보다 번호가 뒤일 수밖에 없기 때문에 (1, 0)과 같은 짝은 나올 수 없다.
  2. 항상 번호가 가장 빠른 학생부터 짝을 짓기 때문에 (2, 3), (0, 1)의 순서로 짝을 지어줄 일도 없다.

답의 수의 상한

모든 답을 생성해 가며 답의 수를 세는 재귀 호출 알고리즘은 답의 수에 정비례하는 시간이 걸린다.
실제로 프로그램을 짜기 전에 답의 수가 얼마나 될지 예측해 보고 모든 답을 만드는 데 시간이 얼마나 오래 걸릴지를 확인해야 된다.

이 문제에서 가장 많은 답을 가질 수 있는 입력은 열 명의 학생이 모두 서로 친구인 경우다.
이때 가장 번호가 빠른 학생이 선택할 수 있는 짝은 아홉 명이고, 그 다음 학생이 선택할 수 있는 짝은 일곱 명이다.

이와 같이 나가면 최종 답의 개수는 9×7×5×3×1=9459×7×5×3×1=945 가 된다.

구현

#include <iostream>
#include <vector>

using namespace std;

typedef vector<vector<bool>> Graph;
typedef vector<bool> Paired;

int n = 0;

int countPairCase(const Graph& graph, Paired paired) {
	int toPair = -1;
    	// 가장 빠른 순서의 학생을 구합니다.
	for (int i = 0; i < n; ++i)
		if (!paired[i]) {
			toPair = i;
			break;
		}
        // 더 이상 짝을 지어줄 학생이 없다면 종료합니다.
	if (toPair == -1) return 1;
	int caseCount = 0;
	for (int i = toPair + 1; i < n; ++i) {
    		// 두 학생이 친구인지, 이미 짝이 지어진 학생이 아닌지 검사합니다.
            	// 조건에 부합하면 짝을 지어주고 재귀 호출합니다.
		if (graph[toPair][i] && !paired[i]) {
			paired[toPair] = paired[i] = true;
			caseCount += countPairCase(graph, paired);
			paired[toPair] = paired[i] = false;
		}
	}
	return caseCount;
}

void linkNodeByKeyboard(Graph& graph) {
	int from, to;
	cin >> from >> to;
	graph[from][to] = 1;
	graph[to][from] = 1;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int C;
	cin >> C;
	while (C--) {
		int m;
		cin >> n >> m;
		Graph graph(n, vector<bool>(n));
		Paired paired = vector<bool>(n);
		for (int i = 0; i < m; ++i)
			linkNodeByKeyboard(graph);
		cout << countPairCase(graph, paired) << '\n';
	}
	return 0;
}

문제: 게임판 덮기 (문제 ID: BOARDCOVER, 난이도: 하)

문제 보기
게임판이 주어질 때 이를 L자 모양의 3칸짜리 블록으로 덮는 방법의 수를 계산하는 프로그램을 작성하자.

완전 탐색

이 문제도 경우의 수를 세는 것이니만큼, 게임판을 덮을 수 있는 모든 경우를 생성하는 완전 탐색을 이용해 해결할 수 있다.

  • 입력으로 주어진 게임판에서 흰 칸의 수가 3의 배수가 아닐 경우 무조건 답이 없으므로 따로 처리한다.
  • 이 외의 경우에는 흰 칸의 수를 3으로 나눠서 내려놓을 블록의 수 N을 얻은 뒤, 문제의 답을 생성하는 과정을 N조각으로 나눠 한 조각에서 한 블록을 내려놓도록 하자.
    재귀 함수는 주어진 게임판에 블록을 한 개 내려놓고 남은 흰 칸들을 재귀 호출을 이용해 덮도록 하자.

중복으로 세는 문제

같은 배치도 블록을 놓는 순서에 따라서 여러 번 셀 수 있다.
특정한 순서대로 답을 생성하도록 강제해야 한다.

재귀 호출의 각 단계마다 아직 빈 칸 중에서 가장 윗 줄, 그 중에서도 가장 왼쪽에 있는 칸을 덮도록 하자.
한 답을 한 가지 방법으로밖에 생성할 수 없으므로 중복으로 세지 않는다.

각 칸을 채우는 방법은 다음과 같다.
순서대로 (a), (b), (c), (d), (e)

재귀 호출 알고리즘은 첫 번째 빈 칸을 찾은 후 덮을 방법을 하나하나 시도한다.
이 방법이 달라질 때마다 서로 다른 배치가 되므로, 우리가 원하는 답은 남은 게임판을 재귀 호출에 넘겨서 얻은 경우의 수를 모두 더한 수가 된다.

답의 수의 상한

한 블록을 놓을 때마다 모두 네 가지의 선택지가 있다. 우리는 최대 ⌊503⌋=16\lfloor\frac{50}{3}\rfloor=16개의 블록을 놓기 때문에 가능한 답의 상한은 416=2324^{16}=2^{32}개가 된다.
이론 상으로는 굉장히 큰 수지만, 실제 작성해보면 시간 안에 답을 구할 수 있다는 확신을 얻을 수 있다.

구현

  • 한 칸을 덮는 네 가지 방법을 배열에 저장한다.
    이 배열은 네 가지 방법에서 새로 채워질 칸들의 상대 좌표의 목록을 저장한다.
  • coverBoardWithCenterAndType()은 해당 위치에 블록을 놓을 수 있는지 여부도 같이 판단한다.
    단, 이때 곧장 함수를 종료하면 안 된다. 만약 블록을 구성하는 세 칸 중에 기존의 블록과 겹치는 칸이 있다면, 함수를 곧장 종료하면 나중에 덮었던 블록을 치울 때, 두 번째 칸에 이미 있던 블록마저 치워 버리게 된다.
    따라서 그 자리에 1을 더함으로써 두 개의 블록이 겹쳐서 놓여 있다고 표시한다.
#include <iostream>
#include <vector>

#define FOR(i, from, n) for (int i=(from), LIMIT=(n); i<LIMIT; ++i)

#define BLOCK_SPACE	3
#define NONE		-1
#define TYPE_AMOUNT	4
#define COVER		1
#define ERASE		-1
#define OVERLAP		1

using namespace std;

typedef vector<vector<int>> GameBoard;

typedef struct Point { int x, y; } Point;

const int COVER_TYPE[TYPE_AMOUNT][BLOCK_SPACE][2] = {
	{{0,0},{1,0},{0,1}},	// (b)
	{{0,0},{0,1},{1,1}},	// (c)
	{{0,0},{1,0},{1,1}},	// (d)
	{{0,0},{1,0},{1,-1}},	// (e)
};

Point findFirstWhite(GameBoard& gameBoard) {
	FOR(y, 0, gameBoard.size()) {
		FOR(x, 0, gameBoard[0].size()) {
			if (!gameBoard[y][x])
				return { x, y };
		}
	}
	return { NONE, NONE };
}

bool hasNoWhite(Point& whitePoint) {
	return whitePoint.x == NONE || whitePoint.y == NONE;
}

bool coverBoardWithCenterAndType(GameBoard& gameBoard, Point center, int type) {
	bool canCoverBoard = true;
	FOR(i, 0, BLOCK_SPACE) {
		const int COVERED_Y = center.y + COVER_TYPE[type][i][0];
		const int COVERED_X = center.x + COVER_TYPE[type][i][1];
		if (COVERED_Y < 0 || COVERED_X < 0 ||
			COVERED_Y >= gameBoard.size() || COVERED_X >= gameBoard[0].size())
			canCoverBoard = false;
		else if ((gameBoard[COVERED_Y][COVERED_X] += COVER) > OVERLAP)
			canCoverBoard = false;
	}
	return canCoverBoard;
}

bool eraseBoardWithCenterAndType(GameBoard& gameBoard, Point center, int type) {
	bool canCoverBoard = false;
	FOR(i, 0, 3) {
		const int COVERED_Y = center.y + COVER_TYPE[type][i][0];
		const int COVERED_X = center.x + COVER_TYPE[type][i][1];
		if (COVERED_Y < 0 || COVERED_X < 0 ||
			COVERED_Y >= gameBoard.size() || COVERED_X >= gameBoard[0].size())
			canCoverBoard = false;
		else if ((gameBoard[COVERED_Y][COVERED_X] += ERASE) > OVERLAP)
			canCoverBoard = false;
	}
	return canCoverBoard;
}

int countCoverCapacity(GameBoard& gameBoard) {
	Point firstWhite = findFirstWhite(gameBoard);
	if (hasNoWhite(firstWhite)) return 1;

	int capacity = 0;
	FOR(type, 0, TYPE_AMOUNT) {
		if (coverBoardWithCenterAndType(gameBoard, firstWhite, type))
			capacity += countCoverCapacity(gameBoard);
		eraseBoardWithCenterAndType(gameBoard, firstWhite, type);
	}
	return capacity;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int C;
	cin >> C;
	while (C--) {
		int H, W;
		cin >> H >> W;
		GameBoard gameBoard = vector<vector<int>>(H, vector<int>(W));
		int whiteAmount = 0;
		FOR(y, 0, H) {
			FOR(x, 0, W) {
				char temp;
				cin >> temp;
				whiteAmount += temp == '.' ? 1 : 0;
				gameBoard[y][x] = temp == '#' ? 1 : 0;
			}
		}
		if (whiteAmount % BLOCK_SPACE == 0)
			cout << countCoverCapacity(gameBoard) << '\n';
		else
			cout << "0\n";
	}
	return 0;
}

최적화 문제

문제의 답이 하나가 아니라 여러 개이고, 그 중에서 어떤 기준에 따라 가장 '좋은' 답을 찾아 내는 문제들을 통칭해 최적화 문제(Optimization problem)라고 부른다.

최적화 문제의 예

  • n개의 사과 중에서 r개를 골라서 무게의 합을 최대화하는 문제
  • 가장 무거운 사과와 가장 가벼운 사과의 무게 차이를 최소화하는 문제

최적화 문제를 해결하는 방법

  • 동적 계획법
  • 조합 탐색
  • 최적화 문제를 결정 문제로 바꿔 해결하는 기법

가장 기초적인 것이 완전 탐색이다.
가능한 답을 모두 생성해 보고 그중 가장 좋은 것을 찾아내면 된다.

예제: 여행하는 외판원 문제

문제 보기
여러 개의 도시와 그 도시 간의 거리가 주어졌을 때, 각 도시를 정확히 한 번씩 방문하는 가장 짧은 경로를 찾자.

책과의 차이점

  1. 시작 지점으로 돌아가는 경로는 제외한다. (사이클이 아닌 단순 경로를 구해야 한다.)
  2. 시작 지점은 0뿐만 아니라 모든 점이 될 수 있다.

무식하게 풀 수 있을까?

완전 탐색으로 문제를 풀기 위해서는 첫번째로 시간 안에 답을 구할 수 있을지 확인해야 한다.
우리가 시작한 도시로 돌아오는 경로를 찾기 때문에, 경로의 시작점은 신경 쓰지 않고 무조건 0번 도시에서 출발한다고 가정해도 경로의 길이는 다르지 않다.
그러면 남은 도시들을 어떤 순서로 방문할지를 정하기만 하면 된다.

n-1개의 도시를 나열하는 방법은 모두 (n−1)!(n-1)!가지가 있다.
도시가 열 개라면 경로의 수는 9!=362,8809!=362,880개가 된다.
따라서 안전하게 완전 탐색을 사용해 문제를 해결할 수 있음을 알 수 있다.

알고스팟의 문제에서는 최대 8개의 도시가 있고, 시작한 도시로 돌아오지 않기 때문에
경로의 수는 8!=403208!=40320개가 된다.

재귀 호출을 통한 답안 생성

n개의 도시로 구성된 경로를 n개의 조각으로 나눠, 앞에서부터 도시를 하나씩 추가해 경로를 만들어 가기로 하자.

shortestPath(path)=path가 지금까지 만든 경로일 때, 나머지 도시들을 모두 방문하는 경로들 중 가장 짧은 것의 길이를 반환한다.

책의 구현

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

나의 구현

#include <iostream>
#include <vector>

#define FOR(i, from, n) for (int i=(from), LIMIT=(n); i<LIMIT; ++i)
#define min(first, second) first <= second ? first : second;

using namespace std;

typedef vector<vector<double>> Distance;
typedef vector<bool> Visit;

Visit visited;

// 책과의 차이점
// 방문할 정점과 남은 정점의 수를 인수로 받습니다
// (방문한 정점에서 인접한 정점으로 가는 길이 + 그 정점으로 가는 경로 중에서 가장 짧은 길이)를 더해서 그중 최소값을 구합니다.
double findFastestRouteDistance(Distance & distance, int toTraverse, int remains) {
	if (remains == 0)
		return 0.0;
	visited[toTraverse] = true;
	double minDistance = 1e20;
	FOR(i, 0, distance.size()) {
		if (visited[i]) continue;
		double temp = distance[toTraverse][i] + findFastestRouteDistance(distance, i, remains - 1);
		minDistance = min(minDistance, temp);
	}
	visited[toTraverse] = false;
	return minDistance;
}

void setDistanceForNByKeyboard(Distance & distance, int n) {
	FOR(i, 0, n)
		FOR(j, 0, n)
			cin >> distance[i][j];
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int C;
	cin >> C;
	while (C--) {
		int N;
		cin >> N;
		Distance distance = vector<vector<double>>(N, vector<double>(N));
		visited = vector<bool>(N);
		setDistanceForNByKeyboard(distance, N);
		
		double fastestDistance = 1e20;
		for (int startNode = 0; startNode < N; ++startNode)
			fastestDistance = min(fastestDistance, findFastestRouteDistance(distance, startNode, N - 1));
		
		cout << fixed;
		cout.precision(10);
		cout << fastestDistance << '\n';
	}
	return 0;
}

문제: 시계 맞추기 (문제 ID: CLOCKSYNC, 난이도: 중)

문제 보기
스위치를 눌러서 모든 시계를 12시로 맞출 수 있는 최소 회수를 구하자.

문제 변형하기

문제의 특성을 이용해 적절히 단순화하면 완전 탐색으로 해결할 수 있다.

예제 입출력 설명이 유도하는 방향과는 달리 스위치를 누르는 순서는 전혀 중요하지 않다.
두 스위치를 누르는 순서를 바꾼다고 해서 결과가 바뀌지는 않기 때문이다.
따라서 각 스위치를 몇 번 눌렀는지를 계산하면 된다.

완전 탐색 알고리즘을 사용하려면 스위치를 누르는 횟수의 모든 조합을 하나 하나 열거할 수 있어야 하는데, 각 스위치를 몇 번 누르는지는 상관없고 따라서 그 조합의 수는 무한하다.

시계는 12시간이 지나면 제 자리로 돌아온다는 점을 이용하면 유한하게 바꿀 수 있다.
어떤 스위치를 네 번 누르면 연결된 시계는 모두 12시간씩 앞으로 이동하니 하나도 누르지 않는 것과 다름없다.
따라서 어떤 스위치건 최대 세 번 이상 누르지 않아도 된다.
따라서 각 스위치를 누르는 횟수는 0에서 3 사이의 정수다.

열 개의 스위치가 있으니 전체 경우의 수는 410=1,048,5764^{10}=1,048,576이다.
따라서 완전 탐색으로 무난하게 풀 수 있다.

완전 탐색 구현하기

  • 만약 답을 구할 수 없을 경우 재귀 함수의 반환 값은 문제의 출력 값인 -1이 아니라 매우 큰 값이 된다.
    solve()는 재귀 호출하면서 가장 작은 출력 값을 찾게 되는데,
    -1 대신에 매우 큰 값을 반환하면 답이 없는 경우를 따로 확인하지 않아도 된다.
    마지막에 답을 출력할 때 답이 매우 크다면 -1을 대신 출력하면 된다.
  • 어떤 스위치가 어떤 시계에 연결되어 있는지 2차원 배열에 저장했다.
    i번째 스위치가 j번째 시계에 연결되어 있는 것은 linked[i][j]로 확인할 수 있다.
    문제에 적혀 있는 표현과 다르기 때문에 눈으로 확인하기 까다롭다는 단점이 있다.

책의 구현

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] = {
   //0123456789012345
   "xxx.............", 
   "...x...x.x.x....", 
   "....x.....x...xx", 
   "x...xxxx........", 
   "......xxx.x.x...",
   "x.x...........xx",
   "...x..........xx",
   "....xx.x......xx",
   ".xxxxx..........",
   "...xxx...x...x.."
};

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

//swtch번 스위치를 누른다.
void push(vector<int>& clocks, int swtch) 
{
   for(int i = 0; i< CLOCKS; i++)
      if(linked[swtch][i] == 'x')
      {
         clocks[i] += 3;
         if(clocks[i] == 15) clocks[i] = 3;
      }
}

//clocks: 현재 시계들의 상태
//swtch: 이번에 누를 스위치의 번호가 주어질 때, 남은 스위치들을 눌러서 clocks를 12시로 맞출 수 있는 최소 횟수를 반환한다.
//만약 불가능하다면 INF이상의 큰 수를 반환한다.
int solve(vector<int>& clocks, int swtch)
{
   //이 스위치를 0번 누르는 경우부터 세 번 누르는 경우까지를 모두 시도한다.
   if(swtch == SWITCHES)
      return areAligned(clocks) ? 0 : INF;
   
   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;
}

나의 구현

#include <iostream>
#include <vector>

#define CLOCK_AMOUNT		16
#define SWITCH_AMOUNT		10
#define TWELVE_CLOCK		3
#define TIME_TYPE_AMOUNT	4
#define INF					99999

#define FOR(i, from, n) for (int i=(from), LIMIT=(n); i<LIMIT; ++i)
#define min(first, second) first <= second ? first : second;

using namespace std;

typedef int Time[CLOCK_AMOUNT];
typedef const vector<vector<int>> Switch;

Switch SWITCH_WITH_LINKED_CLOCK = {
	{0, 1, 2},
	{3, 7, 9, 11},
	{4, 10, 14, 15},
	{0, 4, 5, 6, 7},
	{6, 7, 8, 10, 12},
	{0, 2, 14, 15},
	{3, 14, 15},
	{4, 5, 7, 14, 15},
	{1, 2, 3, 4, 5},
	{3, 4, 5, 9, 13}
};

void setTimeByKeyboard(Time& time) {
	FOR(i, 0, CLOCK_AMOUNT) {
		int temp;
		cin >> temp;
		time[i] = temp / 3 - 1;
	}
}

void clickSwitch(Time& clockTime, int switchIndex) {
	FOR(i, 0, SWITCH_WITH_LINKED_CLOCK[switchIndex].size()) {
		int clockIndex = SWITCH_WITH_LINKED_CLOCK[switchIndex][i];
		clockTime[clockIndex] += 1;
		clockTime[clockIndex] %= TIME_TYPE_AMOUNT;
	}
}

bool checkAllTwelveClock(Time& time) {
	FOR(clock, 0, CLOCK_AMOUNT)
		if (time[clock] != TWELVE_CLOCK) {
			return false;
		}
	return true;
}

int getMinCount(Time& clockTime, int switchIndex) {
	if (switchIndex == SWITCH_AMOUNT)
		return checkAllTwelveClock(clockTime) ? 0 : INF;

	int minCount = INF;
	FOR(clickCount, 0, TIME_TYPE_AMOUNT) {
		minCount = min(minCount, clickCount + getMinCount(clockTime, switchIndex + 1));
		clickSwitch(clockTime, switchIndex);
	}
	return minCount;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int C;
	cin >> C;
	while (C--) {
		Time time;
		setTimeByKeyboard(time);
		int minCount = getMinCount(time, 0);
		cout << (minCount == INF ? -1 : minCount) << '\n';
	}
	return 0;
}

구현하면서 실수를 했었다.
마지막에 답을 출력하는 구문의 삼항 연산자를 괄호로 감싸지 않아
계속해서 답이 0으로 출력됐다.

연산자 우선순위를 제대로 숙지하지 못 하면 괄호를 사용하는 편이 좋겠다.

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

주어진 원소로 만들 수 있는 모든 순열 만들기, 주어진 원소 중 R개를 골라낼 수 있는 방법 만들기 등은 다른 문제의 부분 문제로도 빈번히 출제된다.

그러니 입력의 크기에 따라 답의 개수가 어떻게 변하는지를 알고 구현하는 방법을 연습해 두면 좋다.

모든 순열 만들기

서로 다른 N개의 원소를 일렬로 줄 세운 것을 순열(permutation)이라고 부른다.
가능한 순열의 수는 N!N!이 되는데, N이 10을 넘어간다면 시간 안에 모든 순열을 생성하기 어려우므로 완전 탐색 말고 다른 방법을 생각해야 한다.
다른 방법으로는 9.11절(정수 이외의 입력에 대한 메모이제이션)의 기법들이 유용하다.

C++ 사용자는 표준 라이브러리인 STL에 포함된 next_permutation() 함수에서 모든 순열을 순서대로 생성하는 작업을 대신하게 할 수 있다.

모든 조합 만들기

서로 다른 N개의 원소 중에서 R개를 순서 없이 골라낸 것을 조합(combination)이라고 부른다.
이때 경우의 수는 이항 계수 (NR)\begin{pmatrix} N \\ R \end{pmatrix}로 정의된다.
(NR)=N!(N−R)!\begin{pmatrix} N \\ R \end{pmatrix}=\frac{N!}{(N-R)!}

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

n개의 질문에 대한 답이 예/아니오 중의 하나라고 할 때 존재할 수 있는 답의 모든 조합의 수는 2n2^n가지다.

각 조합을 하나의 n비트 정수로 표현한다고 생각하면 재귀 호출을 사용할 것 없이 1차원 for문 하나로 이 조합들을 간단하게 모두 시도할 수 있다. 비트 마스크

profile
Jun
이전 포스트

04~05 알고리즘 분석

다음 포스트

07 분할 정복

0개의 댓글