[10주 완성 C++ 코딩테스트] 필수개념 - 순열(Permutation), 조합(Combination)

순서와 상관 O 뽑는다면 >> 순열

순서와 상관 X 뽑는다면 >> 조합

 

순서를 재배치하여 ...

~한 순서의 경우 max 값을 구하시오 등등의 문제 >> 순열 !

---

* 순열 함수

next_permutation(오름차순)

prev_permutation(내림차순)

 

* 예시 코드

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

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

결과

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

 

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

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

&a[0] 이렇게 안쓰고 a 만 써도 가능하다.

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

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

벡터인 경우 begin, end 함수를 이용해서 호출한다.

순서정렬이 안되어 있다면 그 다음 경우의 수부터 구해지므로 순열함수 사용 전에 정렬을 꼭 해야 한다.

경우의 수 개수를 구하는 공식도 알아두자.

---

* 조합

[조합 경우의 수 개수구하는 공식]

 

[구현방법]

1) 재귀함수(4개 이상 뽑을 때 추천) 암기★★★★★

#include <iostream>
#include <vector>
using namespace std;

int n = 5, k = 3, a[5] = { 1, 2, 3, 4, 5 }; // 5C3

void print(vector<int> v) {
	for (int i : v) cout << a[i] << " ";
	cout << "\n";
}

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

int main() {
	vector<int> v;
	combi(-1, v);
	return 0;
}

 

2) 중첩 for문(3개 이하로 뽑을 때 추천. 구현이 간단함.)