[기초 수학] 집합과 경우의 수

|  집합(Set)

✏️ 개념 정리 

특정 조건에 맞는 원소들의 모임

 

- 특징

중복되지 않은 수들을 한 곳에 모아놓는 것으로, 자바에서는 Set을 사용해 중복데이터를 거를 수 있다.

 

- 종류

종류	기호	HashSet 메소드
교집합	A ∩ B	a.retainAll(b);
합집합	A ∪ B	a.addAll(b);
차집합	A  -  B	a.removeAll(b);
여집합	Ac	-

 

💻 구현하기

[ HashSet 구현해보기 ]

	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.HashSet;
	import java.util.List;
	class MyHashSet{
	ArrayList<Integer> list;
	MyHashSet(){
	this.list = new ArrayList<>();
	}
	MyHashSet(int[] arr) {
	this.list = new ArrayList<>();
	for (int data : arr) {
	// 기존 데이터 확인 (중복 삭제)
	if (list.contains(data)) {
	continue;
	}
	list.add(data);
	}
	}
	public void add(int data) {
	if (this.list.contains(data)) {
	return;
	}
	this.list.add(data);
	}
	// 교집합 - retainAll
	public MyHashSet retainAll(List<Integer> comp){
	MyHashSet result = new MyHashSet();
	for (Integer data : this.list) {
	if (comp.contains(data)) {
	result.list.add(data);
	}
	}
	return result;
	}
	// 합집합 - addAll
	public MyHashSet addAll(List<Integer> comp) {
	MyHashSet result = new MyHashSet();
	result.list = (ArrayList<Integer>) this.list.clone();
	for (Integer data : comp) {
	if (result.list.contains(data)) {
	continue;
	}
	result.list.add(data);
	}
	return result;
	}
	// 차집합 - removeAll
	public MyHashSet removeAll(List<Integer> comp) {
	MyHashSet result = new MyHashSet();
	for (Integer data : this.list) {
	if (!comp.contains(data)) {
	result.list.add(data);
	}
	}
	return result;
	}
	}
	public class SetReview {
	public static void main(String[] args) {
	// 집합 (Set)
	// 1. HashSet의 retainAll(), addAll(), removeAll()을 사용
	System.out.println("==HashSet==");
	HashSet<Integer> set1 = new HashSet<>(Arrays.asList(1, 2, 3, 4, 5));
	// 교집합
	set1.retainAll(Arrays.asList(4, 5, 6, 7, 8));
	System.out.println("교집합 : " + set1);
	// 합집합
	set1.addAll(Arrays.asList(1, 2, 3, 4, 5, 6));
	System.out.println("합집합 : " + set1);
	// 차집합
	set1.removeAll(Arrays.asList(4, 5, 6, 7, 8));
	System.out.println("차집합 : " + set1);
	// 2. 직접 구현
	int[] arr = new int[]{1, 2, 3, 4, 5};
	MyHashSet set2 = new MyHashSet(arr);
	// 교집합
	set2 = set2.retainAll(Arrays.asList(4, 5, 6, 7, 8));
	System.out.println("교집합 : " + set2);
	// 합집합
	set2.addAll(Arrays.asList(1, 2, 3, 4, 5, 6));
	System.out.println("합집합 : " + set2);
	// 차집합
	set2.removeAll(Arrays.asList(4, 5, 6, 7, 8));
	System.out.println("차집합 : " + set2);
	}
	}

view raw SetReview.java hosted with ❤ by GitHub

 

|  경우의 수

✏️ 개념 정리 

어떤 사건에서 일어날 수 있는 경우의 가짓수 : n(A)

종류	내용	기호	예시
합의 법칙	A와 B의 분리된 집단에 관한  어떤 사건의 경우의 수를 구할 때 * 단 두 집단의 합은 전체 집단이어야 한다.	n(A ∪ B) = n(A) + n(B) - n(A ∩ B)	- 남(5명)/여(3명) 집단이 있을 때, 나열할 수 있는 모든 경우의 수  - 주사위 두 개를 던졌을 때, 전체 합이 3의 배수 또는 4의 배수가 나오는 모든 경우의 수
곱의 법칙	A와 B의 사건이 동시에 일어날 때 = A와 B의 사건이 연달아서 일어나며, 모든 사건이 끝나지 않았을 때	n(A x B) = n(A) x n(B)	- 주사위와 동전을 동시에 던졌을 때, 나올 수 있는 모든 경우의 수 - 주사위 두 개를 던졌을 때,  하나는 3의 배수 하나는 4의 배수가 나오는 모든 경우의 수

 

(1) 약수 

- 6의 약수는 1,2,3,6

- N의 약수를 코드로 구할 때 루프를 사용한다면 N/2만큼만 루프를 돌려 나누어떨어지는 수를 구하고, 마지막으로 자기 자신을 더해주면 된다 (why? 2로 나누었을 때 절반까지만 나눠질것)

 

