1. 완전 탐색이란?
컴퓨터의 빠른 계산 능력을 이용하여 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미한다.
'무식하게 푼다'라는 의미인 Brute-Force (브루트 포스)라고도 부른다.
이름이 거창하게 지어져 있지만 사실 완전 탐색 자체로는 알고리즘이라고 부르긴 그렇고, 문제 푸는'방법'이라고 이해하면 편할 것 같다. 알고리즘을 모르는 사람이 프로그래밍 문제를 푼다면, 당연히 가능한 모든 경우들을 다 구해서 그중에 만족하는 답을 찾아낼 것이고 이 과정 자체가 완전 탐색이다. 대신에 이 방식은 절대 답을 못 구하는 경우는 없으므로 나름 강력한 방법이다.
예를 한번 들어보자.
"10개의 정수 원소로 이루어진 수열이 있다. 이 수열에서 두 원소를 선택해서 구한 합의 최댓값을 구하시오. "
이 문제에서 완전 탐색을 이용하는 방식은, 10개의 원소에서 두 원소를 고르는 모든 경우를 다 고려하는 것이다.
즉, 10C2 가지의 경우를 모두 구한 후 나온 합 중 최댓값을 출력하게 되는 것이다.
이 예시에서는 10C2 = 45이므로 경우가 45가지밖에 나오지 않아 충분히 빠르게 해결이 가능하다.
하지만 만약 원소의 개수가 10만이라면 경우의 수가 50억 가지나 되므로 제한된 시간 내에 경우들을 모두 구할 수 없게 된다.
(이를 해결하기 위해서는 가장 큰 원소와 두 번째로 큰 원소를 찾아 더하면 답이 된다.)
이처럼 완전 탐색은 답으로 가능한 경우의 수가 많은 경우에는 이용하기가 어려우므로 완전 탐색을 이용할 수 있는 경우인지 잘 파악하는 게 중요하다.
2. 완전 탐색 기법
완전 탐색 자체가 알고리즘은 아니기 때문에 완전 탐색 방법을 이용하기 위해서 여러 알고리즘 기법이 이용된다. 주로 이용되는 기법들은 다음과 같다.
- 단순 Brute-Force
- 비트마스크(Bitmask)
- 재귀 함수
- 순열 (Permutation)
- BFS / DFS
기본적으로 완전 탐색은 N의 크기가 작을 때 이용이 되기 때문에 보통 시간 복잡도가 지수승이나, 팩토리얼 꼴로 나올 때 많이 이용된다.
이 기법들에 대한 자세한 설명은 하지 않고, 어떻게 이용되는지만 언급하겠다.
1. 단순 Brute-Force
어느 기법을 사용하지 않고 단순히 for문과 if문 등으로 모든 case들을 만들어 답을 구하는 방법이다. 이는 아주 기초적인 문제에서 주로 이용되거나, 전체 풀이의 일부분으로 이용하며, 따라서 당연히 대회나 코테에서는 이 방법만을 이용한 문제는 거의 나오지 않는다.
2. 비트마스크(Bitmask)
2진수를 이용하는 컴퓨터의 연산을 이용하는 방식이다. 완전 탐색에서 비트마스크는 문제에서 나올 수 있는 모든 경우의 수가 각각의 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우에 유용하게 사용이 가능하다.
간단한 예시로 원소가 5개인 집합의 모든 부분집합을 구하는 경우를 생각해보자.
어떤 집합의 부분집합은 집합의 각 원소가 해당 부분집합에 포함되거나, 포함되지 않는 두 가지 경우만 존재한다.
따라서 5자리 이진수 (0 ~ 31)를 이용하여 각 원소의 포함 여부를 체크할 수 있다.
위 그림과 같이 0부터 31까지의 각 숫자들이 하나의 부분집합에 일대일로 대응이 된다.
3. 재귀 함수
재귀 함수를 통해서 문제를 만족하는 경우들을 만들어가는 방식이다.
위에서 언급한 부분집합 문제를 예로 들면, 만들고자 하는 부분집합을 S'라고 할 때, S' = { } 부터 시작해서 각 원소에 대해서 해당 원소가 포함이 되면 S'에 넣고 재귀 함수를 돌려주고, 포함이 되지 않으면 S'를 그대로 재귀 함수에 넣어주는 방식이다.
비트마스크와 마찬가지로 주로 각 원소가 포함되거나, 포함되지 않는 두 가지 선택을 가질 때 이용된다.
4. 순열
완전 탐색의 대표적인 유형이다. 서로 다른 N개를 일렬로 나열하는 순열의 경우의 수는 N! 이므로 완전 탐색을 이용하기 위해서는 N이 한자리 수 정도는 되어야 한다.
순열에 원소를 하나씩 채워가는 방식이며, 재귀 함수를 이용하거나 C++에서는 next_permutation이라는 아주 유용한 함수를 제공하고 있다.
5. BFS / DFS
약간의 난이도가 있는 문제로 완전 탐색 + BFS/DFS 문제가 많이 나온다. 대표적인 유형으로 길 찾기 문제가 있다. 단순히 길을 찾는 문제라면 BFS/DFS만 이용해도 충분하지만, 주어진 도로에 장애물을 설치하거나, 목적지를 추가하는 등의 추가적인 작업이 필요한 경우에 이를 완전 탐색으로 해결하고 나서, BFS/DFS를 이용하는 방식이다.
3. 완전 탐색 실전 이용 예시
보통 완전 탐색 문제는 난이도가 쉬운 편이기 때문에 초급자들도 큰 어려움을 겪지 않는다. 하지만 약간의 난이도가 있는 문제에서 오히려 알고리즘 공부를 어느 정도 한 사람들이 "이게 완전 탐색이라고?" 하는 반응을 보이는 경우가 꽤나 있다. 완전 탐색 유형이라고 미처 생각하지 못하는 경우가 많기 때문이다. 특히나 코드포스 같은 아이디어를 많이 요구하는 CP에서 자주 발생한다. 그래서 필자의 경험 상, 문제를 봤을 때 완전 탐색이지 않을까?라는 생각을 한번 정도는 해볼 만한 경우들을 생각해봤다.
(지금까지의 적은 경험 하에서는 코드포스 등의 CP 이외에는 크게 유용할 것 같지는 않다... 그래도 혹시 모르니..)
1. 입력으로 주어지는 데이터(N)의 크기가 매우 작다.
보통 프로그래밍 문제들을 풀게 되면 N = 10만, 20만 같은 크기를 주는 경우가 많다. 하지만 대부분의 경우 완전 탐색 문제는 N의 크기가 매우 작다. 위에서 언급한 부분집합 문제나, 순열, 조합 같은 문제들은 완전 탐색으로 푼다면 기본적으로 시간 복잡도가 O(2^N)이나, O(N!) 이므로 당연히 N의 크기가 매우 작아야 한다.
2. 답의 범위가 작고, 임의의 답을 하나 선택했을 때 문제 조건을 만족하는지 역추적할 수 있다.
1번과 연관되는 내용일 수도 있다. N의 크기가 작으면 답의 범위 또한 작을 확률이 높기 때문이다. 하지만, 2번의 경우는 N이 작다고 하더라도 완전 탐색인 것을 떠올리기가 어려운 경우가 많다.
이 문제가 아주 적절한 예시가 될 것 같다.
codeforces.com/problemset/problem/1395/C
Problem - 1395C - Codeforces
codeforces.com
이 문제는 N, M이 최대 200이고, N개의 원소를 갖는 수열 a와 M개의 원소를 갖는 수열 b가 주어진다.
이때, 수열 Cn를 다음과 같이 정의한다. Ci = ai & bj (1 ≤ i ≤ n , 1 ≤ j ≤ m , & : AND 연산)
그리고, 구하고자 하는 답은 C1 | C2 | ... | Cn 의 최솟값을 구하는 것이다. ( | : OR 연산)
처음에 N과 M의 범위가 200 이하인 것을 보고 범위가 작으니 모든 경우를 만드는 완전 탐색을 생각할 수도 있다.
따라서 가능한 Cn을 모두 만들려고 보게 되면 각각의 ai마다 m개의 수열 b의 원소가 대응되므로 경우의 수가 N^M개가 나오게 된다. 즉, 200^200승이므로 당연히 시간 내에 돌아가지 못한다.
여기까지는 대부분 생각할 수 있는 부분이고, 이후부터는 어떤 알고리즘을 사용할지 고민하게 된다.
하지만 문제에서 요구하는 답을 보면 C1 | C2 | .... | Cn 이고, 수열 Cn의 각 원소의 범위는 2^9 = 512보다 작다.
Ci = ai & bj 이고, a와 b의 범위가 모두 2^9보다 작기 때문이다.
결국 답이 되는 C1 | C2 | .... | Cn 의 범위 또한 512보다 작게 나온다.
따라서 이를 이용하여 답을 미리 정해놓고, 문제 조건을 만족하는지 체크를 해볼 수 있다.
C1 | C2 | .... | Cn의 최솟값을 구해야 하기 때문에 0부터 511까지 1씩 키워가면서 답이라고 가정한다.
현재 값을 K라고 할 때, ai에 대해서 b의 모든 원소들 중에서 K | (ai & bj) == K 를 만족하는 j가 존재한다면 ai에는 bj를 대응시켜주면 된다. (C1 | C2 | .... | Cn) | Ci = (C1 | C2 | ... | Cn) 을 항상 만족하기 때문이다.
그러므로 모든 ai가 b에 대응이 가능하다면, K가 답이 될 수 있는 것이다.
소스 코드)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
int a[201];
int b[201];
int main(void) {
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= m; i++) cin >> b[i];
for (int i = 0; i < 512; i++) {
int c = 0;
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= m; k++) {
if ((i | (a[j] & b[k])) == i) {
c++;
break;
}
}
}
if (c == n) {
cout << i;
break;
}
}
}
|
이렇게 답의 범위가 아주 제한적인 경우에는, 임의로 답을 고정시켜놓고 주어진 조건들이 답에 적합한지 역으로 확인해보는 방법을 이용해볼 수 있다. 가능한 답을 모두 확인하는 과정에서 완전 탐색이 이용되는 것이다.
3. 여러 문제 조건 중 한 조건을 고정시키면 문제 풀이가 간단해진다.
2번과 비슷한 방법이지만 답을 고정시키는 것이 아니라, 주어진 조건을 고정시키는 약간의 차이점이 있다.
이것 또한 예시를 보면 어떤 느낌인지 더 잘 알 것 같다. 마찬가지로 코드포스 문제이다.
codeforces.com/problemset/problem/1400/B
Problem - 1400B - Codeforces
codeforces.com
이 문제는 쉽게 설명하자면, 두 사람이 있고 가지고 있는 돈이 있다. 그리고 상점에 두 물건 A, B이 있는데, A와 B의 개수가 주어지고, A와 B의 가격이 주어진다. 이때, 두 사람이 살 수 있는 물건의 총개수를 구하는 문제이다.
무작정 가격이 싼 물건을 더 많이 사면 최대가 되는 듯 보이나, 사람이 2명이므로 둘 중 한 명이 돈이 많이 남게 될 수도 있다. 또 물건의 개수도 정해져 있기 때문에 단순히 싼 물건만 고려를 하기엔 쉽지 않다.
여기서 주목해야 할 점은 물건의 개수가 총 최대 40만 개라는 점이다. 그러므로 답의 범위 또한 40만 이하이다.
2번과 비슷하게 답의 범위가 조금 작은 듯 하나, 전체 물건을 4곳에 분배해야 하기 때문에 답을 고정시켜서는 완전 탐색이 어렵다.
잘 생각해보면 이 문제가 쉽지 않은 이유는 결국 사람이 두 명이기 때문이다.
사람이 1명만 있다면 무조건 싼 물건을 최대한 사는 게 이득이다. 하지만 사람이 두 명이기 때문에 무조건 싼 물건을 최대한 사면 안되고, 뒤에 구매할 사람까지 고려를 해주어야 한다.
그러므로 한 사람이 구매하는 개수를 고정시켜주면 편하지 않을까? 하는 생각을 해볼 수 있다.
실제로 물건 A, B의 개수가 각각 최대 20만이므로 완전 탐색으로 사람1 이 A, B 중 더 싼 물건을 구매할 개수를 고정시켜놓게 되면 사람1은 남은 돈으로 최대한 다른 물건을 구매해야 하고, 이후에 과정은 결국 사람이 1명만 있는 경우로 바뀌게 된다.
소스 코드)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
int main(void) {
int T; cin >> T;
while (T--) {
int p, f; cin >> p >> f;
int cnts, cntw; cin >> cnts >> cntw;
int s, w; cin >> s >> w;
if (s > w) {
swap(s, w);
swap(cnts, cntw);
}
int ans = 0;
for (int i = 0; i <= cnts; i++) {
int res = 0;
int k = min(i, p / s);
int k2 = min(cntw, (p - k*s) / w);
int k3 = min(cnts - k, f / s);
int k4 = min(cntw - k2, (f - k3*s) / w);
res = k + k2 + k3 + k4;
ans = max(ans, res);
}
cout << ans << '\n';
}
}
|
이런 방식으로 문제에서 주어진 조건 중 하나를 고정시켜서 문제가 단순해질 수 있는 경우에, 완전 탐색을 적용하여 문제를 해결할 수 있다. (완전 탐색 + 그리디)
4. 예시 문제
비교적 기초적인 문제들은 이 블로그에서 제시한 문제를 풀어보는 것을 권장한다. (설명도 잘되어있다)
blog.naver.com/kks227/220769870195
완전 탐색(Brute-force Search)
모든 문제를 푸는 데 있어서 가장 쉽고 간단한 방법부터 짚고 넘어가 봅시다.완전탐색, 브루트포스(Brute-...
blog.naver.com
아이디어)
총 칸의 개수가 8x8 = 64개이고, 벽을 총 3개 세워야 하므로 벽을 세우는 경우의 수가 최대 64C3이다. 충분히 완전 탐색으로 벽을 세울 수 있고, 벽을 세운 다음에 그래프 탐색으로 바이러스를 퍼트린 후에, 안전지대의 크기를 구하면 된다.
소스 코드)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#define MAX 2e9
#define pii pair<int, int>
using namespace std;
vector<vector<int>>ori(9, vector<int>(9));
int N, M;
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1 , 0 };
int ans;
int res(vector<vector<int>> &v) {
int cnt = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (v[i][j] == 0) cnt++;
}
}
return cnt;
}
void sol(int left, int x, int y) {
if (left == 0) {
vector<vector<int>> temp(ori);
queue<pii> q;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (temp[i][j] == 2) {
q.push({ i, j });
}
}
}
while (!q.empty()) {
pii now = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int a = now.first + dx[i];
int b = now.second + dy[i];
if (a > 0 && a <= N && b > 0 && b <= M) {
if (temp[a][b] == 0) {
temp[a][b] = 2;
q.push({ a,b });
}
}
}
}
ans = max(ans, res(temp));
}
else {
for (int j = y + 1; j <= M; j++) {
if (ori[x][j] == 0) {
ori[x][j] = 1;
sol(left - 1, x, j);
ori[x][j] = 0;
}
}
for (int i = x + 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (ori[i][j] == 0) {
ori[i][j] = 1;
sol(left - 1, i, j);
ori[i][j] = 0;
}
}
}
}
}
int main(void) {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
// freopen("input.txt", "r", stdin);
cin >> N >> M;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
cin >> ori[i][j];
}
}
sol(3, 1, 0);
cout << ans;
}
|
아이디어)
체스에서 퀸은 상하좌우, 대각선으로 이동이 가능하다. 따라서 같은 행과 같은 열에 두 개 이상의 퀸이 있으면 안 되므로 해당 행, 열에 퀸이 존재하는지 각각 1차원 배열로 정보를 담고 있으면서, 다음 퀸을 놓을 때 이 배열로 체크한다. 대각선은 직접 확인할 수 있다. 백트래킹 유형의 대표 문제이다.
소스 코드)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int chess[16][16];
int col[16];
int ans;
int N;
int dx[2] = { -1, -1 };
int dy[2] = { 1, -1 };
void sol(int x, int left) {
if (left == 0) {
ans++;
return;
}
if (x == N + 1 || x + left > N+1) return;
for (int q = 1; q <= N; q++) {
if (col[q] == 0) {
int check = 0;
for (int k = 0; k < 2; k++) {
int i = x + dx[k];
int j = q + dy[k];
while (i > 0 && j > 0 && i <= N && j <= N) {
if (chess[i][j] != 0) {
check = 1;
break;
}
i += dx[k];
j += dy[k];
}
if (check == 1) break;
}
if (check == 0) {
chess[x][q] = 1;
col[q] = 1;
sol(x + 1, left - 1);
chess[x][q] = 0;
col[q] = 0;
}
}
}
}
int main(void) {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> N;
sol(1, N);
cout << ans;
}
|
아이디어)
위에서 언급한 '연구소' 문제와 비슷하다. 주어지는 치킨집의 개수가 m개 이상, 13개 이하이므로 최대 13개라고 가정했을 때, 치킨집의 폐업 경우의 수는 13Cm이다. m = 6인 경우가 문제에서 가질 수 있는 최대의 경우의 수이고, 이 값은 충분히 완전 탐색이 가능하다. 따라서 M개의 치킨집만 남겨두는 경우들을 모두 구한 뒤, 각 집에서 최소 거리를 구한다.
소스 코드)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
#include<iostream>
#include<algorithm>
#include<vector>
#define MAX 2e9
#define pii pair<int, int>
using namespace std;
int N, M;
int ans;
int cnt;
vector<vector<int>> city(51, vector<int>(51));
vector<pii> chi;
vector<pii> sur;
int res(void) {
int t = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (city[i][j] == 1) {
int a = MAX;
for (int k = 0; k < M; k++) {
a = min(a, abs(sur[k].first - i) + abs(sur[k].second - j));
}
t += a;
}
}
}
return t;
}
void sol(int num, int idx) {
if (num == M) {
ans = min(ans, res());
return;
}
for (int i = idx + 1; i < cnt; i++) {
sur.push_back(chi[i]);
sol(num + 1, i);
sur.pop_back();
}
}
int main(void) {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> N >> M;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> city[i][j];
if (city[i][j] == 2) {
chi.push_back({ i, j });
cnt++;
}
}
}
ans = MAX;
sol(0, -1);
cout << ans;
}
|
아이디어)
기본적으로 모든 단어가 a, n, t, i, c를 포함하고 있기 때문에 N이 5보다 작은 경우는 답이 0이다.
그리고 N이 5 이상인 경우에는 처음부터 a, n, t, i, c를 포함시켜놓고 나머지 남은 알파벳으로 남은 개수만큼 완전 탐색을 이용하여 조합한다. 가능한 경우가 커 보이지만 실제로 최대의 경우의 수는 남은 알파벳 21개 중 10개 또는 11개를 고르는 경우의 수이고, 이는 약 35만 가지이다. N이 50보다 작고, 문자열의 길이가 15보다 작기 때문에 시간 내에 가능하다.
(비트마스크를 이용하면 훨씬 간단하고 빠르다)
소스 코드)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
using namespace std;
bool check[26];
vector<string> s;
vector<int> v;
int N, K;
int ans;
int sz;
void sol(int idx, int cnt) {
if (sz - 1 - idx < K - cnt) return;
if (cnt == K) {
int k = 0;
for (int i = 1; i <= N; i++) {
int ch = 0;
for (int j = 0; j < s[i].size(); j++) {
if (check[s[i][j] - 'a']) {
ch = 1; break;
}
}
if (ch == 0) k++;
}
ans = max(ans, k);
return;
}
else {
for (int i = idx + 1; i < sz; i++) {
check[v[i]] = false;
sol(i, cnt + 1);
check[v[i]] = true;
}
}
}
int main(void) {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> N >> K;
s.assign(N + 1, string());
for (int i = 1; i <= N; i++) {
cin >> s[i];
for (int j = 0; j < s[i].size(); j++) {
if (check[s[i][j] - 'a'] == false && s[i][j] != 'a' && s[i][j] != 'n'
&& s[i][j] != 't' && s[i][j] != 'i' && s[i][j] != 'c') {
v.push_back(s[i][j] - 'a');
check[s[i][j] - 'a'] = true;
}
}
}
if (K < 5) {
cout << 0;
}
else {
K -= 5;
sz = v.size();
if (sz <= K) cout << N;
else {
if (K == 0) {
int k = 0;
for (int i = 1; i <= N; i++) {
int ch = 0;
for (int j = 0; j < s[i].size(); j++) {
if (check[s[i][j] - 'a']) {
ch = 1; break;
}
}
if (ch == 0) k++;
}
ans = max(ans, k);
}
else {
for (int i = 0; i < sz - K + 1; i++) {
check[v[i]] = false;
sol(i, 1);
check[v[i]] = true;
}
}
cout << ans;
}
}
}
|
아이디어)
N이 8 이하이므로 완전 탐색으로 충분히 가능하다. 배열 A의 원소를 일렬로 나열하는(순열) 모든 경우를 고려해서 답을 구한다. (C++에서 제공하는 next_permutation 함수를 이용하면 훨씬 간단하다)
소스 코드)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int N;
int A[10];
int ans;
vector<int> temp;
bool check[10];
void sol(int cnt) {
if (cnt == N) {
int k = 0;
for (int i = 0; i < N-1; i++) {
k += abs(temp[i + 1] - temp[i]);
}
ans = max(ans, k);
return;
}
for (int i = 1; i <= N; i++) {
if (check[i] == false) {
check[i] = true;
temp.push_back(A[i]);
sol(cnt + 1);
temp.pop_back();
check[i] = false;
}
}
}
int main(void) {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> A[i];
}
sol(0);
cout << ans;
}
|
PC로 보시는 것을 권장합니다.
피드백은 언제나 환영입니다. 댓글로 달아주세요 ^-^
'알고리즘' 카테고리의 다른 글
| 비트마스크 (BitMask) 알고리즘 (3) | 2020.10.15 |
|---|---|
| 최소 / 최대 맨해튼 거리 (Manhattan Distance) (0) | 2020.09.17 |
| LIS (Longest Increasing Subsequence) - 최장 증가 부분 수열 (9) | 2020.04.22 |
| Knuth's Optimization (0) | 2019.07.22 |
| 볼록 껍질 (Convex Hull) (5) | 2019.03.10 |
