[문제해결기법02] 뽑기 - 조합/순열

 

1. 개념 정리

조합 : 순서가 상관없음

순열 : 순서가 상관있음

중복 : 같은 아이템을 여러 번 뽑을 수 있는지 (중복조합 / 중복순열)

 

 

 

2. 문제 해결 방법

- k : 앞으로 뽑아야 할 크기

- Trivial Case : k가 0일 때

- Recursive Case (if k > 0) : 앞으로 K 개를 더 뽑아야 하므로 일단 1개를 뽑고 같은 함수를 이용해 k-1개를 더 뽑는다.

 

 

3. 예시

1) 공뽑기 : A, B, C, D, E, F,G가 적혀 있는 공 7개에서 3개를 뽑는 경우를 구하라

=> 순서가 상관없고 중복이 없으므로 "조합" 문제이다.

#include <stdio.h>

void pick(int n, int* bucket, int bucketSize, int k, char* balls){
    int i, lastIndex,smallest, item;
    if(k == 0){
        for(i=0; i<bucketSize; i++){
            printf("%c ", balls[bucket[i]]);
        }
        printf("\n");
        return;
    }
    
    lastIndex = bucketSize - k - 1;
    
    if(bucketSize == k){
        smallest = 0;
    } else {
        smallest = bucket[lastIndex] + 1;
    }
    
    for(item=smallest; item<n; item++){
        bucket[lastIndex+1] = item;
        pick(n, bucket, bucketSize, k-1, balls);
    }
}

int main(void) {
    
    int n = 7;
    char balls[7] = {'A','B','C','D','E','F','G'};
    int bucket[3];
    
    pick(n, bucket, 3, 3, balls);
    
    
    return 0;
}

 

 

 

 

2) 배우들 중 n명을 뽑아서 최우수, 우수상을 수여하기로 한다. 1명은 단 하나의 상만 받을 수 있다.

배우는 공유, 김수현, 송중기, 지성, 현빈 5명 중에서 선택한다고 하자. 어떤 경우가 가능한가?

=> 순서가 중요하고, 중복이 허용되지 않으므로 "순열" 문제이다.

 

#include <stdio.h>

int isIn(int* bucket, int size, int num){
    int i;
    for(i=0; i<size; i++){
        if(bucket[i] == num)
            return 1;
    }
    return 0;
}

void pick(int n, int* bucket, int bucketSize, int k, char balls[][10]){
    int i, lastIndex, item;
    if(k == 0){
        for(i=0; i<bucketSize; i++){
            printf("%10s", balls[bucket[i]]);
        }
        printf("\n");
        return;
    }
    
    lastIndex = bucketSize - k - 1;
    
    for(item=0; item<n; item++){
        if(!isIn(bucket, lastIndex+1, item)){
            bucket[lastIndex+1] = item;
            pick(n, bucket, bucketSize, k-1, balls);
        }
    }
}

int main(void) {
    
    int n = 5;
    char actors[5][10] = {"공유", "김수현", "송중기","지성", "현빈"};
    
    
    int bucket[2];
    
    pick(n, bucket, 2, 2, actors);
    
    
    return 0;
}

 

 

 

3) 4진법으로 만들 수 있는 n자리 수를 모두 나열하는 프로그램 작성하시오

입력 : 3  (3자리 수)

출력 : 000, 001, ..., 333 으로 나오면 된다.

=> 순서가 중요하고, 중복이 가능하므로 "중복순열" 문제이다. 

#include <stdio.h>

void pick(int n, int* bucket, int bucketSize, int k, int* balls){
    int i, lastIndex, item;
    if(k == 0){
        for(i=0; i<bucketSize; i++){
            printf("%d", balls[bucket[i]]);
        }
        printf("\n");
        return;
    }
    
    lastIndex = bucketSize - k - 1;
    
    for(item=0; item<n; item++){

        bucket[lastIndex+1] = item;
        pick(n, bucket, bucketSize, k-1, balls);
    
    }
}

int main(void) {
    
    int n = 4;
    int num[4] = {0,1,2,3};
    
    int bucket[3];
    
    pick(n, bucket, 3, 3, num);
    
    
    return 0;
}

 

 

 

4) 1부터 n까지의 연속되어 있는 수와 +/-를 이용해서 만들 수 있는 모든 수식을 그 결과와 함께 나열하시오

- 입력 : 2

- 출력:

 + 1 + 2 = 3

+ 1 -2 = -1

-1 + 2 = 1

-1 -2 = -3

 

=> 1과 2는 그대로 있고, +와 -를 이용해 중복순열을 처리하는 문제이다.

#include <stdio.h>

int charToInt(char x, int sum, int n){
    if(x == '+'){
        sum += n;
    } else {
        sum -= n;
    }
    return sum;
}

void func(int n, char bucket[2], int bucketSize, int k, char *balls){
    
    int i, j;
    int balls_idx = bucketSize - k;
    
    if(k == 0){
        int sum = 0;
        for(j=0; j<bucketSize; j++){
           
            printf("%c", balls[j]);
            printf("%d", j+1);
            sum = charToInt(balls[j], sum, j+1);
            
        }
        printf("=%d\n", sum);
        return;
    }
    
    for(i=0; i<bucketSize; i++){
        balls[balls_idx] = bucket[i];
        func(n, bucket, bucketSize, k-1, balls);
    }
}

int main(void) {
    
    char bucket[2] = {'+','-'};
    
    char answer[2];
    
    int n;
    
    scanf("%d", &n);
    
    func(n, bucket, 2, n, answer);
    
    
    return 0;
}

 

 

 

 

 

5) 1000,5000,10000원 짜리 지폐로 입력값을 만들 수 있는 모든 방법을 출력하시오

입력 : 6000

출력 :

- 1000 1000 1000 1000 1000 1000

- 5000 1000

 

=> 순서가 중요하지 않고, 중복을 허용하므로 "중복조합"이다. 

#include <stdio.h>

int sumBalls(int *balls, int ballSize){
    int i, sum = 0;
    for(i=0; i<ballSize; i++){
        sum += balls[i];
    }
    return sum;
}

void func(int input, int *bucket, int bucketSize, int k, int *balls, int ballSize){
    int i, j;
    
    int sum_balls;
    sum_balls = sumBalls(balls, ballSize);
    
    if(sum_balls == input){
        for(j=0; j<ballSize; j++){
            printf("%d ", balls[j]);
        }
        printf("\n");
        return;
    } else if(sum_balls > input){
        return;
    }
    
    for(i=k; i<bucketSize; i++){
        balls[ballSize] = bucket[i];
        func(input, bucket, bucketSize, i, balls, ballSize+1);
    }
    
}

int main(void) {
    
    int moneys[3] = {1000,5000,10000};
    int answer[1000];
    int input;
    
    scanf("%d", &input);
    
    func(input, moneys, 3, 0,  answer, 0);
    
    return 0;
}