[C/C++] 순열과 조합 알고리즘 구현하기 3

저번 시간까지 순열의 개념을 학습하고, 일반적인 순열과 중복이 가능한 순열을 알고리즘으로 구현하는 방법을 알아보았다.

오늘은 조합에 대해서 알아보고 알고리즘을 구현해 보자.

---

조합

 

조합이란 Combination이라고도 하며 순열과 마찬가지로 n개 중에서 r개를 고르는 경우의 수를 의미한다.

순열과 다른 점은 순서를 고려하지 않는 다는 것이다.

여기서 순서란 이런 의미이다.

순열의 경우 1, 2, 3 중에서 2개를 고를 때 (1, 2), (1, 3), (2, 1) ... 순서로 1과 2를 뽑았더라도 나중에 2와 1 순서로 다시 한 번 뽑을 수 있는 것이다.

하지만 조합은 (1, 2)와 (2, 1)를 같은 것으로 본다.

그러므로 1, 2, 3 중에서 2개를 고른다면 조합은 (1, 2), (2, 3), (3, 1) 3개의 경우의 수로 나타낼 수 있다.

헷갈린다면 이렇게 기억하자.

순열은 (1, 2)와 (2, 1)이 순서가 다름을 고려한 것이고, 조합은 (1, 2)와 (2, 1)는 같은 경우의 수라고 생각한다!

그러므로 순열의 경우의 수가 더 많아진다.

아래는 조합의 공식이다.

 

조합 공식

알아두면 나중에 코드 작성할 때 도움이 되니 외워두자!

 

조합 알고리즘

 

조합은 앞서 선택했던 숫자들의 조합을 다시 선택하지 않는 것이 중요하다.

그래서 순열과 마찬가지로 DFS를 활용하지만, 다음 함수를 호출할 때 인자로 현재 선택한 숫자의 인덱스+1을 전달한다.

int tmp[5];
bool check[5] = { false, };

 

먼저 배열을 생성하자.

tmp는 선택한 숫자를 담기 위한 배열이다.

숫자 데이터를 담을 것이기 때문에 int형으로 생성한다.

check 배열은 선택한 숫자의 방문 여부를 저장하기 위해 생성하므로 bool 형식으로 생성한다.

하지만! 조합을 구현할 때는 check 배열을 사용하지 않아도 된다!

combination 함수의 인자를 통해서 앞에서 뽑았던 숫자를 사용하지 않도록 할 수 있기 때문이다!

그러므로 이번 시간에는 check 배열 없이 어떻게 중복 없이 숫자를 뽑을 수 있는가에 대해서 이해하면 100점이다!

void combination(int depth, int next)
{
	...
}

 

드디어 조합을 구현하는 함수이다.

정수형 변수 depth는 선택한 숫자의 개수이다.

함수를 호출할 때마다 현재 몇 개의 숫자를 선택했는지를 넘겨준다.

숫자를 선택했다면 depth+1 형식으로 넘겨준다.

next는 선택한 숫자의 인덱스이다.

현재 어느 위치에 있는 숫자를 선택했는지 알고, 다음 번 숫자를 선택하라는 의미로 next+1 형태로 넘겨준다.

이게 바로 중복 없이 숫자를 뽑을 수 있는 비결이다.

for (int i = next; i < 3; i++)
{
	tmp[depth] = i+1;
	combination(depth + 1, i+1);
}

 

숫자를 선택하는 부분이다.

선택한 숫자 바로 다음 숫자를 next라고 하며, 주어진 숫자의 끝까지 반복하며 선택을 한다.

check[i]의 데이터를 선택하지 않았다면 true 처리 후 tmp[depth]에 선택한 숫자를 넣어준다.

그리고 함수를 호출해 선택한 숫자의 개수와 다음 숫자의 인덱스를 넘겨준다.

이 떄 depth+1이 선택한 숫자의 개수이며, i+1이 다음 숫자의 인덱스이다.

이 함수의 호출이 종료되면 check를 false 처리 해준다.

if (depth == 2)
{
	for (int i = 0; i < 2; i++)
	{
		cout << tmp[i] << " ";
	}
	cout << endl;
	return;
}

 

2개의 숫자를 선택했다면 저장된 숫자를 모두 출력해주는 코드이다.

출력 후 줄 바꿈을 한 뒤 함수를 return한다.

int main()
{
	combination(0, 0);
}

 

메인 함수에서 combination 함수를 호출하는 것이다.

처음에는 선택한 숫자가 없으므로 depth 값으로 0을 넘겨주고, next 또한 첫 번째 숫자부터 선택해야 하므로 0을 넘겨준다.

 

아래는 전체 코드이다.

#include <iostream>

using namespace std;

int tmp[5];
bool check[5] = { false, };

void combination(int depth, int next)
{
	if (depth == 2)
	{
		for (int i = 0; i < 2; i++)
		{
			cout << tmp[i] << " ";
		}
		cout << endl;
		return;
	}

	for (int i = next; i < 3; i++)
	{
		check[i] = true;
		tmp[depth] = i+1;
		combination(depth + 1, i + 1);
	}
}

int main()
{
	combination(0, 0);
}

---

오늘은 조합의 개념을 학습했다.

순열과 다른 점을 이해하면 조합의 개념을 학습하는데 도움이 될 것이다.

코드를 여러 번 작성해 보면서 check 배열로 true와 false를 저장하는 이유를 알고, combination 함수에 어떤 인자를 넘겨줘야 하는지 이해하면 학습 효과가 좋을 것이다.

특히, 조합을 구현한 알고리즘은 순열과는 달리 check 배열을 활용해서 방문 여부를 체크하지 않는다.

그래서 뽑았던 숫자를 다시 뽑지 않는 방법에 대해서 헷갈리기 쉽다.

그러므로 이 부분을 중점으로 생각하면서 코드를 작성하는 연습을 하면 좋겠다.