1. 조합 (Combination)
조합은 주어진 원소들 중에서 순서를 고려하지 않고 특정 개수의 원소를 선택하는 경우를 말합니다. 즉, 선택된 원소들의 순서가 중요하지 않으며, 같은 원소를 여러 번 선택할 수 없습니다.
예시:
주어진 원소 `{1, 2, 3}`에서 2개를 선택할 때:
- 가능한 조합은 `{1, 2}, {1, 3}, {2, 3}`입니다.
수학적 정의:
- `n`개의 원소 중에서 `r`개를 선택하는 조합의 수는 `C(n, r) = n! / (r! * (n - r)!)`입니다.
조합 구현:
- 조합을 구하는 방법은 순열과 달리 순서가 중요하지 않으므로, 중복을 피하면서 원소를 선택하는 방식으로 구현됩니다. 재귀적으로 원소를 선택하고, 선택된 원소를 포함한 조합을 탐색합니다. 백트래킹 방식을 사용합니다.
import java.util.*;
public class Combination {
public static void main(String[] args) {
int[] nums = {1, 2, 3}; // 조합을 구할 배열
int k = 2; // 선택할 원소의 수
List<List<Integer>> result = new ArrayList<>();
combine(nums, k, 0, new ArrayList<>(), result);
// 결과 출력
for (List<Integer> comb : result) {
System.out.println(comb);
}
}
// 조합을 구하는 함수
public static void combine(int[] nums, int k, int start, List<Integer> current, List<List<Integer>> result) {
// 현재 조합이 k개 원소를 선택했으면 결과에 추가
if (current.size() == k) {
result.add(new ArrayList<>(current));
return;
}
for (int i = start; i < nums.length; i++) {
current.add(nums[i]); // 원소를 선택
combine(nums, k, i + 1, current, result); // 다음 원소로 진행
current.remove(current.size() - 1); // 선택을 취소하고 백트래킹
}
}
}
2. 중복조합 (Combination with Repetition)
중복조합은 주어진 원소들 중에서 중복을 허용하여 선택하는 경우입니다. 즉, 같은 원소를 여러 번 선택할 수 있으며, 순서는 중요하지 않습니다.
예시:
주어진 원소 `{1, 2, 3}`에서 2개를 중복 허용하여 선택할 때:
- 가능한 중복조합은 `{1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {3, 3}`입니다.
수학적 정의:
- 중복조합의 경우, `n`개의 원소에서 `r`개를 중복 허용하여 선택하는 경우의 수는 `C(n + r - 1, r)`입니다.
중복조합 구현:
- 중복조합은 중복을 허용하면서 순서가 중요하지 않은 조합을 구하는 문제입니다. 백트래킹을 사용하여 구현할 수 있습니다.
import java.util.*;
public class RepeatedCombination {
public static void main(String[] args) {
int[] nums = {1, 2, 3}; // 중복조합을 구할 배열
int r = 2; // 선택할 원소의 수
List<List<Integer>> result = new ArrayList<>();
generateCombinations(nums, r, 0, new ArrayList<>(), result);
// 결과 출력
for (List<Integer> comb : result) {
System.out.println(comb);
}
}
// 중복조합을 구하는 함수
public static void generateCombinations(int[] nums, int r, int start, List<Integer> current, List<List<Integer>> result) {
if (current.size() == r) {
result.add(new ArrayList<>(current));
return;
}
for (int i = start; i < nums.length; i++) {
current.add(nums[i]);
generateCombinations(nums, r, i, current, result); // 동일한 원소를 다시 선택 가능
current.remove(current.size() - 1);
}
}
}
결론
- 조합은 주어진 원소들에서 중복 없이 순서와 관계없이 선택하는 경우에 사용됩니다.
- 중복조합은 주어진 원소들에서 중복을 허용하여 순서와 관계없이 선택하는 경우에 사용됩니다.
두 가지 모두 재귀적 방법을 사용하여 해결할 수 있으며, 각 문제에서 요구하는 조건에 맞게 구현을 선택해야 합니다.
참고
`Set`을 사용하는 경우:
- 중복을 제거해야 할 때: 중복된 원소를 허용하지 않고, 유일한 값만 저장하고자 할 때 (`Set`은 중복을 자동으로 제거).
- 순서가 중요하지 않을 때: 원소의 순서가 중요하지 않고, 유일한 값들만 필요할 때.
`List`를 사용하는 경우:
- 순서가 중요할 때: 원소의 순서가 중요한 경우 (예: 순열, 특정 순서대로 값 저장).
- 중복을 허용할 때: 중복된 원소를 포함해야 할 때 (`List`는 중복을 허용).
즉, 중복을 제거하고 순서가 중요하지 않으면 `Set`, 순서가 중요하거나 중복을 허용해야 하면 `List`를 사용하면 됩니다.