[Algorithm][Combination]조합

추상적 자료형(Abstract data type)과 자료구조(Data structure)는 엄밀히 말하면 다르다.

가령 스택의 경우는 추상적 자료형이다. 그 이유는 리스트(List)는 정의만 존재하고 구현은 사용자 마음이다.

그러나 만약 누군가가 연결리스트(Linked List), 혹은 배열리스트(Array List, Vector)를 말한다면 그건 자료구조인 셈이다.

그러나 이런 구분이 애매한 녀석들도 존재하기는 한다.

스택(Stack)같은 녀석이 그 정체인데 스택은 추상적 자료형으로 분류되는게 맞으나 사실상 자료구조라고도 볼 수 있다.

왜냐하면 스택을 구현하는 방식이 배열과 연결리스트 두가지가 존재하긴 하지만 사실상 무조건 배열을 쓰는게 이득이기 때문이다.

그래서 필자의 포스팅에서는 추상적 자료형과 자료구조를 엄밀히 구분하지 않고 모두 자료구조라 논하겠다.

참고:

이 사이트의 예제 문제는 백준 사이트(https://www.acmicpc.net/)를 참조합니다.

선수 개념:

[Recursive]재귀 함수

알고리즘 문제에서 조합과 순열문제는 유명하다.

이는 다른 알고리즘에 근간이 되기도 한다. 우리는 먼저 조합을 해보도록하자.

조합에 대해서 모르는 사람은 거의 없겠지만 먼저 조합을 설명하자면

"n개의 원소에서 k개를 순서와 상관없이 뽑는 경우"이다.

여기서 중요한건 순서가 상관이 없다.

1 2 3 4 5에서 2 5를 고른 경우와 5 2를 고른 경우는 같은 경우라고 가정한다.

알고리즘에서 흔히 묻고싶은 종류는 두가지가 있다.

바로 조합의 갯수와 조합의 나열이다.

갯수를 묻는 문제와 나열의 묻는 문제는 사실상 다른 문제이다. 물론 같은 솔루션으로 푸는것도 가능은 하다.

우리는 먼저 나열 하는 법 부터 해보도록하자.

#include <stdio.h>

#define MAXSIZE 1001
int N, K;
int arr[MAXSIZE];
int res[MAXSIZE];
int cnt;

void print_arr() {
    for (int k = 1; k <= K; k++) {
        printf("%d ", res[k]);
    }
    printf("\n");
}

void comb(int n, int k) {
    cnt++;
    if (k > K) {
        print_arr();
        return;
    } else if (n > N) {
        return;
    }
    res[k] = arr[n];
    comb(n + 1, k + 1);
    comb(n + 1, k);
}

int main() {
    scanf("%d %d", &N, &K);
    for (int i = 1; i <= N; i++) {
        arr[i] = i;
    }
    comb(1, 1);
    printf("cnt : %d", cnt);
    return 0;
}

N과 K는 N개중에 K를 고르는 경우라고 할 수 있다.

배열 arr는 1보다 크고 N보다 작은 자연수로 미리 초기화 시킨다.

cnt는 디버깅용 숫자로 사실 필요하진 않으니 무시해도된다.

실수를 줄이기 위해서 배열의 인덱스 0은 쓰지 않고 진행하겠다.

N의 크기는 1000개 보다 작다고 가정한다. 더 필요하다면 더 쓰면된다.

comb는 재귀로 구현되게 된다.

comb만 중심적으로 보도록 하자.

void comb(int n, int k) {
    cnt++;
    if (k > K) {
        print_arr();
        return;
    } else if (n > N) {
        return;
    }
    res[k] = arr[n];
    comb(n + 1, k + 1);
    comb(n + 1, k);
}

cnt는 디버깅용 코드로 사실 필요 없는 숫자이다.

중요한건 로직이다. 조합의 특징이라면 특정 숫자를 쓸수도, 안쓸수도 있다는 것이다.

즉 이분법적인 사고를 한다는 것이다.

이 사고는 밑에 두 재귀를 통해서 알 수 있다.

res[k] = arr[n];
comb(n + 1, k + 1);
comb(n + 1, k);

k는 현재 내가 넣는 배열의 인덱스 이다.

만약 k가 3이라면 n개 중에서 3개를 뽑는 경우이다.

여기서 n과 k가 함께 증가한다는 것은 현재 값을 넣는 것이다.

그러나 n만 증가하고 k를 증가하지 않을 경우 현재 값을 넣었을 지라도 다시 k에서 값을 덧쓰게된다.

f (k > K) {
    print_arr();
    return;
} else if (n > N) {
    return;
}

멈춰야할 base 캐이스는 두 종류이다.

첫번째는 k의 갯수를 다 썼을 경우이다.

즉 배열을 모두 채운 상황이므로 출력을 해주면된다.

그런데 k의 갯수를 다 채우지 못한 상태에서 n을 다 소진한경우,

이는 더이상 k를 채울 방법이 없으므로 우리가 원하는 상황이 아니다.

따라서 이 경우는 버린다.

그럼 실행결과를 보도록하자.

5 3

5개 중에서 3개를 고르는 경우를 보도록 하자.

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
cnt : 51

결과 모든 값을 다 출력할 수 있다.

만약 역순으로 출력하고 싶다면 코드를 살짝 바꾸면된다.

이 combination출력은 부르트포스이므로 모든 경우를 몽땅 확인하게 된다.

따라서 시간 복잡도는 n^n이 되게된다. 물론 실제 걸리는 시간은 훨씬 적지만 시간복잡도가 높다는건 변하지 않는다.

5개에서 3개를 뽑는 경우는 고작 10가지 밖에 안되지만 실제로 도는 횟수는 51개나 되게 된다.

comb(n + 1, k + 1);
res[k] = arr[n];
comb(n + 1, k);

위의 경우 역순으로 출력하게된다.

조합의 갯수를 구하는 방법은 조합의 나열에서 연결된다.

사실 여러분은 이미 조합의 갯수를 구할줄 안다.

#include <stdio.h>

int N, K;
int res;
int cnt;

void comb(int n, int k) {
    cnt++;
    if (k > K) {
        res++;
        return;
    } else if (n > N) {
        return;
    }

    comb(n + 1, k + 1);
    comb(n + 1, k);
}

int main() {
    scanf("%d %d", &N, &K);
    comb(1, 1);
    printf("%d\n",res);
    printf("cnt : %d", cnt);
    return 0;
}

조합의 나열을 구하는 방법에서 로직을 좀만 손보면 순쉽게 구할 수 있다.

N과 K에 각각 5와 3을 넣었을 때의 결과를 보도록하자.

10
cnt : 51

뭐 이렇게 구하는건 어렵지 않지만 아무래도 조금 찝찝할 수는 있다.

이는 조합의 기본정의 때문이다.

모두가 아는 조합 공식인데 이 공식을 보면 실제로는 n팩토리얼을 구하고 r팩토리얼을 구한후 n-r팩토리얼을 구하면된다.

위의 모든것을 구하는 공식은 n+k인데 k는 n보다 무조건적으로 작거나 같으므로 n이라고 할수있다.

즉 시간복잡도가 n이기 때문에 직접적으로 저 공식을 대입하는게 낫지 않느냐는 것이다.

물론 일반적으로 생각하면 그렇다...

하지만 이방식을 실제로 쓰기에는 조금 부담이 되는 문제가 있는데 그 이유는 이걸 계산하는 놈이 컴퓨터이기 때문이다.

13!값은 6227020800로 62억이다. 즉 int형의 값을 넘어서게 된다.

그럼 long long형을(java의 long형)쓰면 안되나 하고 물을 수 있다.

70!값은 11978571669969891796072783721689098736458938142546425857555362864628009582789845319680000000000000000이다.

이 범위는 long long형까지 넘어서게된다.

즉 우리는 100팩토리얼도 사실상 제대로 구할수 없다는 것이다.

그럼 다른 방법으로 값을 미리 나누는 방법은?

근데 그렇게 나누게 되면 float형으로 떨어지게되면서 값의 손실이 생기게 된다는 문제점이 있다.

이 문제를 해결할 수 있는 방법이 바로 파스칼의 삼각형을 이용한 Dynamic Programming을 이용한 방법이다.

그 부분은 Dynamic Programming에서 다루도록 하겠다.