hyeoneee's blog

소수는 1과 나 자신으로만 나누어지는 수이다.

소수를 판별하는 알고리즘 중에서 에라토스테네스의 체가 가장 빠르다. ( 시간 복잡도 O(Nlog(logN)) )

에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나가는 방법을 이용한다.

1. 배열을 생성하여 초기화한다.
2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.(지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.)
3. 2부터 시작하여 남아있는 수를 모두 출력한다.

여기서 한단계 더 발전시켜서 i*i까지 체크해준다. 

// i*i 부터 시작하는 이유는? 그이전 값은 그이전 i값에서 다 소수인지 체크 했으므로
// 3*3 = 9 부터 +3 씩 체크해주면된다, 2의배수는 2에서 모두 체크했음 5는 5에서 체크할 예정

static boolean[] prime = new boolean[1000001];
static void findPrime(){
        // 100만 이하 소수 찾기 prime[i] == false 소수
        for (int i = 2; i * i <= 1000000; i++) {
         // i*i 부터 시작하는 이유는? 그이전 값은 그이전 i값에서 다 소수인지 체크 했으므로
 		// 3*3 = 9 부터 +3 씩 체크해주면된다, 2의배수는 2에서 모두 체크했음 5는 5에서 체크할 예정
            if (!prime[i]) {
                for (int j = i * i; j <= 1000000; j += i) {
                    prime[j] = true;
                }
            }
        } 
}

두수 의 최대 공약수를 구하는 알고리즘이다. 

임의의 두 자연수 a, b가 주어졌을때. 둘중 큰 값이 a라고 가정한다면,

a를 b로 나눈 나머지를 n 이라고 하면 (a%b = n)

n이 0일때, b가 최대 공약수(GCD)이다.

만약 n이 0이 아니라면, a에 b값을 다시 넣고 n를 b에 대입 한 후 다시 위에 step2부터 반복하면 된다.

ex) a = 12 , b = 8 

1) 12 % 8 = 4 ( a % b = n )

2 ) 8 % 4 = 0 ( a % b = 0 이면 b가 최대공약수 )

따라서 a, b의 최대 공약수는 4 이다

1. 반복문

int gcd(int a, int b){
    if(a<b){ // a가 항상 큰값 
        int tmp = a;
        a = b;
        b = tmp;
    }
    
//b가 0이 될때까지(a%b), 반복문을 돌게되고, b가 0인 순간의 a를 GCD로 판단하고 리턴합니다.
    while(b!=0){
        int n = a % b;
        a = b;
        b = n;
    }
    return a;
}

2. 재귀

 static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    } 

세그먼트 트리는 인덱스트리를 탑다운으로 내리는것이다

나머지는 다 같다.

탑다운으로 내리는 것이기 때문에 구현은 재귀로 구현한다.

구간 Update 

s부터 e 까지의 구간을 cost만큼 update 해 준다.

// s,e : 찾아야할 구간 , l,r : 전체 구간 ( nLeaf 더해주어야함)
static void update( int s , int e , int node , int l , int r , int cost){ 
	if(r < s || e < l )  return ;  // 시작점과 끝점이 (찾으려고 하는 구간)이 전체 지점에서 벗어날 때 리턴
	if( s <= l && r <= e){  // 시작점과 끝점(찾으려고 하는 구간)이 전체 트리에서 딱 맞으면? 
		Tree[node] += cost ;  // 해당 노드에 cost를 더해주고 리턴 
		return;
	}
	
	int mid = ( l + r) / 2 ; 
	update(s , e , node *2 , l , mid , cost );
	update(s , e , node * 2 + 1 , mid+1 , r , cost );

}

점 Query

static void query(int idx){ // 부모의 자식의 수?
	int res = 0 ; 
	idx += nLeaf;
	
	while(idx >=1){
		res+= tree[idx];
		idx /= 2;
	}
	return res;
}

정말 중요한 인덱스 트리이다.

특징

1. 포화 이진 트리이다 

- 모든 트리가 꽉차 있는데 자식은 2개씩

2. 0번은 비운다 

- 자식을 내려갈때 *2 , *2+1 을 해주어야 하기 때문이다.

3. 최대 노드 10만, 20만 정도가 최대이다.

-> 이게 안되면 리라벨링 / 좌표 압축을 해주어야한다 

=> 값을 그대로 넣는것이 아니라 값의 순서로 넣어주는 것이다.

4. 세그먼트 트리는 탑다운방식 ( 재귀)

   인덱스 트리는 바텀업 방식 

응용

1. 구간의 최소값 

- 초기화 = MAX

2. 구간의 최대값

- 초기화 = 0

3. 구간합

- 초기화 = 0

4. K번째 값 찾기 *** 

값 update

해당 노드를 찾아서 트리를 위로 부모로 올라가면서 ( 나누기 2) 

루트가( 1) 이 될때까지 값을 업데이트 해준다.

해당 되는 cost를 직접 바꾸지않고 현재 노드와의 차이값을 구해

해당되는 차이 값을 더해준다.

