조합(Combination)
조합은 여러 개의 물건이나 숫자 중에서 몇 개를 뽑는 방법이에요. 여기서 중요한 점은 순서를 상관하지 않고 뽑는다는 거예요. 예를 들어, '1, 2, 3, 4'라는 숫자가 있을 때, 그중에서 두 개를 뽑는 모든 경우를 찾는 거예요. 조합은 물건이나 숫자의 순서가 중요하지 않아서 순열과는 조금 다르답니다!
조합을 어떻게 표현할까요?
- 조합은 수학 기호로 nCr이라고 써요. 여기서 n은 전체 숫자의 개수, r은 뽑을 숫자의 개수예요.
- 예를 들어, 4C2는 '4개의 숫자 중에서 2개를 뽑는다'는 뜻이에요.
조합의 공식
- 조합의 공식은 다음과 같아요: nCr = n! / (n-r)!r!
(여기서 !는 팩토리얼을 뜻해요. 팩토리얼은 그 숫자까지의 모든 수를 곱하는 거예요. 예를 들어, 3!는 3 x 2 x 1이에요.)
조합을 찾는 3가지 방법
- 재귀를 이용하는 방법
- 시작 위치(start)를 이용하는 방법
- Next Permutation을 이용하는 방법
각 방법을 하나씩 설명해볼게요!
1. 재귀 사용하기
이 방법은 재귀를 이용해서 숫자를 뽑을 때마다, 이 숫자를 뽑을지 말지를 결정하는 거예요. 마치 여러 색깔 공을 하나씩 보면서 '이 공을 뽑을까, 말까?' 하고 고민하는 것과 같아요.
import java.util.Arrays;
public class Combination {
public static int N; // 입력 데이터 수
public static int R; // 뽑을 데이터 수
public static int[] data; // 입력 데이터 배열
public static int[] selected; // 뽑은 데이터 배열
public static void main(String[] args) {
data = new int[] { 1, 2, 3, 4 };
N = data.length;
R = 2; // 2개를 뽑을 거예요
selected = new int[R];
findCombination(0, 0);
}
public static void findCombination(int count, int start) {
if (count == R) { // 2개를 다 뽑았다면
System.out.println(Arrays.toString(selected));
return;
}
for (int i = start; i < N; i++) {
selected[count] = data[i];
findCombination(count + 1, i + 1); // 다음 숫자부터 뽑기
}
}
}결과
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]이 방법은 색깔 공을 하나씩 보면서 선택하는 것과 비슷해요. 한 번 뽑은 공은 다시 뽑지 않고, 다음 공만 고르는 방식이죠!
2. 시작 위치(start) 사용하기
이번에는 start라는 변수를 이용해서 숫자를 뽑아볼 거예요. 이 변수는 현재 뽑은 숫자 다음부터만 숫자를 뽑도록 해줘서 중복이 생기지 않도록 해줘요.
import java.util.Arrays;
public class Combination {
public static int N; // 입력 데이터 수
public static int R; // 뽑을 데이터 수
public static int[] data; // 입력 데이터 배열
public static int[] selected; // 뽑은 데이터 배열
public static void main(String[] args) {
data = new int[] { 1, 2, 3, 4 };
N = data.length;
R = 2; // 2개를 뽑을 거예요
selected = new int[R];
findCombination(0, 0);
}
public static void findCombination(int depth, int start) {
if (depth == R) { // 2개를 다 뽑았다면
System.out.println(Arrays.toString(selected));
return;
}
for (int i = start; i < N; i++) {
selected[depth] = data[i];
findCombination(depth + 1, i + 1); // 다음 숫자부터 뽑기
}
}
}결과
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]이 방법은 한 번 뽑은 숫자 이후의 숫자들만 뽑기 때문에 중복 없이 빠르게 조합을 찾을 수 있어요. 마치 공을 차례로 뽑아 나가는 것처럼요!
3. Next Permutation 사용하기
이번에는 Next Permutation을 이용해서 조합을 찾아볼 거예요. 사전에서 단어를 찾는 것처럼, 숫자의 다음 순서를 차례로 찾아가면서 조합을 만들어내요.
import java.util.Arrays;
public class Combination {
public static int N; // 입력 데이터 수
public static int R; // 뽑을 데이터 수
public static int[] data; // 입력 데이터 배열
public static int[] selected; // 뽑은 데이터 배열
public static void main(String[] args) {
data = new int[] { 1, 2, 3, 4 };
N = data.length;
R = 2;
selected = new int[N];
// 첫 번째 조합을 만들기 위해 배열을 초기화
int cnt = 0;
while (++cnt <= R) {
selected[N - cnt] = 1; // 배열의 뒤에서부터 1로 채움
}
do {
for (int i = 0; i < N; i++) {
if (selected[i] == 1)
System.out.print(data[i] + " ");
}
System.out.println();
} while (nextPermutation());
}
private static boolean nextPermutation() {
int i = N - 1;
while (i > 0 && selected[i - 1] >= selected[i]) {
i--;
}
if (i == 0)
return false;
int j = N - 1;
while (selected[i - 1] >= selected[j]) {
j--;
}
swap(i - 1, j);
int k = N - 1;
while (i < k) {
swap(i++, k--);
}
return true;
}
private static void swap(int i, int j) {
int temp = selected[i];
selected[i] = selected[j];
selected[j] = temp;
}
}결과
1 2
1 3
1 4
2 3
2 4
3 4이 방법은 '다음 순서'를 찾아가며 조합을 만들어내요. 사전에서 단어를 하나씩 찾듯이, 숫자의 조합을 규칙에 따라 만들어내는 방식이에요!
부분집합(Subset / Powerset)
부분집합은 어떤 집합에서 일부를 선택하는 것을 말해요. 예를 들어, {1, 2, 3}이라는 숫자들이 있을 때, 이 숫자들로 만들 수 있는 모든 부분집합을 찾는 거예요. 여기서 중요한 건, 아무것도 선택하지 않는 공집합도 포함된다는 거예요. 그리고 이렇게 모든 부분집합을 모은 것을 멱집합(Powerset)이라고 해요.
부분집합의 예시
- 예를 들어, {1, 2, 3}이라는 숫자들이 있으면, 그 숫자들로 만들 수 있는 부분집합은:
- {}
- {1}
- {2}
- {3}
- {1, 2}
- {1, 3}
- {2, 3}
- {1, 2, 3}
이렇게 총 8개가 있어요. 숫자가 많아질수록 부분집합도 많아지죠!
부분집합을 구하는 방법
부분집합을 구하는 방법에는 몇 가지가 있어요. 그중에서 두 가지 방법을 설명해줄게요!
- 재귀와 visited 배열을 사용하기
- 비트마스크를 사용하기
1. 재귀와 visited 배열 사용하기
이 방법은 숫자를 하나씩 보면서 이 숫자를 포함할지, 말지를 결정하는 거예요. 마치 여러 색깔 공을 뽑을 때, '이 공을 선택할까 말까?' 하고 생각하는 것과 같아요.
public class Subset {
public static int N; // 입력 데이터 수
public static int[] data; // 입력 데이터 배열
public static boolean[] visited;
public static void main(String[] args) {
data = new int[] { 1, 2, 3 };
N = data.length;
visited = new boolean[N];
findSubset(0);
}
public static void findSubset(int depth) {
if (depth == N) { // 모든 숫자를 다 확인했을 때
for (int i = 0; i < N; i++) {
if (visited[i])
System.out.print(data[i] + " ");
}
System.out.println(); // 줄 바꾸기
return;
}
// 현재 숫자를 선택하는 경우
visited[depth] = true;
findSubset(depth + 1);
// 현재 숫자를 선택하지 않는 경우
visited[depth] = false;
findSubset(depth + 1);
}
}결과
1 2 3
1 2
1 3
1
2 3
2
3이 방법은 공을 하나씩 보면서 선택할지 말지를 정해요. 그리고 모든 조합을 찾아가며 부분집합을 만드는 방식이에요. 마치 한 상자에서 여러 개의 공을 꺼내는 것처럼, 뽑았다가 다시 제자리에 넣는 것을 반복하는 거예요!
2. 비트마스크(bitmask) 사용하기
이번에는 비트마스크라는 방법을 사용해 볼 거예요. 이 방법은 마치 여러 개의 스위치를 켜고 끄는 것처럼, 숫자를 선택했는지 안 했는지를 비트로 표현해요. 비트는 컴퓨터가 사용하는 0과 1의 값이에요.
public class Subset {
public static int N; // 입력 데이터 수
public static int[] data; // 입력 데이터 배열
public static void main(String[] args) {
data = new int[] { 1, 2, 3 };
N = data.length;
findSubset(0, 0);
}
public static void findSubset(int depth, int bit) {
if (depth == N) { // 모든 숫자를 다 확인했을 때
for (int i = 0; i < N; i++) {
if ((bit & (1 << i)) != 0) // 비트로 선택 여부 확인
System.out.print(data[i] + " ");
}
System.out.println(); // 줄 바꾸기
return;
}
// 현재 숫자를 포함하는 경우
findSubset(depth + 1, bit | (1 << depth));
// 현재 숫자를 포함하지 않는 경우
findSubset(depth + 1, bit);
}
}결과
1 2 3
1 2
1 3
1
2 3
2
3이 방법은 스위치를 켜고 끄는 것처럼 각 숫자가 선택되었는지를 비트로 표현해요. 예를 들어, 숫자가 선택되었으면 스위치를 켠 상태(1), 선택되지 않았으면 꺼진 상태(0)로 표시하는 거예요. 그래서 컴퓨터가 이 정보를 빠르게 확인할 수 있어요!
정리
조합(Combination)은 여러 가지 물건이나 숫자를 순서 없이 뽑는 다양한 방법이에요. 초등학생 친구들도 쉽게 이해할 수 있죠! 숫자나 물건을 줄 세우는 순열과는 다르게, 순서 없이 선택하는 것이 조합의 매력이에요. 이렇게 숫자 놀이를 하듯이 조합을 찾아보며 재미있게 배울 수 있답니다!
부분집합(Subset)은 어떤 집합에서 일부를 선택하는 다양한 방법이에요. 초등학생 친구들도 쉽게 이해할 수 있죠! 숫자나 물건을 골라보며 이렇게 다양한 조합을 찾을 수 있어요. 그리고 선택한 것들로 만들어진 전체를 멱집합이라고 불러요. 숫자 놀이처럼 부분집합을 구해보며 재미있게 배워보세요!
