각 조각에서 하나의 원소를 고른다. 원소를 고른 뒤, 남은 원소들을 고르는 작업을 재귀함수로 구현한다.
남은 원소를 고르는 작업을 다음과 같은 입력들의 집합으로 정의할 수 있다.
원소들의 총 개수
더 골라야 할 원소들의 개수
지금까지 고른 원소들의 번호
//n은 전체 원소의 수
//picked는 지금까지 고른 원소들의 번호
//toPick은 더 고를 원소의 수
void pick(int n, vector<int>& picked, int toPick){
//base case:더 고를 원소가 없을 때 고른 원소들을 출력한다.
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();
}
}
재귀 호출을 이용하면 특정 조건을 만족하는 조합을 모두 생성하는 코드를 쉽게 작성할 수 있다.
때문에 재귀 호출은 완전 탐색을 구현할 때 아주 유용한 도구이다.
완전탐색 레시피
1. 완전탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에 정확히 비례한다.
최대 크기의 입력을 가정했을 때 답의 개수를 계산하고 이들을 모두 제한 시간 안에 생성할 수 있을지를 가늠한다.
만약 시간안에 계산할 수 없다면 다른 설계 패러다임을 적용해야한다.
2. 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눈다. 각 선택은 답의 후보를 만드는 과정의 한 조각이 된다.
3.그중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀호출을 통해 완성한다.
4. 조각이 하나밖에 남지 않은 경우, 혹은 하나도 남지 않은 경우에는 답을 생성했으므로, 이것을 기저 사례로 선택해 처리한다.
이론적 배경: 재귀 호출과 부분 문제
문제와 부분 문제의 정의를 알아야한다.
이 정의는 동적계획법, 분할정복 같은 디자인 패러다임을 설명하는데 사용된다.
쉽게 생각하는 직관과는 다르다.
문제를 여러 조각으로 나누었을 때 조각들을 부분문제라고 할 수 있다.
나의 정리
부분으로 조각내고 각 케이스 별로 만들어서 케이스의 끝인 경우 문제의 정답인지 확인 후 정답인 경우 반환하면 된다.
그 전에 나오면 안되는 예외의 경우 함수 내에서 더이상 진행되지 않도록 처리.
6.7 최적화 문제 (Optimization problem)
문제의 답이 하나가 아니라 여러 개이고, 그 중에서 어떤 기준에 따라 가장 '좋은' 답을 찾아내는 문제를 최적화 문제라고 한다.
n개의 사과 주에서 r개를 골라서 무게의 합을 최대화하는 문제, 가장 무거운 사과와 가장 가벼운 사과의 무게 차이를 최소화 하는 문제 등은 최적화 문제가 된다.
사과를 고르는 방법은 여러 가지인데, 이 중 특정 기준에의해 가장 좋은 답을 고르는 문제이기 때문이다.
최적화 문제는 우리 생활과 밀접하다. 세상에는 효율적인, 최대의, 최소의 값을 찾아야하는 경우가 많다.
때문에 최적화 문제는 중요한 주제 중 하나이다.
예제: 여행하는 외판원 문제
어떤 나라에 n(2≤n≤10)개의 큰 도시가 있다고 하자.
한 영업 사원이 한 도시에서 출발해 다른 도시들을 전부 한 번씩 방문한 뒤 시작 도시로 돌아오려고 한다.
문제를 간단히 하기 위해, 각 도시는 모두 직선 도로로 연결되어 있다고 한다.
이 때 이동 거리는 도시 방문 순서에 따라 달라진다.
무식하게 풀 수 있을까?
완전 탐색으로 문제를 풀기 위한 첫 번째 단계는 시간 안에 답을 구할 수 잇는지 확인하는 것이다.
시작한 도시로 돌아오는 경로를 찾기에 경로의 시작점은 신경쓰지 않아도 된다.
시작 도시를 정하고 나머지 도시의 경우의 수는 (n-1)!가 된다.
도시 10개의 경우 9!은 362,880개가 되어 1초안에 처리할 수 있다.
재귀 호출을 통한 답안 생성
int n;//도시의 수
double ist[MAX][MAX];//두 도시 간의 거리를 저장하는 배열
//path는 지금까지 만든 경로
//vidited는 각 도시의 방문여부
//currentLength는 지금까지 만든 경로의 길이
//나머지 도시들을 모두 방문하는 경로들 중 가장 짧은 것의 길이를 반환한다.
double shortestPath(vector<int>& ath, vector<bool>& visited, double currentLength)
{
//base case - 모든 도시를 방문한 경우 시작 도시로 돌아가고 종료한다.
if(path.size() == n)
return currentLength + dist[path[0]][path.back()];
double ret = INF;
//다음 방문할 도시를 전부 시도해 본다.
for(int next = 0; next < n; ++next)
{
//방문할 곳이 이미 방문한 곳이라면 통과
if(visited[next]) continu;
//방문한 곳이 아니라면 방문
int here = 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;
}
6.8 문제: 시계 맞추기 (문제 ID: CLOCKSYNC, 난이도: 중)
그림과 같이 4X4개의 격자 형태로 배치된 열여섯 개의 시계가 있다.
이 시계들은 12, 3, 6, 9시를 가리키고 있다.
이 시계들이 모두 12시를 가리키도록 바꾸려한다.
시계의 시간을 조작하는 방법은 열개의 스위치들을 조작하는 것으로, 각 스위치는 누를 때 마다, 해당 스위치와 연결된 시계들의 시간은 3시간 후로 움직인다.
스위치 번호
연결된 시계
스위치 번호
연결된 시계
0
0, 1, 2
5
0, 2, 14, 15
1
3, 7, 9, 11
6
3, 14, 15
2
4, 10, 14, 15
7
4, 5, 7, 14, 5
3
0, 4, 5, 6, 7
8
1, 2, 3, 4, 5
4
6, 7, 8, 10, 12
9
3, 4, 5, 9, 13
시계 순서는 위에서 아래로, 왼쪽에서 오른쪽으로 매겨진다.
모든 시계를 12시로 돌리기 위해 최소한 스위치를 몇 번 눌러야 할지 구하시오.
시간 및 메모리 제한
프로그램은 10초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야한다.
입력
첫번째 줄에 테스트 케이스 개수 C가 주어진다. (C≤30)
각 테스트 케이스는 한줄에 16개의 정수로 주어진다. 각 정수는 시계를 의미하며 정수의 값은 3, 6, 9, 12중 하나로 표현한다.
출력
각 케이스당 정수 하나를 한줄에 출력한다. 정수 값은 스위치 누르는 횟수이다.
시계들을 12시로 만드는 것이 불가능 하다면, -1을 출력한다.
예제 입력
2
12 6 6 6 6 612 12 12 12 12 12 12 12 12 12
12 9 3 12 6 6 9 3 12 9 12 9 12 12 6 6
예제 출력
2
9
6.9 풀이: 시계 맞추기
문제 변형하기
문제 그대로 풀려고 하면 복잡하다.
문제의 특성을 이용해 단순화하면 완전탐색으로 해결할 수 있다.
이 문제에서 깨달아야 할 것은 스위치를 누르는 순서는 중요하지 않다는 것이다.
순서를 바꾼다고 결과가 달라지지 않는다.
구해야할 것은 각 스위치를 몇번 누를 것인가 이다.
이렇게 문제를 바꿔도 완전탐색으로 구할 수 없다.
완전 탐색 알고리즘을 사용하려면 스위치를 누르는 횟수의 모든 조합을 하나하나 열거할 수 있어야 하는데,
각 스위치를 몇번 누르는 지는 상관이 없기에 조합의 수가 무한하기 때문이다.
시계는 12시간이 지나면 제자리로 돌아온다는 점을 이용하면 무한한 조합의 수를 유한하게 바꿀 수 있다.
어떤 스위치를 네번 누르면 연결된 시계는 모두 12시간 앖으로 이동하니 하나도 누르지 않은 것과 같다.
따라서 어떤 스위치건 3번 이상 누를 일이 없다.
따라서 각 스위치를 누르는 횟수는 0에서 3사이의 정수이다.
10개의 스위치가 있으니 전체 경우의 수는 4^10이 된다.
완전탐색 구현하기
const int INF = 9999, SWITCHES = 10, CLOCKS = 16;
//linked[i][j]가 x인 경우는 i번 스위치와 j번 시계가 연결되어 있다는 의미
//linked[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 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 areAlingned(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()가 4번 호출되어 초기상태와 같아진다.
return ret;
}
6.10 많이 등장하는 완전 탐색 유형
모든 순열 만들기
서로 다른 N개의 원소를 일렬로 줄 세운 것을 순열이라한다.
자주 볼 수 있는 유형이다.
가능한 순열의 수는 N!인데, N이 10을 넘어간다면 시간 안에 모든 순열을 생성하기 어려워져, 완전 탐색이 아닌 다른 방법을 찾아야한다.
C++ 사용시 유리하다.
STL에 포함된 next_permutation()함수에서 모든 순열을 순서대로 생성하는 작업을 해준다.
다른 언어에서는 직접 순열을 만들어야 한다.
모든 조합 만들기
서로 다른 N개의 원소 중에서 R개를 순서 없이 골라낸 것을 조합이라고 한다.
nCr의 경우의 수가 나온다.
위에서 6.2의 pick()함수처럼 구현하면 된다.
2ⁿ가지 경우의 수 만들기
n개의 질문에 대한 답이 예/아니오 중의 하나라고 할 때 존재할 수 있는 답의 경우의 수는 2ⁿ가지이다.
흔한 문제이며, 각 조합을 하나의 n비트 정수로 표현한다고 생각하면 1차원 for문으로 모두 시도할 수 있다.
이것은 뒤에서 기술한다.
복습
완전 탐색 레시피
1. 완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에 정확히 비례한다.
2. 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눈다.
3. 그 중 하나의 조각을 선택해 답의 일부를 만들고 나머지 답을 재귀 호출을 통해 완성한다.
4. 조각이 하나밖에 남지 않은 경우, 혹은 하나도 남지 않은 경우 답을 생성 한 것이니, 기저 사례로 처리한다.
즉, 답을 만드는 과정을 나누고 재귀로 답의 일부를 만들고 나머지를 재귀 호출로 완성한다.
