재귀함수로 만드는 조합과 순열

순열과 조합은 경우의 수를 기반으로 푸는 코딩 테스트 문제에 많이 활용됩니다.

여러가지 경우의 수를 생각해야 하는데 순서를 바꿔서 몇 개를 뽑는다.몇 개를 설정한다.
라고 했을 때는 순서가 상관 있으니 순열을 써야 하고, 순서를 바꾸지 않고 몇 개를 뽑는 게 중요하다.
설정하는게 중요하다 라는게 있다면 조합을 써야 합니다.

조합

조합에 '순서'는 없습니다. 순서 상관없이 오로지 몇명을 '다양하게' 뽑을 때 사용합니다.

 

for 문 안에 재귀함수와 push/pop이 일어나는 과정만 이해하면 됩니다.

 

재귀함수를 통한 조합 구현 방법도 유용하지만 r이 작을 때에는
중첩 for문을 이용하는 게 더 효율적입니다. r이 10이거나 20이라면 재귀함수를 이용하는게 좋습니다.

#include <bits/stdc++.h>
using namespace std;
int n = 5, k = 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';
            }
        }
    }
    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

 

위코드와 순서만 다를 뿐 같은 의미를 가집니다. "뽑는 것"은 동일합니다.

nCr 이나 nC(n-r) 이나 동일하다는 의미입니다.

#include <bits/stdc++.h>
using namespace std;
int n = 5, k = 3, a[5] = {1, 2, 3, 4, 5};
int main(){
    for(int i=0 ; i<n ; i++){
        for(int j=0 ; j<i ; j++){
            for(int k=0 ; k<j ; k++){
                cout << i << " " << j << " " << k << '\n';
            }
        }
    }
    return 0;
}

2 1 0
3 1 0
3 2 0
3 2 1
4 1 0
4 2 0
4 3 0
4 3 1
4 3 2

 

순열

순열은 정해진 임의의 집합을 다른 순서로 섞는 연산을 말합니다.

for 문안에 재귀함수와 swap이 일어나는 과정만 이해하면 됩니다.

 

재귀함수를 통한 순열 구현 방법도 유용하지만 실제 코딩 테스트에서는
nextPermutation() 함수 사용 후 do while 문으로 해결하는게 효율적입니다.

 

vector의 end()는 해당 리스트의 마지막 요소보다 한칸 뒤 주소를 가리킵니다.

해당 매개변수를 이용하면 종점인 end()를 넣지 않고 범위를 조정하여 순열을 만들 수 있습니다.

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

void printV(vector<int> &v) {
    for(int i=0 ; i < v.size() ; i++) {
        cout << v[i] << " ";
    }
    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 부터 오름차순 순열 뽑기
    do {
        printV(v)
    } while(nextPermutation(v.begin(), v.end());
    
    return 0;
}

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1