(2) 최대공약수

- A와 B의 약수 중 가장 큰 공통된 수

 

(3) 최소공배수 

- A와 B의 배수 중 가장 작은 공통된 수

- 최소공배수 = A x B / A와 B의 최대공약수 

 

 

💻 구현하기 

[ 경우의 수 - 합의 법칙과 곱의 법칙 ]

 

	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.HashSet;
	public class NumOfCasesReview {
	public static void main(String[] args) {
	// 1. 경우의 수
	// 1-1. 합의 법칙
	// 두 개의 주사위를 던졌을 때 합이 3 또는 4의 배수인 경우의 수
	// 식 ) n(A) + n(B) - n(A ∩ B)
	int[] dice1 = {1, 2, 3, 4, 5, 6};
	int[] dice2 = {1, 2, 3, 4, 5, 6};
	int nA = 0; //합이 3의 배수일 때 경우의 수
	int nB = 0; //합이 4의 배수일 때 경우의 수
	int nAandB = 0; //합이 12의 배수일 때 경우의 수
	for (int itemA : dice1) {
	for (int itemB : dice2) {
	if ((itemA + itemB) % 3 == 0) {
	nA++;
	} else if ((itemA + itemB) % 4 == 0) {
	nB++;
	} else if ((itemA + itemB) % 12 == 0) {
	nAandB++;
	}
	}
	}
	System.out.println("result = " + (nA + nB - nAandB));
	// HashSet을 사용하여 합의 법칙을 충족하는 두 수의 집합 구하기
	// ** HashSet 안에 ArrayList를 넣으면 두 수의 순서도 일치해야 중복으로 간주한다.
	HashSet<ArrayList<Integer>> allCase = new HashSet<>();
	for (int itemA : dice1) {
	for (int itemB : dice2) {
	if ((itemA + itemB) % 3 == 0 || (itemA + itemB) % 4 == 0) {
	allCase.add(new ArrayList<Integer>(Arrays.asList(itemA, itemB)));
	}
	}
	}
	System.out.println("allCase = " + allCase);
	// 1-2. 곱의 법칙
	// 두 개의 주사위 a , b를 던졌을 때 a는 3의 배수, b는 4의 배수인 경우의 수
	// 식 ) n(A) * n(B)
	nA = 0;
	nB = 0;
	for (int itemA : dice1) {
	if (itemA % 3 == 0) {
	nA++;
	}
	}
	for (int itemB : dice2) {
	if (itemB % 4 == 0) {
	nB++;
	}
	}
	System.out.println("result = " + (nA * nB));
	}
	}

view raw NumOfCasesReview.java hosted with ❤ by GitHub

 

[ 약수, 최대공약수, 최소공배수 구하기 ]

 

	import java.util.ArrayList;
	public class DenomiReview {
	// 약수
	public ArrayList getDivisor(int num) {
	ArrayList result = new ArrayList();
	for (int i = 1; i <= (int)num/2; i++) {
	if (num % i == 0) {
	result.add(i);
	}
	}
	result.add(num);
	return result;
	}
	// 최대 공약수
	// GCD: the Greatest Common Denominator
	public int getGCD(int numA, int numB) {
	int gcd = -1;
	// numA와 numB의 각각의 약수들을 구한다.
	ArrayList dA = getDivisor(numA);
	ArrayList dB = getDivisor(numB);
	// 두 리스트 가장 큰 공통된 수를 찾는다.
	for (int itemA : (ArrayList<Integer>) dA) {
	for (int itemB : (ArrayList<Integer>) dB) {
	if (itemA == itemB) {
	if (gcd < itemA) {
	gcd = itemA;
	}
	}
	}
	}
	return gcd;
	}
	// 최소 공배수
	// LCM: the Lowest Common Multiple
	public int getLCM(int numA, int numB) {
	int lcm = -1;
	// 최소 공배수 공식 : 두 수를 곱한 값에 최대공약수를 나눈다
	int gcd = getGCD(numA, numB);
	if (gcd != -1) { // 예외처리 - 최대 공약수를 구할 수 없는 경우도 염두하여야 한다.
	lcm = (numA * numB) / gcd;
	}
	return lcm;
	}
	public static void main(String[] args) {
	// Test code
	int number1 = 10;
	int number2 = 6;
	Practice p = new Practice();
	ArrayList l1 = p.getDivisor(number1); // 10: 1, 2, 5, 10
	ArrayList l2 = p.getDivisor(number2); // 6: 1, 2, 3, 6
	System.out.println("l1 = " + l1);
	System.out.println("l2 = " + l2);
	System.out.println("최대 공약수: " + p.getGCD(number1, number2));
	System.out.println("최대 공배수: " + p.getLCM(number1, number2));
	}
	}

view raw DenomiReview.java hosted with ❤ by GitHub