[C++] 조합 (Combination) 구할 수 있는 알고리즘

개념

n개의 값 중에서 r 개의 숫자의 순서를 고려하지 않고 나열한 경우의 수, 순열은 반대로 고려한다.

 

예시)

 

[1,2] 와 [2,1] 이 있을 때 동일하게 여긴다는 의미

계산식으로는 nCr 이라고 표현한다.
nCr
= nPr / r!
= n! / ((n-r)! * r!)

예시로 서로 다른 3개의 숫자(1,2,3) 중 중복되지 않으면서 순서와 관계 없이 2개를 뽑는다고 가정해보자

3C2
= 3! / 1! * 2!
= 3! / 2!
= (3x2x1) / (2x1)
= 3

로 총 3개의 경우의 수가 나오게 된다 (1,2 / 1,3 / 2,3)

 

조합의 점화식

 

n-1Cr-1 + n-1Cr

1. n-1Cr-1 : 어떤 특정한 원소를 포함시키고 뽑았을 때
2. n-1Cr : 어떤 특정한 원소를 포함시키지 않고 뽑았을 때

예시)
{1,2,3} 에서 3C2 조합

1뽑기 
- 2뽑기 ➡️ 🌟 {1,2} 조합 완성 종료 
- 2안뽑기
    - 3뽑기 ➡️ 🌟 {1,3} 조합 완성 종료 
    - 3안뽑기 ➡️ 끝까지옴 종료 

1안뽑기
- 2뽑기
    - 3뽑기 ➡️ 🌟 {2,3} 조합 완성 종료 
    - 3안뽑기 ➡️ 끝까지 옴 종료 
- 2안뽑기
    - 3뽑기 ➡️ 끝까지 옴 종료 
    - 3안뽑기 ➡️ 끝까지 옴 종료 

구현

재귀함수

#include <iostream>
#include <vector>

using namespace std;

int R;
vector<int> cout_arr(9);

/**
 arr = 대상 배열
 comb = 출력 배열
 r = 남은 뽑아야 할 갯수
 index = comb 의 인덱스
 depth = 대상 배열에서 뽑을 원소를 결정하는 인덱스
 */
void Combination(vector<int> arr, vector<int> comb, int r, int index, int depth) {// depth == 점화식의 n역할
    if (r == 0) {                       // 뽑아야할 갯수가 모두 찬 경우에는 comb 에 들어있는 값 모두 출력
        for(int i = 0; i < R; i++) cout << comb[i] << " ";
        cout << endl;
    } else if (depth == arr.size()) {   // 뽑을 원소 인덱스가 대상 배열의 마지막까지 온 경우 return
        return;
    } else {
        
        // arr[depth] 를 뽑은 경우
        comb[index] = arr[depth];
        
        // cout << "Combination1 comb["<<comb[0]<<","<<comb[1]<<","<<comb[2]<< "] / r="<<r-1<<", index="<<index+1<<", depth="<<depth+1<<endl;
        Combination(arr, comb, r - 1, index + 1, depth + 1); // n-1Cr-1: 특정 원소를 뽑은 경우

        // cout << "Combination2 comb["<<comb[0]<<","<<comb[1]<<","<<comb[2]<< "] / r="<<r<<", index="<<index<<", depth="<<depth+1<<endl;
        
        // arr[depth] 를 뽑지 않은 경우
        Combination(arr, comb, r, index, depth + 1); // n-1Cr: 특정 원소를 뽑지 않은 경우
    }
}

int main() {
    vector<int> arr = {1, 2, 3, 4, 5};      // n = 5
    cout << "[1,2,3,4,5] 의 배열에서 몇개를 뽑을지 입력해주세요 : ";
    cin >> R;
    Combination(arr, cout_arr, R, 0, 0);    // 5Cr
    return 0;
}

백트래킹

#define MAX 6 // 1부터 5까지 수의 순열을 구한다.

int visit[MAX]; // 방문 여부를 저장하는 배열

void combination_DFS(int index, int count) { // count개의 수를 이용해 조합을 만듬
	if (count == 3) {
		for (int i = 0; i < MAX; i++) {
			if (visit[i]) // 조합과 순열의 차이 (조합은 중복 제거)
				cout << i << " ";
		}
		cout << endl;
		return;
	}

	for (int i = index; i < MAX; i++) 
	{
		// 이미 방문한 곳이라면 건너뛴다.
		if (visit[i]) continue;

		visit[i] = true; // 방문 표시를 남긴다.
		combination_DFS(i, count + 1);
		visit[i] = false; // 체크 취소 (다른 자식 노드를 체크하기 위해)
	}
}

int main() {
	combination_DFS(1, 0);
	return 0;
}

STL (prev_permutation, next_permutation)

 

prev_permutation

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	const int r = 2;
	vector<char> arr{'a', 'b', 'c', 'd'};
	vector<bool> temp(arr.size(), false);
	
    // 앞부터 r개의 true가 채워진다. 나머지 뒤는 false.
    // {true, true, false, false}
	for(int i = 0; i < r; i ++) 
		temp[i] = true;
	do {
		for (int i = 0; i < arr.size(); ++i) {
			if (temp[i] == true)
				cout << arr[i] << ' ';
		}
		cout << endl;
	} while (prev_permutation(temp.begin(), temp.end()));
}

 

next_permutation

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    const int r = 2;
    
    vector<char> arr{'a', 'b', 'c', 'd'};
    vector<bool> temp(arr.size(), true);
    
    // 뒤에 false가 n-r개 채워지고 뒤에 true 가 r개 채워진다.
    // {false, false, true, true}
    for(int i = 0; i < arr.size() - r; i ++) 
        temp[i] = false;
 
    do {
        for (int i = 0; i < arr.size(); ++i) {
            if(temp[i] == true) 
                cout << arr[i] << " ";
        }
        cout << endl;
    } while (next_permutation(temp.begin(), temp.end()));
}

 

시간 복잡도) 

재귀호출 시 2번의 함수를 호출하기 때문에 O(2n)
2n = (1+1)n = nC0 + nC1+nC2+...+nCn

 

출처