1. 조합이란?
조합은 요소들을 특정한 순서없이 선택하여 그 부분 집합을 만드는 것을 의미합니다. 조합은 순서가 중요하지 않은 경우에 사용됩니다.
ex. A, B, C의 모든 조합은 AB, AC, BC
n개의 요소에서 r개를 선택하여 나열하는 경우의 수는 다음과 같이 표현됩니다.
$nPr = {n!\over r!(n - r)!}$
2. C++로 나타낸 조합
1) 재귀 함수 이용
#include <iostream>
#include <vector>
using namespace std;
void combination(int start, vector<int> v, int n, int k) {
if (v.size() == k) {
for (int i : v) {
cout << i << " ";
}
cout << endl;
return;
}
for (int i = start + 1; i < n; i++) {
v.push_back(i);
combination(i, v, n, k);
v.pop_back();
}
return;
}
int main() {
int n = 5; // 전체 요소의 개수
int k = 3; // 조합의 크기
vector<int> v;
combination(-1, v, n, k);
return 0;
}
n은 전체 요소의 개수이고, k는 조합의 크기입니다.
- 만약 현재 선택된 요소들의 개수가 k와 동일하다면, 현재 조합을 출력하고 함수를 종료합니다.
- 그렇지 않은 경우, start 다음 인덱스부터 끝까지의 요소를 하나씩 선택하여 v에 추가한 후, 재귀적으로 함수를 호출합니다.
- 재귀 호출이 끝나면, 마지막에 선택한 요소를 v에서 제거하여 이전 상태로 돌아갑니다.
!! 여기서 나온 조합수들은 Index로 사용될 수 있습니다.
실행결과
2) for 다중루프 이용
#include <bits/stdc++.h>
using namespace std;
int n = 5;
int k = 3;
int main() {
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
for(int k = j + 1; k < n; k++){
cout << i << " " << j << " " << k << '\n';
}
}
}
return 0;
}
C
Contents