[C++/CPP] C++ 코딩테스트 용 순열 및 조합 next_permutation, next_combination

Visual Studio에 <bits/stdc++.h> 헤더파일 추가하기

출처:https://hkhan.tistory.com/36

[C++] Visual Studio에 <bits/stdc++.h> 헤더파일 추가하기

stdc++.h

0.00MB

C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.38.33130\include

위 경로에서 " 14.33 .31629 "는 Visual Studio 버전이며 각자 다른 숫자일 수 있으니 불안하다면 각 폴더에 있는 include에 bits 폴더 복사 후 붙여넣기 해준다.

위 경로에서 "bits" 폴더 생성 후 "stdc++.h" 파일 넣는다.

#include<bits/stdc++.h>
// include 신경쓰지 않고 코딩에만 집중

int main() {
	// logic
}

 

C++ 온라인 컴파일러 사이트

1. https://replit.com/~
2. https://www.onlinegdb.com/online_c++_compiler
3. https://cpp.sh/
4. https://www.tutorialspoint.com/compile_cpp_online.php

1. 순열 - next_permutation()

#include<bits/stdc++.h>

using namespace std;

int cnt;

void printV(vector<int> &v){
    for(int i = 0; i < v.size(); i++){
        cout << v[i] << " ";
    }
    cnt++;
    cout << "\n";
}

int main(){
    int a[3] = {1, 2, 3};
    vector<int> v;
    for(int i = 0; i < 3; i++){
        v.push_back(a[i]);
    }
    // 1, 2, 3 로 배열 만들기
    cout << "next_permutaion" << "\n";
    do{
        printV(v);
    }while(next_permutation(v.begin(), v.end()));
    cout << cnt << '\n';
}

// 출력 결과
next_permutaion
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1 
6

next_permutation 함수는 주어진 범위의 원소들을 순열로 정렬한 후,

다음 순열을 구합니다. 다음 순열을 구할 수 없는 경우, false를 반환한다.

next_permutation 함수를 사용하면 다음 순열을 쉽게 구할 수 있다.

또한, 이 함수는 O(n)의 시간 복잡도를 가지므로, 효율적으로 사용할 수 있다.

2. 조합 - next_combination()

#include<bits/stdc++.h>

using namespace std;

void print_combination(const vector<int>& elements, const vector<int>& combination) {
    cout << "Combination: ";
    for (int index : combination) {
        cout << elements[index] << ' ';
    }
    cout << endl;
}

void generate_combinations_helper(const vector<int>& elements, size_t r, vector<int>& combination, size_t start) {
    if (r == 0) {
        print_combination(elements, combination);
        return;
    }

    for (size_t i = start; i < elements.size(); ++i) {
        combination.push_back(i);
        generate_combinations_helper(elements, r - 1, combination, i + 1);
        combination.pop_back();
    }
}

void generate_combinations(const vector<int>& elements, size_t r) {
    vector<int> combination;
    generate_combinations_helper(elements, r, combination, 0);
}

int main() {
    vector<int> elements = { 1, 2, 3, 4 };
    size_t r = 2;  // 조합의 크기

    generate_combinations(elements, r);

    return 0;
}

// 출력 결과
Combination: 1 2
Combination: 1 3
Combination: 1 4
Combination: 2 3
Combination: 2 4
Combination: 3 4

코드 설명

print_combination

void print_combination(const vector<int>& elements, const vector<int>& combination) {
    cout << "Combination: ";
    for (int index : combination) {
        cout << elements[index] << ' ';
    }
    cout << endl;
}

이 부분은 조합을 출력하는 print_combination 함수입니다.

 elements 벡터에 있는 원소들 중에서 

combination 벡터에 있는 인덱스에 해당하는 원소들을 출력합니다.

 

generate_combinations_helper

void generate_combinations_helper(const vector<int>& elements, size_t r, vector<int>& combination, size_t start) {
    if (r == 0) {
        print_combination(elements, combination);
        return;
    }

    for (size_t i = start; i < elements.size(); ++i) {
        combination.push_back(i);
        generate_combinations_helper(elements, r - 1, combination, i + 1);
        combination.pop_back();
    }
}

이 부분은 조합을 생성하는 generate_combinations_helper 함수입니다. 

이 함수는 재귀적으로 호출되며, 

현재 선택된 원소의 인덱스를 combination 벡터에 추가하고,

재귀 호출을 통해 다음 원소를 선택하게 됩니다.

재귀 호출이 r이 0이 될 때마다

print_combination 함수를 호출하여 현재까지의 조합을 출력합니다.

 

generate_combination

void generate_combinations(const vector<int>& elements, size_t r) {
    vector<int> combination;
    generate_combinations_helper(elements, r, combination, 0);
}

이 부분은 조합 생성을 시작하는 generate_combinations 함수입니다. 

이 함수는 초기에 빈 combination 벡터를 생성하고, 

generate_combinations_helper 함수를 호출하여 실제 조합 생성을 시작합니다.

 

main

int main() {
    vector<int> elements = { 1, 2, 3, 4 };
    size_t r = 2;  // 조합의 크기

    generate_combinations(elements, r);

    return 0;
}

이 부분은 프로그램의 진입점인 main 함수입니다. 

여기서는 조합을 생성할 요소들을 정의하고, 

조합의 크기를 r로 설정한 뒤 

generate_combinations 함수를 호출하여 조합을 생성합니다.

코드의 핵심은 재귀적인 방법을 사용하여 모든 조합을 생성하는 부분이며, 

print_combination 함수를 통해 각 조합을 출력합니다. 

 

이 코드를 실행하면

{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}

와 같은 모든 2개씩 묶인 조합이 출력됩니다.