[알고리즘/개념/C++] 여러가지 방법으로 조합(Combination) 구현해보기

알고리즘 개념 정리글입니다. 이해가 힘드신 부분이거나, 명확하지 않은 부분에 대한 피드백은 언제나 환영합니다!

조합

조합은 의미적으로 보자면, 순열안에 있는 개념이다. $nPr$은 "n개 중 r개를 뽑아서, 줄세우는 경우의 수"라고 한다면, $nCr$은 "n개 중 r개를 뽑는 경우"이다.
하지만, 수학적으로 구하는 방법으로는 nPr이 훨씬 쉽기 때문에, nPr안에 nCr의 개념이 있다는 점을 이용해서 nCr을 구하는 방법을 정의한다.

$nPr = nCr \times n! , \therefore nCr = \frac{nPr}{n!}$

그래서, 경우의 수를 구하는 것 역시 Factorial만 있다면, 쉽게 구할 수 있다. 하지만, 이 방법 또한 순열을 구할때와 마찬가지로 , 컴퓨터에서 n!은 표현의 범위가 있기 때문에, 표현할 수 있는 범위가 그렇게 많지 않다.

재귀함수를 이용해서 조합의 수 구하기

조합은 순서를 바꾸는 경우를 같다고 생각하지 않기 때문에, "뽑는다"자체에만 집중해서 구현을 하면 된다. 요소를 직접 뽑아도 되지만, 인덱스를 기준으로 뽑는게 나중에 같은 요소가 있을 때, 헷갈리지 않는다.

#include<bits/stdc++.h>
using namespace std;

int n,r;

void printV(vector<int> vec){
	for(int i=0;i<vec.size();i++){
    	cout<<v[i]<<' ';
    }
    cout<< '\n';
}

void combi(int start,vector<int> res){
	if(res.size() ==r){
    	printV(res);
        return;
    }
    for (int i= start+1;i<n;i++){
    	res.push_back(i);
        combi(i,res);
        res.pop_back();
    }
}
int main(){
	cin>>n>>r;
    vector<int> v;
    combi(-1,v)
    return 0;
}

위의 코드는 매개변수를 줄이고, 인덱스를 기준으로 뽑은코드이다. 물론, 밑에처럼 요소를 기준으로 뽑아도된다.

#include<bits/stdc++.h>
using namespace std;

void printV(vector<int> res){
	for ( int i=0;i<res.size();i++){
    	cout<<res[i]<<" ";
    }
    cout<<'\n';
}

void makeCombination(vector<int> arr,vector<int> result,int start,int depth){
	if(result.size() == depth){
    	printV(res);
        return;
    }
    for (int i=start;i<arr.size();i++){
    	result[depth] = arr[i];
        makeCombination(arr,res,start+1,depth+1);
    }
	
}
int main(){
	cin>>n>>r;
    vector<int> arr;
    vector<int> res(r);
	for (int i=0;i<n;i++){
    	v.push_back(i);
    }
     makeCombination(arr,res,0,0);
	return 0;
}

Combination은 반복문도 괜찮다.

Combination은 3개 이하를 뽑는다면, 반복문을 쓰는게 좋을 수 있다. 왜냐하면, 보통은 재귀함수보다는 반복문이 더 짜기 쉽기 때문이다. 예를들어, 5개 중 2개를 뽑는 $5C2$를 구현한다고 하자. 그럼 아래와 같이 간단한 반복문 으로 구현할 수 있다.

#include <bits/stdc++.h>
using namespace std;

int main()
{
  int a[] = {1, 2, 3, 4, 5};
  for (int i = 0; i < 5; i++)
  {
    for (int j = i + 1; j < 5; j++)
    {
      cout << " " << i << " " << j << '\n';
    }
  }
  return 0;
}