자주 사용하는 알고리즘 정리

주기적으로 눈에 익혀 원할 때 바로바로 사용할 수 있도록 정리

1. GCD 유클리드 호제법

int GCD(int a, int b){
        if(b==0) return a;
        else return GCD(b, a % b);
    }

//최소공배수는 (a*b)/GCD(a,b)

2. 소수 판별

// 제곱근을 이용한 방법
boolean is_Prime(int Number) {
 
	// 1 은 소수가 아니다.
	if(Number == 1){
		return false;	
	}
    
	// 2 ~ Number의 제곱근까지 중 나누어 떨어지는 약수가 있는지 판별
	// Number = 2 의 경우는 자연스럽게 for문을 검사하지 않게 됨
    
	for(int i = 2; i <= Math.sqrt(Number); i++) {
    
		if(N % i == 0) return false;
        
	}
    
	// 위 두 조건에 걸리지 않으면 소수다.
	return true;
}

// 시간복잡도 O(N√N)

// 에라토스테네스의 체
// 1 ~ Max 범위
 
// 소수인 수 = false
// 소수가 아닌 수 = true
 
public boolean[] make_prime(int Max) {
 
	boolean[] Prime = new boolean[Max + 1];	// 0 부터 시작하므로 +1
 
	// 0 과 1 은 소수가 아니므로 true
	Prime[0] = true;
	Prime[1] = true;
    
    
	for(int i = 2; i <= Math.sqrt(Max); i++) {
 
		// 이미 걸러진 배열일 경우 다음 반복문으로 건너뜀
		if(Prime[i] = true) {
			continue;
		}
		
		/*
		정석대로라면 j = i * 2 부터 시작이지만 
		이미 2의 배수가 걸러졌기때문에
		i 의 제곱수부터 시작해도 된다.
		*/
        
		for(int j = i * i; j < Max + 1; j = j + i) {
			Prime[j] = true;
		}
	}
 
	// 배열 index 가 소수라면 false 로, 아니라면 true 로 완성됨
    
	return Prime;
}
// 시간복잡도 O(N ㏒ (㏒ N))

3. 팩토리얼

static int fact(int n){
        if(n<=1)
            return n;
        else
            return fact(n - 1) * n;
    }

4. 유니온-파인드

public static void union(int a,int b){
        a = find(a);
        b = find(b);
        if( a!=b){
         parent[b]=[a]
    }
}

public static int find(int a){
        if(a = parent[a]){
         return a;
        else
         return parent[a] = find(parent[a]) 
    }
}