[알고리즘/C++] 조합

조합은 "순서가 없는" 뽑기

 

예를들어, 1,2,3,4,5 중에 3개를 뽑는 조합을 모두 찾아야 한다면

1,2,3 / 1,2,4 / 1,2,5 / 1,3,4 / 1,3,5 / 1,4,5 / 2,3,4 / 2,3,5 / 2,4,5 / 3,4,5

총 10개가 된다.

여기서 1,2,3 세개가 뽑힌 것에서는 순서가 없다. (2,1,3 이든 3,2,1 이든 똑같은 경우로 따짐)

 

만약 1,2,3,4,5 중에 5개를 뽑는 조합을 찾아야 한다면

1,2,3,4,5가 모두 뽑힌 딱 한 경우 밖에 없다.

3,2,1,5,4 와 같이 순서가 바뀐 경우도 같은 경우인 것이다.

 

조합은 중첩for문으로 구현이 가능하다.

- 조합 코드

#include <iostream>
#include <vector>

using namespace std;
vector<int> v{ 1,2,3,4,5 };
int n = v.size();

int main() {
	for (int i = 0; i < n; i++) { 
		for (int j = 0; j < i; j++) { // for(int j = i+1; j<n; j++) 도 가능
			for (int k = 0; k < j; k++) { // for(int k = j+1; k<n; k ++)
				cout << i << " " << j << " " << k << '\n';
			}
		}
	}
	return 0;
}

 

이런 식으로 3개를 뽑는다면 for문을 3개를 써야한다.

그런데, 4개를 뽑는 다거나 그 이상으로 더 많은 개수를 뽑는다면 for문을 더 많이 중첩해야한다.

그렇게 되면 시간이 오래 걸릴 수 있다.

그래서 조합은 재귀함수로 구현하는 것이 권장된다고 한다.

재귀함수로 구현하는 코드는 다음 게시글에 정리할 것이다.

(한 두개 뽑는 경우라면 for문으로 간단하게 구현해도 OK) 

 

- 조합 공식

 

위 공식에 대입해서 조합의 개수가 몇개가 나오는지 계산할 수 있다.