<알고리즘> 조합(Combination)

조합에서 “순서”는 없음, 그저 몇명을 뽑아서 갈 것인가를 쓸 때 조합을 씁니다.

예를 들어 지원자가 1000명 중에 4명의 개발자를 뽑아 회사의 신입개발자로 채용한다고 하면

순서 상관없고 다양하게 뽑으면 됨

 

 

 

 

1. 재귀 함수 활용 코드

---

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

// 전체개수  
int n = 5;
// 몇개를 뽑을 건지 
int k = 3;
int a[5] = { 1, 2, 3, 4, 5 };
vector<int> b;

void print(vector<int> b)
{
	for (int i = 0; i < b.size(); i++)
		cout << b[i] << " ";
	cout << endl;
}

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()
{
	combi(-1, b);
	return 0;
}

 

 

* 재귀함수 분석

 

 

 

 

2. 중첩 for문 활용 코드

 

---

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

// 전체개수  
int n = 5;
// 몇개를 뽑을 건지 
int k = 3;
int a[5] = {1, 2, 3, 4, 5};
vector<int> b;

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

 

 

순서 다르게 뽑기도 가능

---

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

// 전체개수  
int n = 5;
// 몇개를 뽑을 건지 
int k = 3;
int a[5] = {1, 2, 3, 4, 5};
vector<int> b;

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 2 1
4 3 0
4 3 1
4 3 2
*/