0주차-3. 기초 개념 : 조합(Combination)

조합이란?

• 조합이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미한다. (순서 상관 없음)
• 조합이 순열과 다른 대표적인 점은 순서가 달라도 요소가 같으면 같은 조합으로 본다는 것이다.
• 1, 2, 3, 4, 5라는 집합이 있을 때
• {1, 2, 3, 4, 5}, {2, 1, 3, 4, 5}, {3, 1, 2, 4, 5} .... 등등 순서를 바꿔도 같은 조합으로 본다는 것이 대표적인 차이점이다.
• 조합은 n C r로 표현하며 개수를 구하는 식은 아래와 같다.

 

 

 

 

 

 

---

재귀함수를 이용한 구현 (뽑아야 할 수(r) 가 4개 이상인 경우)

 

void combination(int start, int n, int k, std::vector<int>& v)
{
	// n : 최대 조합 수 'n'Cr
	// k : 그 조합에서 추출할 요소 개수 nC'r' ex) k(3) = {1, 2, 3}...
	if (v.size() == k)
	{
		print(v);
		return;
	}

	for (int i = start+1; i < n; i++)
	{
		v.push_back(i);
		combination(start, n, k, v);
		v.pop_back();
	}

	return;
}


int main()
{
	std::vector<int> v;
	combination(-1, 5, 3, v);
}

• 얼핏 보면 순열과 비슷해보인다.
• swap하는 부분이 push_back으로 i를 넣고 pop_back으로 빼주는 것과 비슷하다.
• i가 start의 영향을 받으므로 수가 순서가 바뀐 채 중복해서 들어가는 일은 없을 것이다.

 

 

 

 

 

---

중첩 for문을 이용한 구현

int main()
{
	int n = 5;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < i; j++)
			for (int k = 0; k < j; k++)
				std::cout << i << ", " << j << ", " << k << std::endl;
}

• r이 3 이하인 경우 이렇게 중첩 for문으로 해결할 수 있다.