1. 집합
특정 조건에 맞는 원소들의 모임
HashSet 내장 기능 사용한 경우
public class Main {
public static void main(String[] args) {
// 1. 자바에서 집합 사용(HashSet)
HashSet set1 = new HashSet();
set1.add(1); set1.add(1); set1.add(1); // 여러번 add 해도 1은 한번만 추가됨
set1.remove(1);
set1.size(); // 크기 출력
set1.contains(2); // 특정 값 포함하는 지 또한 확인 가능(boolean)
// 2. 교집합
HashSet a = new HashSet(Arrays.asList(1,2,3,4,5));
HashSet b = new HashSet(Arrays.asList(2,4,6,8,10));
a.retainAll(b); // a에 교집합의 원소만 남음 a = [2,4];
// 3. 합집합
a.addAll(b); // a = [1,2,3,4,5,6,8,10]
// 4. 차집합
a.removeAll(b); // a = [1,3,5]
}
}public class MySet {
ArrayList<Integer> list;
MySet(){
this.list = new ArrayList<>();
}
MySet(int[] arr){
this.list = new ArrayList<Integer>();
for(int item: arr){
this.list.add(item);
}
}
public void add(int x){
for(int item : this.list){
if(item == x){
return;
}
}
this.list.add(x);
}
// 교집합(HashSet 메서드와 다르게 기존 값을 바꾸지 않게 만듬
public MySet retainAll(MySet b){
MySet result = new MySet();
for(int itemA : this.list){
for(int itemB : b.list){
if (itemA == itemB){
result.add(itemA);
}
}
}
return result;
}
// 합집합
public MySet addAll(MySet b){
MySet result = new MySet();
for(int itemA : this.list){
result.add(itemA);
}
for(int itemB : this.list){
result.add(itemB);
}
return result;
}
// 차집합
public MySet removeAll(MySet b){
MySet result = new MySet();
for(int itemA:this.list){
boolean containFlag = false;
for(int itemB:b.list){
if(itemA == itemB){
containFlag = true;
break;
}
}
if(!containFlag){
result.add(itemA);
}
}
return result;
}
}2. 경우의 수
어떤 사건에서 일어날 수 있는 경우의 가짓수
동전을 던지는 사건 : 경우의 수 2
주사위를 던지는 사건 : 경우의 수 6
합의 법칙 : 사건 A 또는 사건 B가 일어날 경우의 수
ex) 두 개의 주사위를 던졌을때 합이 3 또는 4의 배수일 경우의 수
n(A U B) = n(A) + n(B) - n(A ∩ B);
곱의 법칙 : 사건 A와 사건 B가 동시에 일어날 경우의 수 -> n(A x B)
ex ) 두개의 주사위 a,b를 던졌을 때 a는 3의 배수, b는 4의 배수인 경우의 수
n(A x B) = n(A) x n(B) = 2x1
public class Main {
public static void main(String[] args) {
// 1. 합의 법칙
// 주사위 2개를 던졌을때 합이 3 또는 4의 배수일 경우
int[] dice1 = {1,2,3,4,5,6};
int[] dice2 = {1,2,3,4,5,6};
int nA = 0; int nB = 0; int nAandB = 0;
// 기본 풀이
for(int item1: dice1){
for(int item2: dice2){
if((item1 + item2) % 3 == 0){
nA += 1;
}
if((item1 + item2) % 4 == 0){
nB += 1;
}
if((item1 + item2) % 12 == 0){ // 최소 공배수
nAandB += 1;
}
}
}
System.out.println("결과 : " + (nA + nB - nAandB));
// HashSet 이용
HashSet<ArrayList> allCase = new HashSet<>();
for(int item1 : dice1){
for(int item2 : dice2){
if((item1 + item2) % 3 == 0 || (item1 + item2) % 4 == 0){
ArrayList list = new ArrayList(Arrays.asList(item1, item2));
allCase.add(list);
}
}
}
System.out.println("결과 : " + allCase.size());
// 곱의 법칙(두개의 주사위 a,b를 던졌을 때 a는 3의 배수, b는 4의 배수인 경우의 수)
nA = 0;
nB = 0;
for(int item1 : dice1){
if(item1 % 3 == 0) {
nA++;
}
}
for(int item1 : dice2){
if(item1 % 4 == 0){
nB++;
}
}
System.out.println(nA * nB);
}
}최대 공약수, 최소공배수, 약수 구하는 메서드
// 약수, 최대공약수,최소공배수 구하기
// 활용) 1-10의 수 중 A의 약수 또는 B의 약수인 경우의 수
// 활용) 1-10의 수 중 A의 약수이면서 B의 약수인 경우의 수
public class Practice {
//약수
public ArrayList getDivisor(int num){
ArrayList result = new ArrayList();
for(int i = 1; i <= (int) num/2; i++){ // 절반까지만 for문 돌린 이유 잘 생각하자!
// ( num / 2 에서 num말고 약수가 될수있는 가장 큰수는 num /2)
if(num % i == 0){
result.add(i);
}
}
result.add(num);
return result;
}
// 최대 공약수 (GCD : Greatest Common Denominator)
public int getGCD(int numA, int numB){
int gcd = -1;
ArrayList divisorA = this.getDivisor(numA);
ArrayList divisorB = this.getDivisor(numB);
for(int itemA : (ArrayList<Integer>)divisorA){
for(int itemB : (ArrayList<Integer>)divisorB){
if (itemA == itemB){
if(itemA > gcd) gcd = itemA;
}
}
}
return gcd;
}
// 최소 공배수(LCM : The Lowest Common Multiple) -> 두 수를 곱한 뒤 최대공약수로 나누어 주면 됨
public int getLCM(int numA, int numB){
int lcm = -1;
int gcd = this.getGCD(numA, numB);
if(gcd != -1){
lcm = numA * numB / gcd;
}
return lcm;
}
}3.순열
팩토리얼 : 1에서 n까지 모든 자연수의 곱(n!)
public class Main {
public static void main(String[] args) {
//1. 팩토리얼
int n = 5;
int result = 1;
for(int i = 1; i <= n; i++){
result *= i;
}
System.out.println("result = " + result);
// 스트림으로 팩토리얼 구현
System.out.println(IntStream.rangeClosed(2,n).reduce(1, (x,y) -> x * y));
// 2. 순열
//5명을 3줄로 세우는 경우의 수
n = 5; int r = 3; result = 1;
for(int i = n; i >= n-r+1; i--){
result *= i;
}
// 3. 중복 순열
// 서로 다른 4개의 수 중 2개를 뽑는 경우(중복 허용)
n = 4; r = 2; result = 1;
for(int i = 0; i < r; i++){
result *= n;
}
System.out.println("result = " + result);
System.out.println(Math.pow(n, r));
// 4. 원순열
n = 3; result = 1;
for(int i = 1; i < n; i++){
result *= i;
}
}
}public class Practice1 {
// arr안의 숫자를 이용하여 r자리 자연수를 만드는 방법(순서 O, 중복 X) 각 결과를 출력하기
void permutation(int[] arr, int depth, int n, int r){
// depth는 자릿수
if(depth == r){
for(int i = 0; i < r; i++){
System.out.print(arr[i] + " ");
}
System.out.println();
return;
}
for(int i = depth; i < n; i++){
swap(arr,depth,i);
permutation(arr, depth+1, n, r);
swap(arr,depth,i);
}
}
// 배열로 자릿수 계속 이동시키기(특정 자릿수의 숫자와 특정 인덱스에 있는 값 바꿈)
void swap(int[] arr, int depth, int idx){
int tmp = arr[depth];
arr[depth] = arr[idx];
arr[idx] = tmp;
}
public static void main(String[] args){
// Test code
int[] arr = {1,2,3,4};
Practice1 p = new Practice1();
p.permutation(arr, 0, 4, 3);
}
}위 재귀과정 다시 한번 이해해보고 코드로 직접 구현해보자!
우선 여기서 depth란 함수가 현재 몇째짜리 숫자를 처리하고있는지 나타내는 숫자라고 생각
-> divide and conquer 관점에서 접근하자
첫번째 swap은 해당 depth 자리에 숫자를 고정?하는 느낌이라고 생각하자!
두번째 swap 함수는 반복문에서 바꾼 순서를 다시 원래대로 되돌리기 위해 호출
-> 즉 depth 자리에 고정된 숫자를 원래 대로 되돌려 놓은 후 그다음 반복문의 첫번째 swap을 통해 해당 depth 자리에 다른 숫자를 고정
위 문제에 대한 다른 해결 방법(마찬가지로 재귀 사용)
import java.util.Arrays;
public class Practice2 {
void permutation(int[] arr, int depth, int n, int r, boolean[] visited, int[] out){
if(depth == r){
System.out.println(Arrays.toString(out));
return;
}
for(int i = 0; i < n; i++){
if(visited[i] != true){
visited[i] = true;
out[depth] = arr[i];
permutation(arr, depth+1, n, r, visited, out);
visited[i] = false;
}
}
}
public static void main(String[] args){
//test code
int n = 4;
int r = 3;
int[] arr = {1,2,3,4};
boolean[] visited = new boolean[n];
int[] out = new int[r];
Practice2 p = new Practice2();
p.permutation(arr,0,n,r,visited,out);
}
}순서 예시
- permutation 함수가 depth=0, visited={false, false, false, false}, out={0, 0, 0}으로 호출됩니다.
- for 루프에서 i=0인 경우 visited[0]을 true로 변경하고 out[0]에 arr[0] 값을 할당합니다.
- permutation 함수를 depth=1, visited={true, false, false, false}, out={1, 0, 0}으로 재귀호출합니다.
- for 루프에서 i=0인 경우 visited[0]이 이미 true이므로 건너뜁니다.
- for 루프에서 i=1인 경우 visited[1]을 true로 변경하고 out[1]에 arr[1] 값을 할당합니다.
- permutation 함수를 depth=2, visited={true, true, false, false}, out={1, 2, 0}으로 재귀호출합니다.
- for 루프에서 i=0인 경우 visited[0]이 이미 true이므로 건너뜁니다.
- for 루프에서 i=1인 경우 visited[1]이 이미 true이므로 건너뜁니다.
- for 루프에서 i=2인 경우 visited[2]을 true로 변경하고 out[2]에 arr[2] 값을 할당합니다.
- permutation 함수를 depth=3, visited={true, true, true, false}, out={1, 2, 3}으로 재귀호출합니다.
- depth 값이 r과 같으므로 out 배열을 출력하고 재귀호출을 끝냅니다.
위와같은 순서가 계속 이어짐
4.조합
public class Practice {
static int getCombination(int n, int r){
int pResult = 1;
// nPr
for(int i = n; i >= n-r+1; i--){
pResult *= i;
}
int rResult = 1;
// r!
for(int i = 1; i <= r; i++){
rResult *= i;
}
return pResult / rResult;
}
public static void main(String[] args){
// 1. 조합, 서로 다른 4명 중 주번 2명을 뽑는 경우
int n = 4;
int r = 2;
System.out.println("결과 : " + getCombination(4,2));
// 2. 중복 조합, 후보자 2명, 유권자 3명일때 무기명 투표 경우의 수(중복 허용)
n = 2; r = 3;
System.out.println("결과 : " + getCombination(n+r-1, r));
}
}public class Practice2 {
// arr안의 숫자를 이용하여 r자리 자연수를 만드는 방법(순서 X, 중복 X) 각 결과를 출력하기
// ex : 1,2,3,4의 경우 만들어 질수 있는 수 -> 123, 124, 134, 234 (4가지)
void combination(int[] arr, boolean[] visited, int depth, int n, int r){
if(r == 0){
for(int i = 0; i < n; i++){
if(visited[i]){
System.out.println(arr[i] + " ");
}
}
System.out.println();
return;
}
if(depth == n){
return;
}
visited[depth] = true;
combination(arr, visited, depth+1, n, r-1);
visited[depth] = false;
combination(arr, visited, depth+1, n, r);
}
public static void main(String[] args){
int[] arr = {1,2,3,4};
boolean[] visited = {false, false, false, false};
Practice2 p = new Practice2();
p.combination(arr,visited,0,4,3);
}
}이 부분도 재귀식 잘 이해하기!
Journey for Backend Developer