코딩 테스트를 준비하면서 순열과 조합은 빼놓을 수 없기 때문에 정리를 하였다.
코딩 테스트에 대한 알고리즘 정리에 대한 정보는 그동안 사놓고 책장에 넣어 놓았던 마크 그레고리의 "전문가를 위한 C++" 을 기반으로 구글링하여 작성하였다.

1. 순열

순열(permutation) 이란 시퀀스에 담긴 원소를 다양한 순서로 나열하는 것 이다. 이러한 순열 연산을 제공하는 순열 알고리즘은 다음과 같다.

알고리즘 이름	설명	복잡도
is_permutation()	두 시퀀스 중 하나가 다른 시퀀스의 순열이면 true를 리턴한다.	제곱(quadratic)
next_permutaion() prev_permutaion()	주어진 시퀀스를 사전순으로 다음 또는이전에 나오는 순열로 변환한다. 어느 하나에 대해 연속적으로 호출하면 모든 경우의 순열을 수할 수 있다.단, 제대로 정렬된 시퀀스로 호출하기 시작해야 한다.더 이상 나올 수 있는 순열이 없으면 false 를 리턴한다.	선형

뉴진스의 노래 "디토", "하입보이", "어텐션", "쿠키" 총 4개의 노래 중에 2개를 뽑아 플레이리스트에서 재생하는 방법은 몇가지 일까요? 답은 12가지 입니다. 순서랑 관계 있이? 없이? 상관없이 경우의 수를 뽑는 것 같다면 순열과 조합이 생각 나야합니다. 위 예시의 경우 제가 플레이리스트에 재생하는 방법이라고 했으니 순서가 상관이 있습니다. 그래서 순열이고 nPr(n=4, r=2) 이므로 아래 공식에 의해 12가 나옵니다.

${n}{P}{r}=\frac{n!}{(n-r)!}$ - permutation

만약 일일이 뽑는 방법을 나열하면 각각 노래를 1, 2, 3, 4로 표시하고 다음과 같이 뽑을 수 있습니다.
[12],[13],[14],[23],[24],[34]
그리고 순서를 뒤집어서 [21],[31],[41],[32],[42],[43] 총 12가지 입니다.

서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것을 순열이라 합니다.

C++ 에서 순열을 구성하는 방법에는 표준라이브러리를 사용하는 것과 재귀함수를 이용하는 두가지 방법이 있습니다.

1. 표준라이브러리(next_permutaion, prev_permutaion)

표준 라이브러리로는 next_permutaion 과 prev_permutaion 이 있습니다.

next_permutaion : "오름차순의 배열"을 기반
prev_permutaion : "내림차순의 배열"을 기반

매개변수로는 [first,last) 범위로 순열을 시작할 범위의 첫번째 주소, 그리고 포함되지 않는 마지막 주소를 넣습니다.

3개 중에 3개를 다 뽑는 순열의 코드는 다음과 같습니다.

#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';
    
    cout << "prev_permutaion" << "\n";
    v.clear();
    cnt = 0;
    for(int i = 2; i >= 0; i--){
        v.push_back(a[i]);
    }
    // 3, 2, 1 로 배열 만들기
    do{
        printV(v);
    }while(prev_permutation(v.begin(), v.end()));
    cout << cnt << '\n';
    return 0;
}
// 결과
// next_permutaion
// 1 2 3 
// 1 3 2 
// 2 1 3 
// 2 3 1 
// 3 1 2 
// 3 2 1 
// 6
// prev_permutaion
// 3 2 1 
// 3 1 2 
// 2 3 1 
// 2 1 3 
// 1 3 2 
// 1 2 3 
// 6

next_permutation(v.begin(), v.end())

end()는 해당 배열의 마지막 요소보다 한칸 뒤의 주소값을 가르킵니다. 따라서, 매개변수가 [first, last) 범위 조건에 해당합니다.

또한 아래 코드와 같이 범위를 지정할 수 도 있습니다.

do{
printV(v);
}while(next_permutation(v.begin(), v.begin() + 2));

