[개념정리] 조합(Combination) 직접 구현해보기

아래의 [백준] 14052번 문제를 풀다가 개념을 정리해보았다.

https://www.acmicpc.net/problem/14502

14502번: 연구소

 

주어진 숫자들에 대해서 조합을 하고, 조합된 숫자들에 대해서 문제를 풀어나가야 하는 상황에서 

STL을 사용해서 문제를 풀자니 코드 재활용이 안되고, 과정이 머릿속에서 그려지지 않을 것 같아서 

c++코드로 조합(Combination)을 구현해보았다. 

 

문제 상황

(1,4), (5,2), (9,4), (8,3) ... 와 같이 두개의 숫자로 이루어진 숫자쌍이 여러개 존재하는데, 이 중에서 딱 3쌍을 골라서

문제 풀이를 하는것. 

 

풀이 과정

모든 숫자 쌍을 vector<pair<int,int>> v;를 통해 v라는 벡터에 집어 넣었고, 

3쌍의 조합이 완성될 때마다 저장할 벡터를 vector<pair<int,int>> comb(3);을 통해서 comb이라는 벡터에 집어넣었다.

combination(v, comb, 3, 0, 0);을 통해서 직접 만든 함수 combination()를 호출했고, combination에서는 다음과 같이 동작한다.

여기서 3은 3개를 뽑는다는 의미이고, 첫번째 0은 조합 comb의 index, 두번째 0은 뽑을 원소를 선택하기 위해 v를 순회하는 index이다.

 
void combination(vector<pair<int, int>> v, vector<pair<int,int>> comb, int r, int index, int depth)
{
    if (r == 0)
    {
        //조합이 완성되면 수행할 코드
    }
    else if (depth == v.size()) // 계속 안뽑다가 r개를 채우지 못한 경우 --> 버린다.
    {
        return;
    }
    else
    {
        comb[index] = v[depth];
 
        // v[depth] 원소를 뽑는 경우
        combination(v, comb, r - 1, index + 1, depth + 1);
        
        // v[depth] 원소를 뽑지 않는 경우
        combination(v, comb, r, index, depth + 1);
    }
}