[c++]조합

1. 조합

조합이란 수학에서 우리가 흔히 쓰는 combination이다. 즉 순서와 상관없이 전체n개 중 k를 뽑는 서로 다른 경우의 수를 의미한다. 조합과 순열은 알고리즘에서 완전탐색 문제를 해결하는데 많이 사용된다. 그렇다면 이러한 조합을 재귀함수로 구현하는 경우를 살펴보며 재귀함수의 동작원리 또한 살펴보겠다. 

 

2. 구현

#include <iostream>
#include <vector>
#include <algorithm>
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 << "\n";
}

void combi(int start, vector<int> b) {
	if (b.size() == k) {
		print(b);
		cout << "return\n";
		return;
	}// 기저사례
	for (int i = start + 1; i < n; i++) {
		cout << "b.push_back " << i << "\n";
		b.push_back(i);
		combi(i, b);
		cout << "b.pop\n";
		b.pop_back();
	}
}

int main() {
	combi(-1, b);
}

조합은 다음과 같이 구현된다. 기저 사례로 우리가 설정한 k개를 고르면 return 되고 vector의 사이즈가 b가 아니라면 계속해서 push_back후 재귀 함수를 호출해준다. 그렇다면 재귀함수가 어떤 방식으로 호출 되는 지 살펴보겠다. 

위의 결과를 살펴보면 함수는 이런식으로 호출된다. 

combi(0,b)->combi(1,b)->combi(2,b) ->return ->combi(2,b)나머지(pop) -> combi(3,b)->

return ->combi(3,b)나머지(pop)-> combi(4,b) -> return -> combi(4,b)나머지(pop)->(n == 4)

combi(1,b)나머지(pop)->combi(2,b)->combi(3,b)->return->combi(3,b)나머지(pop)->combi(4,b)->return->combi(4,b)나머지(pop)->combi(2,b)나머지(pop)->combi(3,b)->combi(4,b)->return->combi(4,b)나머지(pop)->combi(3,b)나머지(pop)->combi(4,b)-> combi(4,b)나머지(pop)->combi(0,b)나머지(pop)(for문 1루프 끝)

위의 결과를 살펴보면 재귀함수가 불림에 따라 for문에 조건에 의해 i가 1씩 증가하고 for문의 조건에 의해 i가 n-1이 되면 그 재귀를 종료하고 나머지 코드를 수행한다. 재귀는 이 처럼 분기와같이 뻗어 나간다.

 

위의 순서는 색깔별로 한 분기를 나타내며 한 분기를 모두 진행한 후 그 위를 탐색하는 것이 알고리즘에서 DFS와 비슷하다는 생각을 했다.