2. 재귀함수

#include<bits/stdc++.h>
using namespace std;
int a[3] = {1, 2, 3};
vector<int> v;
int cnt;
void printV(vector<int> &v){
    for(int i = 0; i < v.size(); i++){
        cout << v[i] << " ";
    }
    cnt++;
    cout << "\n";
}

void permutaion(int n, int r, int depth){
    if( r == depth){
        printV(v);
        return;
    }
    for(int i = depth; i< n ; i++){
        swap(v[i], v[depth]);
        permutaion(n, r, depth + 1);
        swap(v[i], v[depth]);
    }
    return;
}

int main(){
    for(int i = 0; i < 3; i++){
        v.push_back(a[i]);
    }
    permutaion(3, 3, 0);
    cout << cnt << "\n";
    return 0;
}

//결과
// 1 2 3 
// 1 3 2 
// 2 1 3 
// 2 3 1 
// 3 2 1 
// 3 1 2 
// 6

swap 함수를 왜 쓰는지 코드만 보면 모르시겠지만 우리가 하나하나 경우를 바꿔가며 경우의 수를 계산하듯이 순서를 바꿔가며 계산하는 방식입니다.

이해가 안되시면 클릭

2. 조합

서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관없게 선택하는 혹은 나열하는 것을 조합이라 합니다.

$\ {n}{C}{r}=\frac{n!}{r!(n-r)!}$ - combination
조합을 구현하는 방법에는 재귀함수와 중복 for문이 있습니다.

1. 재귀함수

#include<bits/stdc++.h>
using namespace std;
int cnt;
int n = 5, r = 3, a[5] = {1, 2, 3, 4, 5};
void printV(vector<int> b){
    for(int i : b)cout << i << " ";
    cout << '\n';
    cnt++;
}

void combi(int start, vector<int> b){
    if(b.size() == r){
        printV(b);
        return;
    }
    for(int i = start + 1; i < n; i++){
        b.push_back(i);
        combi(i, b);
        b.pop_back();
    }
    return;
}

int main(){
    vector<int> b;
    combi(-1, b);

    cout << cnt << '\n';
    return 0;
}
// 결과
// 0 1 2 
// 0 1 3 
// 0 1 4 
// 0 2 3 
// 0 2 4 
// 0 3 4 
// 1 2 3 
// 1 2 4 
// 1 3 4 
// 2 3 4 
// 10

2. 중첩 for 문

r이 작을 때는 for 문을 사용하여 구현할 수 있습니다.만약 r 이 크다면 재귀함수를 이용하는 것이 좋습니다.

#include<bits/stdc++.h>
using namespace std;
int cnt;
int n = 5, r = 3, a[5] = {1, 2, 3, 4, 5};


int main(){
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            for(int k = j + 1; k < n; k++){
                cout << i << " " << j << " " << k << '\n';
                cnt++;
            }
        }
    }
    cout << cnt << '\n';
    return 0;
}
// 결과
// 0 1 2
// 0 1 3
// 0 1 4
// 0 2 3
// 0 2 4
// 0 3 4
// 1 2 3
// 1 2 4
// 1 3 4
// 2 3 4
// 10

그리고 조합의 중요한 특징이 있는데
$\ {n}{C}{r}={n}{C}{(n-r) = \frac{n!}{r!(n-r)!} }$
10개 중에 3개를 뽑나 10개 중에 7개를 뽑나 경우의 수는 같습니다.

아래 코드와 같이 5개 중에 2개 뽑아도 10개입니다.

#include<bits/stdc++.h>
using namespace std;
int cnt;
int n = 5, r = 2, a[5] = {1, 2, 3, 4, 5};


int main(){
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
           
                cout << i << " " << j << '\n';
                cnt++;
            
        }
    }
    cout << cnt << '\n';
    return 0;
}
// 결과
// 0 1
// 0 2
// 0 3
// 0 4
// 1 2
// 1 3
// 1 4
// 2 3
// 2 4
// 3 4
// 10