[ 순열과 조합 구현 ] 재귀를 통한 구현(3 - 중복조합) (C++)

순열과 조합 구현 (1), (2) 번 글에서는 순열과 조합에 대한 전반적인 개념과 구체적으로 어떻게 구현해야 하는지에 알 수

있었다.

[ 순열과 조합 구현(1) 보러가기 ]

[ 순열과 조합 구현(2) 보러가기 ]

지난 글에서는 중복을 허용하지 않는 가장 기본적인 순열과 조합에 대해서 알아보았다. 이번 글에서는

중복을 허용하는 중복 조합과 중복 순열에 대해서 알아보고자 한다.

[ 중복조합 & 중복순열 ? ]

먼저 중복조합과 조합, 중복순열과 순열의 차이점부터 알아보도록 하자.

조합은 순서에 상관없이 중복을 허용하지 않고 나올 수 있는 모든 수열을 조합이라고 하였고,

순열은 순서에 상관이 있고 중복을 허용하지 않고 나올 수 있는 모든 수열을 순열이라고 하였다.

그렇다면, 중복조합과 중복순열은 무엇일까?? 정말 말 그대로 중복을 허용한다는 의미이다.

중복조합은 조합에서 중복을 허용한다는 것, 중복순열은 순열에서 중복을 허용한다는 것이다.

즉, 우리가 알던 조합에서 { 1, 2, 3 } 중에 2개를 뽑는다고 하면

{ 1, 2 } , { 1, 3 } , { 2, 3 } 이렇게 총 3개를 구할 수 있었다.

하지만 중복 조합은 중복을 허용하기 때문에 뽑았던 카드를 다시 한번 뽑을 수 있는 것이다.

즉, {1, 1} , { 1, 2 } , {1, 3 } , {2, 2 }, {2, 3}, {3, 3} 이렇게 경우가 나오게 된다.

헷갈리지 말아야 할 것은, 중복조합이라고 해서 { 1, 2 }를 뽑아놓고 다시 { 2, 1 } 을 뽑을 수 있다 라는 의미가 아닌,

{1, 1} ,{ 2, 2 } 이런식으로 뽑았던 카드를 또 뽑을 수 있다는 의미이다. 헷갈리지 말자 !

그렇다면 중복조합은 코드로 어떻게 구현을 해야 하는지 알아보도록 하자.

[ 중복조합 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 5
using namespace std;
 
int Arr[MAX];
int Select[MAX];
 
void DFS(int Idx, int Cnt)
{
    if (Cnt == 3)
    {
        cout << " { ";
        for (int i = 0; i < 3; i++)
        {
            cout << Select[i] << " ";
        }
        cout << "} " << endl;
        return;
    }
 
    for (int i = Idx; i < MAX; i++)
    {
        Select[Cnt] = Arr[i];
        DFS(i, Cnt + 1);
    }
}
 
int main(void)
{
    for (int i = 0; i < MAX; i++) Arr[i] = i + 1;
    DFS(0, 0);
}

위의 코드는 5개의 숫자중에서 3개를 뽑는 중복조합 코드이다.

먼저 중복을 허용하지 않는 일반적인 조합의 코드와 차이점을 알아보자.

가장 큰 차이점이라면, 재귀호출하는 부분의 for문에 보면, "이미 선택했으니 지나가세요"를 의미하는 부분이 없어졌다.

이 코드는 중복을 허용하지 않는 조합 코드이다.

보면, if(Select[i] == true) continue; 의 부분이 사라졌고, Select[i] = true / false 해주는 부분도 사라졌다.

그렇다면, 조합에서 저 부분을 왜 구현했는지부터 다시한번 이해해보자. 우리는 뽑은 카드에 대해서는 다시는 뽑으면

안되기 때문에, 이미 뽑은 카드에 대해서는 지나가세요 ~, 뽑지 않은 카드는 뽑았다고 표시해주고, 뽑을 카드를 다시 뽑지 않았다고 표시해주면서 그 다음 조합을 구하기 위해서 Select[] 배열을 bool 형으로 사용하였다.

하지만, 이제는 중복조합이다. 카드를 중복해서 뽑아도 되기 때문에 위의 부분이 없어진 것이다. 뽑은 카드를 또 뽑아도 되기 때문에 뽑은 카드에 대해서 지나가세요~ 를 하지 않아도 된다는 말이다. 또한, 뽑은 카드에 대해서 표시를 해주는 과정 또한 필요가 없어지게 된다.

그렇다면, bool형이였던 Select[]배열이 int형으로 바뀌었을까??

이 부분은 본인이 가장 많이 사용하는 본인의 스타일이다. int형으로 바꿔주면서 값을 저장하는 것이다.

우리는 5개 중에 3개를 뽑아야 하고, 우리가 지금 뽑은 카드의 갯수는 Cnt라는 변수가 관리해준다고 알고 있을 것이다.

즉, Select[Cnt] = Arr[i] 라는 말은, "Cnt번째 뽑은 카드는 Arr[i] 입니다." 라는 의미이다.

조합을 제대로 이해했다면, 중복 조합은 훨씬 더 쉽게 이해했을 것이다. 또한, Idx와 Cnt의 역할은 일반조합을 구현할 때의

역할과 똑같으니 헷갈린다면 조합에 대한 글을 읽어보길 바란다 !

사실상, 중복조합은 조합을 완벽하게 이해했다면 쉽게 이해할 수 있을 거라 생각한다.

다음 글에서는, 중복순열에 대해서 알아보도록 하자 !