[C언어] 조합과 중복조합

조합

---

(1) 조합 _ nCr

- 서로 다른 n개 중에서 r개(n≥r)를 뽑는 경우

- 경우의 수에서 순서를 고려하지 않는 경우를 말한다

- ex) 0~8 까지의 숫자 중에서 3개의 숫자를 조합으로 뽑는 경우 ( 0 1 2 ) / (1 2 0) / ( 1 0 2 ) 는 1가지 경우

- 알고리즘을 짤 때 항상 오름차순 / 내림차순으로 뽑아서 중복 방지

​

0

1

3

가능

1

0

3

불가능

 

 

- 오름차순의 경우 ( 0 1 3 ) 은 가능하지만 ( 1 0 3 ) 은 불가능하기 때문에 같은 수의 조합을 방지할 수 있다

 

 

 

 

 

조합 알고리즘 핵심

---

- 조합 알고리즘에서는 item과 bucket을 사용 ( 상황에 따라 item과 bucket을 어떻게 정하는지가 핵심 포인트 )

​- item : 뽑을 수 있는 숫자 / 같은 특성을 갖고 있는 것들의 집단

→ 오늘 조합 예제에서 item은 0부터 n까지 총 item개만큼의 수를 뽑아야 한다는 것을 의미

( ex) int item = 5;    // 0~4까지 총 5개의 수를 뽑아야 한다는 것을 의미 )

 

- bucket : item에서 뽑은 것( 값 자체 / 해당 값의 index )을 저장하는 곳

 

 

 

 

 

 조합 예제 코드

---

Q. 0~4까지 총 5개의 숫자 중 3개를 뽑아 모든 경우의 수를 출력하는 프로그램을 작성하라 (중복허용X)

​

- 5개 중 3개를 뽑아야 하므로 조합과 중복조합 두가지 선택지가 있지만

- 중복을 허용하지 않기 때문에 조합을 사용하여 푸는 문제다!!

 

// 조합 예시 _ 5C3 
#include <stdio.h>
#include <stdlib.h>

/*
    n = item 정보
    bucket = 뽑은 숫자를 담을 배열
    bucketSize = bucket에 대한 정보(배열의 크기)
    k = 앞으로 뽑아야 할 개수
*/
void pick(int n, int* bucket, int bucketSize, int k) { 
	int i, lastIndex, smallest;
	lastIndex = bucketSize - k - 1; // 가장 최근에 뽑힌 수가 저장된 위치 index

	if (k == 0) { // 다 뽑으면 출력하고 출력 마치면 다시 for문으로 돌아가기
		for (i = 0; i < bucketSize; i++) 
			printf("%d ", bucket[i]);
		printf("\n");	
		return; // 무한루프 방지
	}

	if (k == bucketSize)
		smallest = 0; 
	else
		smallest = bucket[lastIndex] + 1; // 조합은 가장 마지막에 뽑힌 수보다 큰 수를 뽑는다

	for (i = smallest; i < n; i++) {
		bucket[lastIndex + 1] = i; 
		pick(n, bucket, bucketSize, k - 1); // k-1 = 앞으로 뽑아야 할 개수를 하나 감소
	}
	return;
}
int main(void) {
	int n = 5; // item 정보
	int bucket[3]; // 뽑은 숫자를 담을 곳

	pick(n, bucket, 3, 3); // 조합 알고리즘
	return;
}

 

코드 결과

 

- 5C3 = 10이므로 총 10가지 경우의 수를 만족하고 모든 경우의 수가 올바르게 출력된 걸 확인할 수 있다

 

 

 

 

​

중복조합

---

(1) 중복조합 _ nHr

- 논리흐름은 조합과 유사

- item에서 값을 뽑아 bucket에 담을 때 오름차순(내림차순)이지만, 같은 것도 뽑을 수 있다

​

중복조합	조합
같은 item을 여러번 뽑아 bucket에 담을 수 있다 → 마지막에 뽑은 item보다 크거나 같은 것을 뽑는다	item에서 뽑은 수는 한 번만 bucket에 담을 수 있다 → 마지막에 뽑은 item보다 큰 것을 뽑는다

 

 

 

 

 

 

중복조합 예제 코드

---

Q. 0~4까지 총 5개의 숫자 중 3개를 뽑아 모든 경우의 수를 출력하는 프로그램을 작성하라 (중복허용O)

​

- 5개 중 3개를 뽑아야 하므로 조합과 중복조합 두가지 선택지가 있지만

- 중복을 허용하고 있기 때문에 중복조합을 사용하여 푸는 문제다!!

​

// 중복조합 예시 _ 5H3
#include <stdio.h>
#include <stdlib.h>

/*
    n = item 정보
    bucket = 뽑은 숫자를 담을 배열
    bucketSize = bucket에 대한 정보(배열의 크기)
    k = 앞으로 뽑아야 할 개수
*/
void pick(int n, int* bucket, int bucketSize, int k) { 
	int i, lastIndex, smallest;
	lastIndex = bucketSize - k - 1; // 가장 최근에 뽑힌 수가 저장된 위치 index

	if (k == 0) { // 다 뽑으면 출력하고 출력 마치면 다시 for문으로 돌아가기
		for (i = 0; i < bucketSize; i++)
			printf("%d ", bucket[i]);
		printf("\n");
		return; // 무한루프 방지
	}

	if (k == bucketSize)
		smallest = 0;
	else
		smallest = bucket[lastIndex]; // 가장 최근에 뽑은 값과 같거나 큰 값을 뽑는다 (조합과의 차이점)

	for (i = smallest; i < n; i++) {
		bucket[lastIndex + 1] = i;
		pick(n,bucket, bucketSize, k - 1); // 앞으로 뽑아야 할 개수를 하나 감소시켜준다
	}
	return;
}
int main(void) {
	int n = 5; // item 정보
	int bucket[3]; // 뽑은 숫자를 담을 곳

	pick(n, bucket, 3, 3); // 중복 조합 알고리즘
	return 0;
}

 

코드 결과

 

- 5H3 = 35이므로 총 35가지 경우의 수를 만족하고 모든 경우의 수가 올바르게 출력된 걸 확인할 수 있다

 

 

오늘은 item과 bucket을 활용하여 조합과 중복조합 프로그램을 작성해보는 방법을 배워봤다!

​

오늘의 공부 끝 :)