[알고리즘] 조합 (Combination)

mallin·2022년 1월 16일
algorithm
2

알고리즘

목록 보기
2/9
post-thumbnail

조합이란 ?

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)

조합에 대해서 본격적으로 들어가기 전에 점화식에 대해서 한 번 짚고 넘어가자.

점화식이란 ?

어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것 이다.
예를 들어 피보나치 수열을 재귀 함수로 구현할 때 아래와 같은 코드가 만들어 지는데 

function fibonacci(n) {
  if ( n <= 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

base case 가 되는 if 의 내용을 제외한 fibonacci(n - 1) + fibonacci(n - 2) 가 바로 피보나치 수열에 대한 점화식이 된다.
더 자세한 내용은 여기 블로그 참고 ❗️ 완전 정리 잘 되어 있다 !! ➡️ 점화식 (TIL 42일차)

조합의 점화식

조합의 점화식은 다음과 같다.

n-1Cr-1 + n-1Cr

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

➡️ 두 가지의 경우를 합쳐야 n개 중 하나를 뽑는 경우의 수가 나오게 된다
이렇게 글로만 봤을 땐 이해가 잘 안될 수도 있기 때문에 예시를 통해서 더 자세히 알아보자

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

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

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

조합 vs 순열

조합과 순열은 상당히 유사한데 차이점이라고 하면

조합은 순서와 상관없이 나열 하는 경우의 수
순열은 순서를 고려해 나열 하는 경우의 수 이다

예시를 들어보자면 [1,2,3] 이라는 배열이 있을 때 2개를 뽑는 경우의 수는

순열인 경우 경우의 수가 6가지
[1,2] / [1,3] / [2,1] / [2,3] / [3,1] / [3,2]

조합은 순서를 상관하지 않기 때문에 경우의 수가 3가지
[1,2] / [2,3] / [3,1]

가 나오게 된다

순열 관련된 포스팅은 [알고리즘] 순열 (Permutation) 를 참고

구현

① 재귀함수를 이용한 조합

위에서 사용한 점화식을 기반으로 재귀함수를 구현한다

#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;
}

2. 백트래킹을 이용한 조합

백트래킹이란?
현재 상태에서 가능한 모든 후보군을 따라 들어가며 해결책에 대한 후보를 구축해 나아가다 가능성이 없다가 판단되면 즉시 후보를 포기하면서 정답을 찾아가는 범용적인 알고리즘
EX) DFS (깊이 우선 탐색)

#include <iostream>
#include <vector>

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

using namespace std;

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

void combination_DFS(int index, int count) { // count개의 수를 이용해 조합을 만듬
    if (count == 3) {
        for (int i = 1; i <= MAX; i++) {
            if (visit[i] == true) // 조합과 순열의 차이 (조합은 중복 제거)
                cout << i << " ";
        }
        cout << endl;
        return;
    }
    
    for (int i = index; i <= MAX; i++) {
        // 이미 방문한 곳이라면 건너뛴다.
        if (visit[i] == true) continue;
            
        visit[i] = true; // 방문 표시를 남긴다.
        combination_DFS(i, count + 1);
        visit[i] = false; // 체크 취소 (다른 자식 노드를 체크하기 위해)
    }
}

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

3. STL 을 이용한 조합 (prev_permutation, next_permutation)

이름설명
next_permutation현재 나와 있는 수열에서 인자로 넘어간 범위에 해당하는 다음 순열을 구하고 true를 반환한다. 다음 순열이 없다면(다음에 나온 순열이 순서상 이전 순열보다 작다면) false를 반환.
prev_permutation현재 나와 있는 수열에서 인자로 넘어간 범위에 해당하는 이전 순열을 구하고 true를 반환한다. 이전 순열이 없다면(다음에 나온 순열이 순서상 이전 순열보다 크다면) false를 반환.

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()));
}

모든 조합을 구하려면 bool 배열의 초기 상태가 내림차순 정렬이여야 한다.
: true 가 false 보다 앞에 와야 한다.

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()));
}

모든 조합을 구하려면 bool 배열의 초기 상태가 오름차순 정렬이여야 한다.
: false 가 true 보다 앞에 와야 한다.

시간복잡도

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

관련 백준 문제

[백준/c++] 15650번 N과 M (2)

🙇🏻‍♀️ 레퍼런스

(C++) 조합(Combination) 구현하기
조합 알고리즘
점화식 (TIL 42일차)
[Algorithm] C++에서 next_permutation 함수(혹은 prev_permutation 함수)를 통해서 순열 구하기

profile
mallin
이전 포스트

[알고리즘] 순열 (Permutation)

다음 포스트

[알고리즘] 동적 계획법 (Dynamic Programming, DP)

0개의 댓글