구종만님의 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략"을 기반으로 공부한 내용입니다.📚 목차
1. 도입
2. 재귀 호출과 완전 탐색
3. 소풍 (문제 ID: PICNIC, 난이도: 하)
4. 게임판 덮기 (문제 ID: BOARDCOVER, 난이도: 하)
5. 최적화 문제(Optimization problem)
6. 시계 맞추기 (문제 ID: CLOCKSYNC, 난이도: 중)
7. 많이 등장하는 완전 탐색 유형
1. 도입
완전 탐색
가능한 방법을 전부 만들어 보는 알고리즘
❓
열 명의 학생을 한 줄로 세우려고 한다.
서로 사이가 안 좋은 학생들이 있을 때 떨어뜨려서 세우는 방법이 있을까?
❕
열 명의 학생을 줄세우는 모든 경우를 만들어 보고 각 경우마다 사이 안 좋은 학생들이 붙어 있는지를 확인한다.
컴퓨터에게 이는 1초도 걸리지 않아 다 세어볼 수 있다.
따라서, 완전 탐색을 쓰면 '문제를 쉽게 푸는 방법'을 고민하지 않고 무식하게 문제를 풀어낼 수 있다.
2. 재귀 호출과 완전 탐색
재귀 함수
자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각으 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수
❓
자연수 n이 주어졌을 때 1부터 n까지의 합을 반환하는 함수 sum()이 있다.
이 함수를 어떻게 하면 재귀 호출을 이용하도록 바꿀 수 있을까?
// 코드 6.1 1부터 n까지의 합을 계산하는 반복 함수와 재귀 함수
// 필수 조건: n >= 1
// 결과: 1부터 n까지의 합을 반환한다.
int sum(int n) {
int ret = 0;
for (int i=1; i<=n; i++)
ret += i;
return ret;
}
// 필수 조건: n >= 1
// 결과: 1부터 n까지의 합을 반환한다.
int recursiveSum(int n) {
if (n == 1) return 1; // 더 이상 쪼개지지 않을 때
return n + recursiveSum(n - 1);
}❕
n개의 숫자의 합을 구하는 작업을 n개의 조각으로 쪼갠다.
하나의 조각은 더할 각 숫자가 되도록 한다.
조각 중에서 n만 따로 빼내면, 1부터 n-1까지의 조각들이 남는다.
자기 자신을 호출해 n-1까지의 합을 구한 뒤, 여기에 n을 더하면 답이 된다.
❗️
n개의 조각 중 n이 아닌 1을 빼냈을 경우, 2부터 n까지의 합이 남는다.
이는 1부터 n까지의 합을 구하는 원래 문제와는 다른 형태가 되므로 sum()을 호출하는 재귀함수를 사용할 수 없다.
📍
코드의 recursiveSum()함수의 첫 줄에 있는 if문을 보자.
n=1 이면 조각이 하나뿐이기 때문에 더 이상 처리할 작업이 없으므로 return 1을 반환한다.
따라서, 모든 재귀함수는 더 이상 쪼개지지 않는 최소한의 작업에 도달했을 때 답을 반환하는 조건문이 포함되어야 한다.
재귀 호출의 기저 사례
더 이상 쪼개지지 않는 가장 작은 작업들을 일컫는 말
예제
1️⃣ 중첩 반복문 대체하기
❓
0번부터 차례대로 번호 매겨진 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; 원소를 더 많이 고를 수록 for문의 중첩도 많아진다.
이 경우에 어떻게 할까?
❕
위의 코드에서 하는 작업을 4개의 조각으로 나눈다.
각 조각에서 하나의 원소를 고르고 남은 원소들을 고르는 작업은 재귀 함수를 통해 해결한다.
[ 남은 원소들을 고르는 작업 ]
아래와 같은 입력들의 집합으로 정의할 수 있다.
- 원소들의 총 개수
- 더 골라야 할 원소들의 개수
- 지금까지 고른 원소들의 번호
// 코드 6.2 n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘
void printPicked(vector<int>& picked);
// 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();
}
}
이와 같이 재귀 호출을 이용하면 특정 조건을 만족하는 조합을 모두 생성하는 코드를 쉽게 작성할 수 있다.
2️⃣ 보글 게임 (문제 ID:BOGGLE, 난이도:하)
보글(Boggle)
- 5x5 크기의 알파벳 격자를 가지고 하는 게임으로 상하좌우/대각선으로 인접한 칸들의 글자들을 이어서 단어를 찾아내는 것
문제 링크 : https://algospot.com/judge/problem/read/BOGGLE
📍
문제의 분할
각 글자를 하나의 조각으로 만든다.
함수 호출 시 단어의 시작 위치를 정해 주기 때문에, 문제의 조각들 중 첫 번째 글자에 해당하는 조각을 간단하게 해결할 수 있다.
- 시작 위치에 쓰여 있는 글자가 단어의 첫 글자와 다르면 false응 반환하고 종료
- 같다면, 원래 단어 word에서 첫 글자를 뗀 단어 word[1..]을 격자에서 찾음
- word[1..]의 시작위치 : word의 시작 위치 (y,x)와 인접한 여덟 칸 중 하나 - 여덟 경우를 모두 시도하며 해결
📍
기저 사례의 선택
탐색 없이 간단히 답을 낼 수 있는 경우 ➡️ 기저 사례로 선택하여 바로 return 시켜준다.
[ 기저 사례 ]
- 위치 (y,x)에 있는 글자가 원하는 단어의 첫 글자가 아닌 경우 항상 실패
- (1번 경우에 해다오디지 않을 경우) 원하는 단어가 한 글자인 경우 항상 성공
이 외에 입력이 잘못되거나 범위에서 벗어난 경우도 기저 사례로 택해 맨 처음 처리되도록 한다.
- 현재 위치가 보글 게임판을 벗어난 경우 항상 실패
- 첫 글자가 일치하지 않는 경우 항상 실패
📍
구현
// 코드 6.3 보글 게임판에서 단어를 찾는 재귀 호출 알고리즘
const int dx[8] = { -1, -1, -1, 1, 1, 1, 0, 0 };
const int dy[8] = { -1, 0, 1, -1, 0, 1, -1, 1 };
// 5*5의 보글 게임 판의 해당 위치에서 주어진 단어가 시작하는지를 반환
bool hasWord(int y, int x, const string& word) {
// 기저 사례 1: 시작 위치가 범위 밖이면 무조건 실패
if (y < 0 || y >= 5 || x < 0 || x >= 5) 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;
}📍
시간 복잡도 분석
모든 경우의 수를 세면 그것이 전탐색의 시간 복잡도가 된다.
위 문제의 경우, 답을 하나라도 찾으면 중간에 종료되므로 "최악의 경우"를 가정하고 계산하면 된다. (답이 없을 경우)
A로 가득 들어찬 곳에서 "AAAAAH"를 찾는다고 하면, 길이(N)만큼 전방향(8번)을 탐색하게 된다.
따라서 시간 복잡도는 가 된다.
완전 탐색 레시피
- 완전탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에 정확히 비례한다.
최대 크기 입력, 최악의 경우를 가정하고 시간 복잡도를 계산하라.
만약 시간 제한에 걸린다면 설계 패러다임을 적용해야 한다. - 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눠라.
각 선택은 답의 후보를 만드는 과정의 한 조각이 된다. - 그 중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성하라.
- 조각이 하나밖에 남지 않았거나, 하나도 남지 않은 경우 기저 사례로 선택해 처리하라.
이론적 배경 : 재귀 호출과 부분 문제
문제(problem)과 부분 문제(subproblem)의 차이를 알아야 한다.
문제'란 항상 수행해야 할 작업과 그 작업을 적용할 자료의 조합을 의미한다.
문제: 주어진 자연수 수열을 정렬하라.
문제: {16, 7, 9, 1, 31}을 정렬하라.
엄밀하게는 특정한 입력을 지정한 후자만을 문제의 정의라 할 수 있다.
보글 게임에서도 (y x), (y-1, x), (y-1, x-1), ...의 단어 적합성을 탐색하는 최소 9가지 정보가 필요하다.
하지만 모두 형식이 같은 또 다른 문제일뿐이다.
이런 문제들을 원래 문제의 부분 문제라 칭한다.
3. 소풍 ( 문제 ID: PICNIC, 난이도: 하 )
문제 : https://algospot.com/judge/problem/read/PICNIC
학생들의 짝을 지어주는 문제이다.
4. 풀이: 소풍
완전 탐색
- 재귀 호출을 이용한다면, 우선 각 답을 만드는 과정을 여러 개의 조각으로 나눈다.
- 전체 문제를 N/2개로 나누어, 한 조각마다 두 학생을 짝지어준다.
중복으로 세는 문제
// 코드 6.4 소풍 문제를 해결하는 (잘못된) 재귀 호출 코드
int n;
bool areFriends[10][10];
// taken[i] = i번째 학생이 짝을 이미 찾았으면 true, 아니면 false
int countPairings(bool taken[10]) {
// 기저 사례: 모든 학생이 짝을 찾았으면 한 가지 방법을 찾았으니 종료한다.
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 = i+1; 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;
}위 코드에는 두 가지 문제점이 존재한다.
- 같은 학생 쌍을 두 번 짝지어 준다.
예) (0,1)과 (1,0)을 따로 세고 있다. - 다른 순서로 학생들을 짝지어 주는 것을 서로 다른 경우로 세고 있다.
예) (0,1) 후에 (2,3)을 짝지어 주는 것과 (2,3) 후에 (0,1)을 짝지어주는 것은 완전히 같은 방법인데 다른 경우로 세고 있다.
❕
해결하기 위한 방법
- 같은 답 중에서 사전순으로 가장 먼저 오는 답 하나만을 센다.
예) (2,3), (0,1)이나 (1,0), (2,3)은 세지 않지만 (0,1),(2,3)은 센다.
📍
구현 방법
-
각 단계에서 남아 있는 학생들 중 가장 번호가 빠른 학생의 짝을 찾아준다.
-
가장 번호가 빠른 학생의 짝은 그보다 번호가 뒤일 수밖에 없기 때문에 (1,0)과 같은 짝은 나올 수 없다.
또한, 항상 번호가 가장 빠른 학생부터 짝을 짓기 때문에 (2,3), (0,1)의 순서로 짝을 지어줄 일도 없다.
// 코드 6.4 소풍 문제를 해결하는 재귀 호출 코드
int n;
bool areFriends[10][10];
// taken[i] = i번째 학생이 짝을 이미 찾았으면 true, 아니면 false
int countPairings(bool taken[10]) {
// 남은 학생들 중 가장 번호가 빠른 학생을 찾는다.
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;
}답의 수의 상한
모든 답을 생성하며 답의 수를 세는 재귀 호출 알고리즘은 답의 수에 정비례하는 시간이 걸린다.
이 문제에서 가장 많은 답을 가질 수 있는 입력은 열 명의 학생이 모두 서로 친구인 경우이다.
이때 가장 번호가 빠른 학생이 선택할 수 있는 짝은 9명이고, 그 다음 학생이 선택할 수 있는 짝은 일곱 명이다.
따라서, 최종 답의 개수는 97531 = 945 가 된다.
5. 게임판 덮기 ( 문제 ID:BOARDCOVER, 난이도: 히 )
문제 : https://algospot.com/judge/problem/read/BOARDCOVER
게임판이 주어질 때 이를 덮는 방법의 수를 계산하는 문제이다.
6. 풀이: 게임판 덮기
완전탐색을 떠올려볼 수 있는 문제다.
'ㄴ'자의 중심부분을 기준으로 빙빙 돌리면, 하나의 좌표에서 최대 4가지 경우가 탐색 가능하다.
우선 입력에서 힁 칸의 수가 3의 배수가 아니라면 무조건 답이 없으니 예외 처리하고 시작해야 한다.
중복으로 세는 문제
블록을 하나 놓고 남은 흰 칸들을 재귀 호출로 덮는 방식은 블록을 놓는 순서에 따라 여러 번 세게 된다.
가장 간편한 방법은 가장 윗줄, 가장 왼쪽의 칸을 최우선으로 덮도록 세는 것이다. (순서 강제)
답의 수의 상한
문제 조건에 의해 흰 칸은 최대 50개가 있을 수 있다.
놓을 수 있는 블록은 50/3의 몫인 16이 최대치
블록을 놓을 때 4가지 경우의 방향이 존재하므로 4^16 = 2^32 개가 상한이다.
하지만 실제로 가능한 경우가 그리 많지 않다. (흰 칸이 48개여도 답은 1,514에 그친다.)
상한이 그리 크지 않으므로 전탐색으로 충분히 해결할 수 있는 문제다.
📍
구현방법
- y, x delta 값을 coverType에 저장한다.
- set() 함수로 delta에 따라 블럭을 놓고 치우는 역할을 수행한다. 동시에 블록을 놓을 수 있는지 여부도 판단한다.
- set()에서 블록을 놓다가 유효하지 않은 칸이 나왔다고 곧장 종료하면, 기존에 놓여있던 블록까지 치워버리게 될 수 있어서 '일단 1을 더해놓고' 나중에 제거하고 있다.
// 코드 6.6 게임판 덮기 문제를 해결하는 재귀 호출 알고리즘
// 주어진 칸을 덮을 수 있는 네 가지 방법
// 블록을 구성하는 세 칸의 상대적 위치 (dy, dx)의 목록
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[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[y][x]를 type 형태로 덮을 수 있으면 재귀 호출한다.
if (set(board, y, x, type, 1))
ret += cover(board);
// 덮었던 블록을 치운다.
set(board, y, x, type, -1);
}
return ret;
}7. 최적화 문제
최적화 문제 (Optimization problem)
문제의 답이 하나가 아니라 여러 개이고, 그 중에서 어떤 기준에 따라 가장 좋은 답을 찾아내는 문제들을 통칭하는 말
-
최적화 문제가 아닌 경우
n개의 원소 중에서 r개를 순서 없이 골라내는 방법의 수를 계산하는 경우 -
최적화 문제인 경우
n개의 사과 중에서 r개를 골라서 무게의 합을 최대화하는 문제
가장 무거운 사과와 가장 가벼운 사과의 무게 차이를 최소화하는 문제
최적화 문제는 인공지능, 생명공학, 자동차 디자인에 이르기까지 컴퓨터가 하는 많은 작업들을 표현한다.
완전 탐색은 최적화 문제를 풀기 위한 가장 직관적인 방법이다.
예제: 여행하는 외판원 문제
문제: https://www.acmicpc.net/problem/2098
무식하게 풀 수 있을까?
완전 탐색으로 문제를 풀기 위한 첫 번째 단계는 시간 안에 답을 구할 수 있을지 확인 하는 것이다.
도시를 하나씩 방문하면 (n-1)! 가지의 경우가 존재하겠지만, 여기선 n=10으로 고정했다고 가정하면 9! = 362,880 으로 완전 탐색으로도 1초안에 가볍게 처리가능하다.
재귀 호출을 통한 답안 생성
방문 여부 배열 visited와 경로 path, 경로 길이 currentLength를 이용하여 n개의 도시로 구성된 경로를 n개의 조각으로 나누었다.
// 코드 6.7 여행하는 외판원 문제를 해결하는 재귀 호출 알고리즘
int n; // 도시의 수
double dist[10][10]; // 두 도시 간의 거리를 저장하는 배열
// 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;
}8. 시계 맞추기 (문제 ID: CLOCKSYNC, 난이도: 중)
문제 : https://algospot.com/judge/problem/read/CLOCKSYNC
시계들이 현재 가리키는 시간들이 주어졌을 때 모든 시게를 12시로 돌리기 위해 최소한 스위치를 몇 번이나 눌러야 할지 계산하는 문제이다.
9. 풀이: 시계 맞추기
문제 변형하기
예제 입출력 설명이 유도하는 방향과는 달리 스위치를 누르는 순서는 전혀 중요하지 않다.
우리가 계산해야 할 것은 각 스위치를 몇 번이나 누를 것인지이다.
이렇게 문제를 바꾼다 해도, 완전 탐색을 곧장 적용할 수는 없다.
❕
시계가 12시간이 지나면 제 자리로 돌아온다는 점을 이용하여 무한한 조랍의 수를 유한하게 바꾼다.
어떤 스위치를 네 번 누르면 연결된 시계는 모두 12시간씩 앞으로 이동하므로 하나도 누르지 않은 것과 똑같다.
따라서 어떤 스위치건 간에 최대 세 번 이상 누를 일이 없다는 것을 알 수 있다.
따라서 각 스위치를 누르는 횟수는 0에서 3사이의 정수이다.
열 개의 스위치가 있으니 전체 경우의 수는 개가 된다.
따라서 완전탐색으로 무난하게 풀 수 있다.
완전 탐색 구현하기
// 코드 6.8 시계 맞추기 문제를 해결하는 완전 탐색 알고리즘
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.............", // 0번 스위치와 연결된 시계들
"...x...x.x.x....", // 1번 스위치와 연결된 시계들
"....x.....x...xx", // 2번 스위치와 연결된 시계들
"x...xxxx........", // 3번 스위치와 연결된 시계들
"......xxx.x.x...", // 4번 스위치와 연결된 시계들
"x.x...........xx", // 5번 스위치와 연결된 시계들
"...x..........xx", // 6번 스위치와 연결된 시계들
"....xx.x......xx", // 7번 스위치와 연결된 시계들
".xxxxx..........", // 8번 스위치와 연결된 시계들
"...xxx...x...x.." // 9번 스위치와 연결된 시계들
};
// 모든 시계가 12시를 가리키고 있는지 확인한다.
bool areAligned(const vector<int>& clocks) {
for (int clock = 0; clock < CLOCKS; ++clock)
if (clocks[clock] != 12) return false;
return true;
}
// 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;
}10. 많이 등장하는 완전 탐색 유형
모든 순열 만들기
순열 (permutation)
서로 다른 N개의 원소를 일렬로 줄 세운 것
모든 조합 만들기
조합 (combination)
서로 다른 N개의 원소 중에서 R개를 순서 없이 골라낸 것
가지 경우의 수 만들기
n개의 질문에 대한 답이 예/아니오 중의 하나라면, 존재 가능한 모든 조합의 수는 가지이다.
각 조합을 하나의 n비트 정수로 표현한다고 하면 재귀 호출을 사용할 것 없이 1차원 for문 하나로 이 조합들을 간단하게 모두 시도할 수 있다.
