28.02_Algorithm with Math_코드 정리_22.09.29

>순열 코드

>조합 코드

public static ArrayList<String[]> combination(String[] str) {
    ArrayList<String[]> result = new ArrayList<>();
    //조합 특징1: 반복문의 시작이 이전 반복문 시작+1 이다.
    //이전 요소가 다시 뽑힐 필요가 없기 때문(순서가 필요없다는 뜻)
    //조합 특징2: 뽑고 싶은 만큼 반복문을 사용하면 된다.
    //현재 예시) 5C3; str 의 5개 요소에서 3개를 뽑는다.
    for(int i = 0; i < str.length; i++) {
        for(int j = i + 1; j < str.length; j++) {
            for(int k = j + 1; k < str.length; k++) {
                String[] input = new String[]{str[i], str[j], str[k]};
                result.add(input);
            }
        }
    }
    return result;
}

>소수 코드

public static boolean isPrime(int num) {
    // 0 과 1 은 소수가 아니다
    if(num < 2) {
        return false;
    }
    // 2 는 소수다
    if(num == 2) {
        return true;
    }

    for(int i = 2; i < num; i++) {
        // 소수가 아닐경우, num(본인) 제외 약수가 존재
        if(num % i == 0) {
            return false;
        }
    }
    // 위 반복문에서 약수를 갖고 있지 않는경우 소수다.
    return true;
}

>소스 코드(최적화)

public static boolean isPrimeExpert(int num) {
    if(num < 2) {
        return false;
    }
    // 제곱근 함수 : Math.sqrt()
    for(int i = 2; i <= Math.sqrt(num); i++) {
        if(num % i == 0) {
            return false;
        }
    }
    return true;
}
// N = p x q ( 1 <= p,q <= N)
// p가 증가하면 q는 감소하고, q가 증가하면 p가 감소한다.
// 위의 내용을 종합하면 p와 q는 √N을 기준으로 영역을 나눌 수 있다.
// 때문에 √N 이하까지만 검색해서 약수의 유무를 파악해도 똑같은 소수 판별 결과를 낼 수 있다.
// 하지만 시간 복잡도를 최적화하여 사용했기에 효율적인 검색 방법이다. O(√N)

>GCD

//조건: a > b
//유클리드 호제법
public static int gcd(int a, int b){
    while(b!=0){
        int r = a % b;
        a= b;
        b= r;
    }
    return a; //a,b는 결국 같은 수가 된다.
}
//유클리드 호제법_재귀 형식
static int GCD(int a, int b){
    if (a%b == 0) {
        return b;
    }
    return GCD(b, a % b);
}
//유클리드 호제법: 2개의 자연수의 최대공약수를 구하는 알고리즘
//a를 b로 나눈 나머지가 0이 될 때, a와 b를 나누는 수가 a와 b의 최대 공약수이다.

//*호제법 : 두 수가 서로 상대방 수를 나누어 결국 원하는 수를 얻는 알고리즘

>Divisor

>DivisorExpert

public static ArrayList<Integer> divisorExpert(int num) {
    ArrayList<Integer> temp = new ArrayList<>();
    for (int i = 1; i <= Math.sqrt(num); i++) {
        if (num % i == 0) { // 약수 중 작은 수 저장
            temp.add(i);
            if (num / i != i) { // 약수 중 큰 수 저장
                temp.add(num / i);
            }
        }
    }
    //ex) 100: [1, 100, 2, 50, 4, 25, 5, 20, 10]
    temp.sort(Comparator.naturalOrder());
    //ex) 100: [1, 2, 4, 5, 10, 20, 25, 50, 100]
    return temp;
}
//소수 구하기랑 같은 원리
//N = p x q 일 때, p랑 q는 √N을 기준으로 양쪽으로 나뉘며 반비례한다.
//위 같은 이유로 √N 까지만 반복문을 돌려도 짝이 되는 약수까지 구할 수 있다.