조합의 모든것 풀어봅시다

조합은 무엇일까요? 재귀를 이용하여 조합을 뽑기 전에 조합은 어떤 모양을 가지고 있는지

알아야 함으로 어떻게 생겼는지 먼저 알아봅시다.

 조합은  Combination 으로 nCr n개의 나열된 숫자에서 r개를 뽑는 것을 말합니다.

하지만 앞서있는 블로그에 순열의 모든것 풀어봅시다 에서 순열과 다른 점은

순서가 달라도 내용물이 같다면 같은 집합임으로 그 경우를 빼고 뽑아야 합니다. 그래서 

순열보다 반 정도가 적게 나오게 됩니다.

예를 들어 1, 2, 3, 4의 숫자에서 2개의 숫자를 뽑는다면 경우는 

노란 블록인 경우와 파란 블록 중 하나인 경우가 조합입니다. 그냥 쉽게 노란 블록이라고 보시면 되고 

파란 블록은 노란 블록가 위치만 다를 뿐 같은 내용물을 가지고 있으므로 같은 경우이기 때문에 제외하셔야 합니다.

문제를 보시면 더 이해가 될 것입니다. 문제를 봐보겠습니다.

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

불러오는 중입니다...

 

#include<stdio.h>
int N, M;
const int DSIZE = 8;
 
int D[DSIZE];
 
void init() {
    scanf("%d %d", &N, &M);
}
void dfs(int idx, int d){
    if (idx == M) {
        for (int i = 0; i < M; i++)printf("%d ", D[i]);
        printf("\n");
        return;
    }
    for (int i = d; i <= N; i++) {
 
            D[idx] = i;
            dfs(idx + 1, i + 1);
            D[idx] = 0;
    }
}
int main(void) {
    init();
    dfs(0,1);
    return 0;
}

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

15664번: N과 M (10)

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
const int DSIZE = 8;
const int inputSIZE = 8;
int D[DSIZE]; int input[inputSIZE];
int N, M;
void init() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) {
        scanf("%d", &input[i]);
    }
    sort(input, input + N);
}
void dfs(int idx, int d) {
    if (idx == M) {
        for (int i = 0; i < M; i++) printf("%d ", D[i]);
        printf("\n");
        return;
    }
    int before = 0;
    for (int i = d; i < N; i++) {
        if (before != input[i]) {
            before = input[i];
            D[idx] = input[i];
            dfs(idx + 1, i + 1);
            D[idx] = 0;
        }
    }
}
int main(void) {
    init();
    dfs(0, 0);
    return 0;
}

before변수를 두어 체크만 해주시고 가능한 조건이면 넣기만 하면됩니다.

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

15652번: N과 M (4)

#include<stdio.h>
#include<algorithm>
using namespace std;
const int DSIZE = 8;
int D[DSIZE];
int N, M;
void init() {
    scanf("%d %d", &N, &M);
}
void dfs(int idx) {
    if (idx == M) {
        for (int i = 0; i < M; i++)printf("%d ", D[i]);
        printf("\n");
    }
    for (int i = 1; i <= N; i++) {
        if (idx < M&&(idx==0||D[idx-1]<=i)) {
            D[idx] = i;
            dfs(idx + 1);
            D[idx] = 0;
        }
    }
}
int main(void) {
    init();
    dfs(0);
    return 0;
}

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

15657번: N과 M (8)

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
const int DSIZE = 8;
const int inputSIZE = 8;
int D[DSIZE];
int input[inputSIZE];
int N, M;
void init() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) {
        scanf("%d", &input[i]);
    }
    sort(input, input + N);
}
void dfs(int idx) {
    if (idx == M) {
        for (int i = 0; i < M; i++)printf("%d ", D[i]);
        printf("\n");
        return;
    }
    for (int i = 0; i < N; i++) {
        if (idx < M&&(idx==0||D[idx-1]<=input[i])) {
            D[idx] = input[i];
            dfs(idx + 1);
            D[idx] = 0;
        }
    }
}
int main(void) {
    init();
    dfs(0);
    return 0;
}

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

15666번: N과 M (12)

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
const int DSIZE = 8;
const int inputSIZE = 8;
int D[DSIZE];
int input[inputSIZE];
int N, M;
void init() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) {
        scanf("%d", &input[i]);
    }
    sort(input, input + N);
}
void dfs(int idx) {
    if (idx == M) {
        for (int i = 0; i < M; i++)printf("%d ", D[i]);
        printf("\n");
        return;
    }
int    before = 0;
    for (int i = 0; i < N; i++) {
        if (idx < M&&(idx==0||D[idx-1]<=input[i])&&before!=input[i]) {
            before = input[i];
            D[idx] = input[i];
            dfs(idx + 1);
            D[idx] = 0;
        }
    }
}
int main(void) {
    init();
    dfs(0);
    return 0;
}

조합의 마지막 문제!!!!!!

입력값에 같은 숫자 있는 경우 저렇게 같은 수이 상의 집합을 뽑는 소스에 

이전의 값을 before 변수에 넣고 같지 않을 때만 넣어주면 됩니다.

정말 쉽지 않나요? 저렇게 조건에 맞추어 생각하시고 조건을 주시면 간단합니다.

처음에는 물론 이해가 안 될 수 있지만 하다 보면 되고 ,

이런 말이 있지 않습니까? 어려운 일은 있을 수 있어도 하지 못하는 일은 없다는 말이 있습니다.

어려울 수 있습니다. 하지만 하지 못하는 건 아닙니다. 할 수 있습니다. 

오늘은 여기까지이고 긴 글 봐주셔서 감사합니다.