[코테/C++] 순열과 조합

순열과 조합은 알고리즘 문제들의 단골 요소다.

경우의 수를 순열과 조합으로 확인하여 풀어야하는 경우들이 많다.

 

배열의 순열과 조합을 확인하는 방법을 알아보자.

 

순열

순열은 next_permutation이라는 메서드를 활용하는 것이 가장 간단한 방법이다.

next_permutation을 사용하기 전에

반드시 배열을 오름차순 정렬해야 함을 주의하자.

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

int main() {
    int a[3] = { 1, 3, 2 };
    sort(a, a+3);
    do{
        for(int i : a) cout << i <<' ';
        cout <<'\n';
    }while(next_permutation(a, a+3));
    /*
    1 2 3 
    1 3 2 
    2 1 3 
    2 3 1 
    3 1 2 
    3 2 1 
    */
    
	return 0;
}

vector도 동일하게 가능하다.

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

int main() {
    vector<int> v= { 1, 3, 2 };
    sort(v.begin(), v.end());
    do{
        for(int i : v) cout << i <<' ';
        cout <<'\n';
    }while(next_permutation(v.begin(), v.end()));
    /*
    1 2 3 
    1 3 2 
    2 1 3 
    2 3 1 
    3 1 2 
    3 2 1 
    */
    
	return 0;
}

 

조합

조합은 순열처럼 단순한 메서드를 사용하기는 어렵고

재귀함수로 별도의 함수를 정의하여 사용하곤 한다.

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

int n = 5, k = 3, a[5] = {1, 2, 3, 4, 5};
void combi(int start, vector<int> b){
    if(b.size() == k){
        for(int i : b){
            cout << a[i] << ' ';
        }
        cout << '\n';
        return;
    }
    for(int i = start + 1; i < n; i++){
        b.push_back(i);
        combi(i, b);
        b.pop_back();
    }
    
}

int main() {
    vector<int> v;
    combi(-1, v);
    
    /*
    1 2 3 
    1 2 4 
    1 2 5 
    1 3 4 
    1 3 5 
    1 4 5 
    2 3 4 
    2 3 5 
    2 4 5 
    3 4 5 
    */
    
    return 0;
}

위 combi 함수는 시작점을 항상 -1로 받고, 

빈배열 b(blank)를 받아서 

참조하는 배열의 길이 n과 뽑아야 하는 값의 개수 k를 사용하여

n에서 k개를 뽑는 모든 조합을 확인한다.

 

값은 중복되는 값이 있을 수도 있기에

보통 index를 기준으로 조합을 생성하고

조합 생성 후 마지막 print, push_back 등의 작업에서 index를 활용하여 값을 호출한다.

 

start 위치를 start + 1로, n 전까지 순회하도록 만드는 것도 핵심이다.