(4장-2) 조합(Combination) 알고리즘이란?

위키백과에 따르면, 조합(Combination)은 서로 다른 n개의 원소 중에서 순서에 상관없이 r개를 선택하는 것을 의미합니다. 흔히 nCr로 표현할 수 있습니다. 코딩 테스트에서 조합은 흔하게 쓰이는 주제 중 하나입니다. 순서에 상관없이에 주의하세요.

 

 

안녕하세요. 지칸입니다.

 

오늘 설명할 알고리즘은 조합입니다.

삼성 SW 역량테스트에서 자주 사용되는 알고리즘 중 하나로 N개의 후보 중 최적의 M개를 선택하는 문제 등으로 자주 출제됩니다. 기본적으로 외울 정도로 익숙해야 하는 알고리즘 중 하나입니다.

 

1) 조합이란?

2) 구현하기

---

1) 조합이란?

N개의 원소 중 M개를 순서에 상관없이 나열하는 것을 의미하는 데 {1, 2, 3, 4}로 예를 들면 아래와 같습니다.

• {1, 2, 3}
• {1, 2, 4}
• {1, 3, 4}
• {2, 3, 4}

우리가 수학 시간에 배웠던 기억을 되살려보면 nCr = n-1Cr-1 + n-1Cr 로 표현된다는 걸 배웠을 겁니다.

이걸 풀어보면 재귀 함수로 구성할 수 있다는 걸 알 수 있습니다. 위 예로 이어서 들어보면 아래와 같습니다.

• 4C3 = 3C2 + 3C3
• 3C2 = 2C1 + 2C2

위 점화식 예시처럼 끝없이 재귀함수로 타고 내려가고  r==1일 때, n==r일 때 리턴합니다.

• r==1이면, n개 중 1개 를 선택하는 것이니 for문으로 n번 돌면서 한 번씩 선택하면 됩니다.
• n==r이면, n개 중 n개를 선택하는 것이니 전부 선택하면 됩니다.

---

2) 구현하기

코드로 위 예시를 살펴보겠습니다. 맨 처음 선택은 뒤에서부터 진행하고 있습니다.

#include <iostream>
#include <vector>
using namespace std;
vector<int> arr;
vector<int> flag;
vector<int> printV;
void printFun() {
	for (int i = 0; i < printV.size(); i++) {
		cout << printV[i] << " ";
	}
	cout << endl;
}
void comb(int n, int r) {
	if (n == r) {
		for (int i = 0; i < n; i++) {
			flag[i] = 1;
		}
		for (int i = 0; i < arr.size(); i++) {
			if (flag[i] == 1) printV.push_back(arr[i]); // 문제해결을 위한 응용 부분
		}
		printFun();  // 응용 부분,    바로 조합값을 출력하지 않고 따로 저장 후 printFun이라는 함수를 시행
		printV.clear(); // 응용 부분
		for (int i = 0; i < n; i++) {
			flag[i] = 0;
		}
		return;
	}
	if (r == 1) {
		for (int i = 0; i < n; i++) {
			flag[i] = 1;
			for (int j = 0; j < arr.size(); j++) {
				if (flag[j] == 1) printV.push_back(arr[j]);  // 응용 부분
			}
			printFun();  // 응용 부분
			printV.clear(); // 응용 부분
			flag[i] = 0;
		}
		return;
	}
	flag[n - 1] = 1;
	comb(n - 1, r - 1);
	flag[n - 1] = 0;
	comb(n - 1, r);
}
int main() {
	arr.push_back(1);
	arr.push_back(2);
	arr.push_back(3);
	arr.push_back(4);
	for (int i = 0; i < arr.size(); i++) {
		flag.push_back(0);
	}
	comb(4, 3);
	return 0;
}

printV 배열은 단순히 출력하려고 만든 배열이므로 큰 의미는 없습니다. printFun 동작처럼 조합을 찾았을 때 어떤 동작이 필요할 경우 내용을 넣어주시면 됩니다. 

 

flag배열은  arr 원소 중 현재 선택한 인덱스를 표기하기 위해 사용되었습니다. printFun을 호출할 때 항상 4개의 원소 중 3개는 flag에 1로 표시가 될 것입니다. 사용 후 flag를 0으로 초기화해주셔야 합니다.

 

 if문을 보시면 1)에서 설명한 것처럼 n==r, r==1 일 때 두 개로 구분하고 있습니다.

• r==1이란 말은 이미 r-1개는 선택된 상태라는 의미이기 때문에 for문을 돌면서 하나 선택 후 프린트, 방금 선택한 거 초기화, 그다음 for문 인덱스 이렇게 돌게 됩니다. 
• n==r일 때는 for문 돌면서 전부 선택 후 프린트, 다시 for문 돌면서 선택한 flag 초기화 이렇게 돌게 됩니다.

 

순열에 비하면 조금 코드가 길어지고 복잡해지죠? 그래도 이해하기 어렵진 않을 것으로 생각됩니다. 혹시 이해가 어려우시면 댓글 달아주세요. 단계별 변화를 보여드리며 좀 더 상세 설명하겠습니다.

 

이렇게 순열과 조합에 대해 공부해 봤습니다.