1. 알고리즘 설명

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘

2. STL next_permutation

현재 순열을 사전 순으로 생각했을 때 다음 순열로 만들고 true를 반환

순열

int a[3] = {1, 2, 3};
do {
	for (int i = 0; i < 3; i++)
		cout << a[i];
	cout << '\n';
} while (next_permutation(a, a+3));
// 사전 순으로 다음 수열이 있다. true
// 현재 수열이 마지막 수열이다 . false

/*
123
132
213
231
312
321
*/

조합

int a[4] = {0, 0, 1, 1};  // 4C2
do {
	for (int i = 0; i < 4; i++) {
		if (a[i] == 0)
			cout << i + 1;
	}
	cout << '\n';
} while (next_permutation(a, a+4));

/*
12
13
14
23
24
34
*/

3. 문제

1. N-Queen

9663. N-Queen

isused 배열을 3개 선언하여 각각 세로 열, 증가 방향 대각선, 감소 방향 대각선에 Queen 말이 들어있는지 확인하면 효과적으로 선택 가능 여부를 확인할 수 있다.

(0, 0)	(0, 1)	(0, 2)
(1, 0)	(1, 1)	(1, 2)
(2, 0)	(2, 1)	(2, 2)

• 증가 방향 대각선 (x 기준) : x+y 로 확인
• 감소 방향 대각선 (x 기준) : x-y+N-1 로 확인

#include <bits/stdc++.h>
using namespace std;

// bool dat[15][15];
bool isused1[15];
bool isused2[30];
bool isused3[30];
int cnt = 0;
int N;

void f(int n) {
    if (n == N) {
        cnt++;
        return;
    }


    for (int j = 0; j < N; j++) {
        if (!(isused1[j] || isused2[n+j] || isused3[n-j+N-1])) {
            // cout << "inside if: " << n << ' ' << j << ' ' << n << '\n';
            isused1[j] = 1;
            isused2[n+j] = 1;
            isused3[n-j+N-1] = 1;
            f(n+1);
            isused1[j] = 0;
            isused2[n+j] = 0;
            isused3[n-j+N-1] = 0;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> N;
    f(0);
    cout << cnt << '\n';
    return 0;
}

2. 부분수열의 합

1182. 부분수열의 합

각 인덱스별로 선택하는 경우와 선택하지 않는 경우 각각을 재귀함수로 처리하면 쉽게 풀 수 있다. S 값이 0인 경우 공집합은 제외해야 하므로 1을 빼 준다

// 부분집합의 개수 2^N
// 진부분집합의 개수 2^N - 1 (공집합 제외)
#include <bits/stdc++.h>
using namespace std;

int N, S, cnt;
int dat[20];

void f(int idx, int sum) {
    if (idx == N) {
        cnt += (sum == S ? 1 : 0);
        return;
    }

    f(idx+1, sum + dat[idx]);
    f(idx+1, sum);
}

int main() {
    cin >> N >> S;
    for (int i = 0; i < N; i++) {
        cin >> dat[i];
    }
    f(0, 0);
    cout << (S == 0 ? cnt - 1 : cnt) << '\n';
}

3. N과 M(12)

15666. N과 M(12)

수열의 중복을 확인해야 할 경우 tmp 변수를 불가능한 값인 0으로 초기화하고 for문 안에서 현재 값으로 변경해서 이전 값과 현재 값이 겹치는지 비교한다.

비오름차순 조건의 경우 K가 0인지 체크하고 0이 아니면 k-1과 현재 값을 비교하여 비오름차순 조건을 만족하는지 확인한다.

#include <bits/stdc++.h>
using namespace std;

int num[10];
int res[10];
int N, M;

void f(int k) {
    if (k == M) {
        for (int i = 0; i < M; i++) {
            cout << res[i] << ' ';
        }
        cout << '\n';
        return;
    }   

    int tmp = 0;
    for (int i = 0; i < N; i++) {
        if (
            tmp != num[i]
            && (k == 0 || (k > 0 && res[k-1] <= num[i])) 
            // && 
        ) 
        {
            res[k] = num[i];
            tmp = num[i];
            f(k+1);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> N >> M;
    for (int i = 0; i < N; i++) 
        cin >> num[i];
    sort(num, num+N);
    f(0);
}

출처 및 참고자료 : 바킹독의 실전 알고리즘