static int N;
nLeaf = 1;
while(nLeaf < N){
	nLeaf <<= 1;
}
tree = new int[nLeaf * 2];

static void update(int i, int cost) { // 해당 인덱스의 값을 cost로 update 해준다
	int idx = nLeaf + i - 1;
	int diff = cost - tree[idx];
	while (idx >= 1) {
		tree[idx] += diff;
		idx /= 2;
	}
}

구간 합 구하기

구간합은 s에서부터 e까지의 노드의 값을 더해준다.

s가 e가 될때까지

시작점이 오른쪽이면 노드를 모두 포함 하고 있지 못하기 때문에 

부모 값을 활용 할수 없어 , 해당 노드를 res에 더해주고 

노드를 오른쪽으로 옮겨준다. 

종료 지점이 왼쪽에 있으면 부모값을 활용할 수 없어, 해당노드를 res에 더해주고 

종료지점을 왼쪽 옮겨준다.

static int query(int s, int e) { // s부터 e까지의 값의 부분합을 구해준다.
	int res = 0;
	s = nLeaf + s - 1;
	e = nLeaf + e - 1;
	while(s <= e) { //시작점 끝점이 서로 크로스 될때까지 반복
		if(s % 2 == 1) { //시작점이 오른쪽이면
		res += tree[s];
        	s++;
		}
		if(e % 2 == 0) { // 끝점이 왼쪽이면
		res += tree[e];
         	e--;
		}
		s/=2; e/=2;
	}
	return res;
} 

K번째 수 구하기

k 번째 값을 구하려면

idx가 위에서부터 찾는데 nLeaf가 있는데 까지 찾으면된다.

좌우 값을 비교해가면서 

k가 왼족 노드 값에 모두 포함되면? 왼쪽으로 이동하고

값이 걸쳐있으면? 왼쪽 노드 값만큼 빼주고 오른쪽으로 이동한다.

 static int search(int k) {// k번째 수 찾기
        int idx = 1; // 루트부터 시작
        while (idx < nLeaf) { // 위에서부터 찾는데 nLeaf 있는데 까지만 찾아도돼
            int l = idx * 2; //좌
            int r = idx * 2 + 1; //우
            if (k <= tree[l]) {  //k번째 값이 왼쪽에 모두 포함되면?
                idx = l; // 걍 왼쪽으로 이동
            } else {
                // 값이 걸쳐있으면? 오른쪽으로 이동해야해
                k -= tree[l]; // 값이 걸쳐있으니깐 , 왼쪽 트리값 빼주기
                idx = r;// 오른쪽이동
            }

        }
        return idx - nLeaf + 1;
    }

단절점이란?

어떤 연결되어 있는 그래프에서 

해당 정점을 없애면, 다른 정점들이 여러 그룹으로 나뉘어 지면 해당 정점이 단절점이다.

그래서 코드는 dfs로 구현하다.

dfs 에서

두가지로 나눈다.

1. 노드가 루트일 경우

-> 밑에 자식이 2 이상이면 단절점이다.

2. 노드가 루트가 아닐경우

dfs로 inOrder를 각 정점에 저장하고

현재 노드의 자식들이 올라갈 수 있는 곳중 가장 높은곳을 리턴받아 그값을 sub라고 하면

그값이 현재 노드의 방문순서보다 더 높으면(크면) 해당 점은 단절점이다.

이게 왜그러냐면, 처음엔 이해가 잘안될 수 있다.

노드 각 정정을 방문하는 순서를 저장하는데  예를들어,

[1,2,3] - [4] - [5,6,7,8] 

이렇게 연결된 노드가 있다고 해보자 크게

그러면 4의 자식인 5~8이 4를 삭제했을때,

1~3을 갈 수 있으면 4는 단절점이 아닌 것이다.

그런데 5~8에서 갈수 있는 곳중 (4를 거치지 않고) 가장 inOrder min값이 5라면 

해당 정점 4는 단절점이다.

샘플코드

    // 시작지점 위치적으로 가장 상위에 있다고 가정 했을때
    // now 노드를 기준으로 하위 sub graph를 탐색했을 때 올라갈 수 있는 가장 높은 위치를 반환
    static int dfs(int now, boolean isRoot) {
        discover[now] = ++inOrder; // 방문순서 마킹
        int res = discover[now]; // 초기값 = 현재 inOrder값
        int child = 0;
        for (int next : adj[now]) {
            if (discover[next] == 0) {//1. 미발견된 노드
                child++; // root일 경우, 단절점 판단을 위해
                int sub = dfs(next, false); // 자식들이 올라갈 수 있는 가장 높은 곳
                if (!isRoot && sub >= discover[now]) {// 루트가 아니고, 자식들이 올라갈 수 있는 가장 높은 곳이 나의 방문 위치보다 더 크다면
                    // 나 이전 노드는 방문 불가
                    isCut[now] = true;
                }
                res = Math.min(res, sub); // 가장 높은곳?
            } else {//2. 발견된노드드
                res = Math.min(res, discover[next]);
            }
        }
        if (isRoot && child >= 2) { // 루트일 경우 단절점 판단
            isCut[now] = true;
        }
        return res;
    }