조합 (코드 포함)

이제 순열을 배웠기 때문에 조합을 알아봅시다.

 

순열은 "순서"가 있었죠?

조합은 "순서가 없습니다!

그저 n개에서 r개를 뽑는게 다입니다.

순서를 지킬 필요가 없죠.

순서를 지킨다면 nPr(Permutation) 즉 순열을 사용하면 되며, 그게 아니라면 nCr(Combination)을 사용하면됩니다.

조합 공식

n개중에 순서없이 r을 뽑는다. 할 때,

예를 들어 3개중에 2개를 뽑는다라고 하면

n은 3이되며 r은 2가됩니다.

3! / 2!(3-2)!가 되며 3 * 2 * 1 / 2 * 1(1)이 됩니다.

그러면 분자에 2 * 1과 분모의 2 * 1은 나뉘어지어 사라지고 3 / 1 이되어 3개가 나온다라는 소리입니다.

쉽네요.

 

코드로 해볼까요?

#include <iostream>
#include <vector>

using namespace std;

int n = 3, k = 2, a[3] = { 1, 2, 3 };

void print(vector<int> vec)
{
    for (int i : vec)
        cout << i << " ";
        
    cout << '\n';
}

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

int main()
{
    vector<int> vec;
    combi(-1, vec);
    return 0;
}

 

3개 중에 2개를 뽑았을 때

결과물은 이렇습니다.

총 3개 맞네요.

 

그렇습니다 순서 상관없이 바로 뽑히는 애들입니다.

 

재귀함수로 해보았지만 중첩 for문을 이용하면 어떨까요?

오히려 더 쉬워요.

 

#include <iostream>

using namespace std;

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

 

 

그렇다면 조합에서

nCr 즉 3C2 라면 3개중에 2개를 뽑는다는거죠?

그렇다면 그렇다면 이건 어떨까요?

3C(3-2)는 3C1이죠?

그러면 3개중에 1개를 뽑는다라는 건데

3개중에 1개 뽑는것과 3개중에 2개를 뽑는것은 의미는 같습니다.

엥 이게 뭔소리죠?

봐봐요

예를 들어 9개중에 2개를 뽑는 것은!

9개 중에 7개를 뽑고 나머지가 9개중에 2개를 뽑은 것과 같겠죠?

그래서 공식은 이렇습니다.

nCr = nC(n-r)과 같다고 봅니다.

 

끄으으읕