[C++] 조합

1. 조합

 

서로 다른 n개에서 순서와 상관없이 r개를 고르는 걸 조합이라고 한다.

 

조합을 구현하는 두 가지 방법에 대하여 학습했다.

 

---

2. 중첩 for문

 

3개까진 중첩 for문을 사용하자.

 

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

int n = 5;
int 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 << a[i] << " " << a[j] << " " << a[k] << '\\n';
			} 
		}
	}
	return 0;
}

/*
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
*/

 

---

3. 재귀함수

 

대략 4개 이상부터는 재귀함수를 사용해서 구현하자.

 

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

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

void print(vector<int> b){
	for(int i : b)cout << i << " ";
    cout << '\\n';
}

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

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

/*
1 2 3 4 
1 2 3 5 
1 2 3 6 
1 2 3 7 
1 2 4 5 
1 2 4 6 
1 2 4 7 
1 2 5 6 
1 2 5 7 
1 2 6 7 
1 3 4 5 
1 3 4 6 
1 3 4 7 
1 3 5 6 
1 3 5 7 
1 3 6 7 
1 4 5 6 
1 4 5 7 
1 4 6 7 
1 5 6 7 
2 3 4 5 
2 3 4 6 
2 3 4 7 
2 3 5 6 
2 3 5 7 
2 3 6 7 
2 4 5 6 
2 4 5 7 
2 4 6 7 
2 5 6 7 
3 4 5 6 
3 4 5 7 
3 4 6 7 
3 5 6 7 
4 5 6 7 
*/

 

---

4. 주의점

 

nCr이나 nC(n-r)이나 똑같다.

 

3개 중에 2개를 뽑는 것 = 3개 중에 1개를 뽑는 것

 

1개를 뽑으면 나머지 2개가 나오기 때문이다.

 

가능한 작은 수를 뽑도록 변형하면 좋겠죠?

 

---

 

[알고리즘] 2309번: 일곱 난쟁이 (수정)