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;
}
