[알고리즘] 탐색(3) - 조합(Combination)

 개념 

서로 다른 n개의 수 중에 r개를 선택
nCr = n! / (n-r)! * r!

 

리스트를 순서에 상관없이 수를 뽑는 것입니다. 사실 완전탐색으로 풀리는 문제가 있지만 많은 문제들이 그렇지 않습니다. 그럴때 최적화를 하여 답을 도출해 내는것이 중요한데, 최적화하기 앞서서 기본 뼈대가되는 탐색인 조합탐색을 알아보도록 하겠습니다.

 

 구현 

재귀 호출을 이용해서 조합을 구성하기 위해서는 네가지 파라미터가 필요합니다.

 

• nCr에서 n
• nCr에서 r
• 기저 조건을 위한 idx
• 어느곳을 탐색할지 정하는 curr

 

그러나 n과 r이 고정되어 있다면 idx와 curr만 사용할수도 있습니다. 이처럼 재귀 호출은 변형에 용이합니다. 그리고 아래와 같은 배열 2가지가 필요합니다.

 

• 나열한 수를 담을 배열
• 나열되어져야 할 수를 담은 배열

 

int ans[3], arr[5];

// nCr
void Combination(int idx, int curr, int n, int r)
{
	if (idx == r)
	{
		for (int i = 0; i < r; ++i)
			cout << ans[i] << " ";
		cout << '\n';
		return;
	}

	for (int i = curr; i < n; ++i)
	{
		ans[idx] = arr[i];
		Combination(idx + 1, i + 1, n, r);
	}
}

 

다음뽑을 수를 파라미터로 i+1로 넣어줌으로써 조합 nCr을 구성하고 있습니다. 그런데 이 뼈대를 어디에 이용할까요? 사실 여기서 주목해야할 점은 조합의 뼈대가 아니라 어떠한 원리로 동작을 하는지 아는 것이 중요합니다. 뼈대는 각자의 코딩스타일마다 다를 수 있고, 또한 방법도 다를 수 있습니다. 가령 이항계수의 성질을 이용해서 조합을 구할수도 있겠죠.

 

우리가 문제를 코딩테스트를 본다고 가정했을 때, 어느곳에서 "5C2 또는 10P3을 구하시오."라는 문제가 나오겠습니까? 따라서 이 뼈대를 이용해서 활용하는 것이 중요합니다.  

 

아주 간단한 변형으로, 철수가 있는데 철수는 사탕을 10개중에 3개를 뽑아서 먹을수있다고 합니다. 존재하는 사탕의 개수가 주어집니다. 이때 3개를 뽑아서 먹을 수있는 경우의수는 몇일까요?? (단 각 사탕은 1개이상씩 있습니다.)

 

이 문제가 의도한 것은 조합을 구성할때, 각 뽑을수있는 개수가 한개가 아닐 수도 있다는 말입니다. 그렇다면 도중에 조건을 달거나 변형을해서 문제를 해결해야겠죠? 정답은, 각 사탕마다 뽑을 수 있는 개수를 정해놓은뒤 중복조합의 코드를 이용해서 짜면 되겠습니다.

 

아래는 중복조합의 코드입니다.

 

int ans[3], arr[5];

// nHr
void Combination(int idx, int curr, int n, int r)
{
	if (idx == r)
	{
		for (int i = 0; i < r; ++i)
			cout << ans[i] << " ";
		cout << '\n';
		return;
	}

	for (int i = curr; i < n; ++i)
	{
		ans[idx] = arr[i];
		Combination(idx + 1, curr++, n, r);
	}
}

 

 

 시간복잡도 

모든 조합의 합은 이항계수의 성질에 따라 한번 재귀호출시마다 2개의 함수를 호출하기 때문에 시간복잡도는 O(2^n)을 가집니다. 만약 한가지 조합만의 시간복잡도를 구하기 위해서는 페르마 소정리를 이용해서 구할 수 있습니다. 그러나 조합탐색의 경우 가지치기를 포함해서 최적화에대한 상충관계를 이해해야하기 때문에 딱히 정답이 없습니다.

 

다음번에는 가지치기에대해서 자세히 알아보도록하겠습니다.