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;
    }

어떤 일을 하는 순서를 찾는 알고리즘이다.

DAG 란

1. 노드간의 순서가 있을때 

2. 사이클이 없을때 -> 사이클 판단 가능

3. 시간복잡도 O(V+ E)

dfs , bfs 모두 가능하다. bfs로 구현해보도록 하겠다.

DAG는 노드간의 순서가 있기 때문에

진입차수가 0인것을 queue에 넣어서 BFS를 진행해 보도록 하겠다.

Dfs

	for( n of All){
		if(!visited[n]) dfs(n);
	}
	
	dfs(int now){
		visited[now] = true;
		for(next : adj){
			if(!visited[next]) dfs(next);
		}
		stack.push(now);	//dfs 나오는 순서대로 stack에 쌓아준다. 
	}

Bfs

  static int bfs() { //위상정렬 DAG
        Queue<Integer> q = new ArrayDeque<>();
        int cnt = 0; 
       		
         for(int i = 1 ;i <= indegree.size()-1 ; i ++){
			if(indegree[i]==0){ // 인디그리가 없으면 큐에 넣어준다.
				q.add(i);
           }
	}

        while (!q.isEmpty()) {
            int now = q.poll();
            cnt++;
            for (Node next : adj[now]) {
                indegree[next.n]--; //next에 방문했으니 진입차수 줄여주기
                // next에 오기까지 위한 최대 dist 구해주기 그래야 다음을 갈 수 있음
                dist[next.n] = Math.max(dist[next.n], dist[now] + next.cost);
                if (indegree[next.n] == 0) {
                    q.add(next.n);
                }
            }
        }
        
        return cnt != N // cnt가 N이 아니면 사이클이 있음
    }

응용

1. 순서 찾기

2. 사이클 찾기

3. 문제 조건에 따라 순서 부여해 풀기

4. 위상정렬 + 동적 계획법

5. 사이클 없애가는 문제 

탐욕적인 방법(greedy method) 을 이용하여 

네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것

1) cost 기준으로 오름차순 정렬

2) 정렬된 그래프를 기준으로 간선연결

 - 간선은 필요한 간선만 연결
 - 필요한 간선이란? 기 연결된 정점은 해당 간선을 이용해 연결하지 않는다
 즉, 어떤 두 정점이 연결됐는지 안됐는지 확인하는 연산필요 -> union find 이용 
 1) find(a) != find(b) => 연결 (union(a,b))
 2) find(a) = find(b) => 연결 X

    static long kruskal(int startIdx) {
        initParent();
        for (int i = startIdx; i < M; i++) {
            Edge edge = list.get(i);
            if (find(edge.e) == find(edge.s)) { // 같은 그룹이면 연결 안함
                continue;
            }
            union(edge.s, edge.e); // 다른그룹이므로 연결함
        }
        return -1; // 연결 안되어 있음
    }

대표적 그래프 알고리즘으로 '합집합 찾기'라는 의미를 가지고 있습니다.

상호 배타적 집합(Disjoint-set)이라고도 합니다.

여러 노드가 존재할 때, 두 개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다.

즉, 그래프에서 같은 그룹에 속하는가? 를 물어볼 수 있는 알고리즘이다.

혹은 그룹을 합치거나

1. 초기화 ( make set)

자기자신을 부모로 갖도록 초기화 해준다.

int[] parent = new int[N+1];
for(int i = 0 ; i <= N ; i ++){
	parent[i] = i;
}

2. find

int find(int a){
	if(a == parent[a]) return a;
	return parent[a] = find(parent[a]); // 경로 압축

}

시간복잡도 O(N)

원래 return 부가 

return find(parent[a]) 인데 

return parent[a] = find(parent[a]) 로 경로 압축을 해주었다. 한번에 가기~!

3. union

void union(int a, int b){
	a = find(a);
	b = find(b);
	
	if(a != b){
		//항상 더 작은수로 부모를 넣어준다.
		if(a > b){ // a가 항상 작은수가 되도록 만듦
              int tmp = a;
              a = b;
              b = tmp;
        }
        parent[b] = a;
	}
}

4. 문제 풀기

1. 계속 합쳐지는 패턴 
2. 계속 분리되는 패턴 
 - 질문의 역순으로 답을 내야함 

  => 질문을 미리 저장해두고, 질문의 역순으로 답을 낸다. 

  
3. 그룹의 멤버의 수 
4. 유효/무효 값 분리 

LCA는 트리를 이용해서 최단거리 알고리즘을 구하는 것이다.

최소 공통조상을 구하는 알고리즘이다. Lowest Common Ancestor

구현

0. dfs or bfs depth , parent[N][K] : N번 노드의 2^K번째 조상 기록

parent[2][0] = 2번 노드의 첫번째 조상
parent[2][1] = 2번 노드의 두번째 조상
parent[2][2] = 2번 노드의 네번째(2^2) 조상

dfs로 구현하면 stack이 터질 수 있으니, bfs로 구현하는 것이 좋다.

2^K번째 조상을 기록 한다는것이 잘 이해가 안갈 수 있다. 왜 2^K번째 조상을 기록할까? 시간복잡도를 줄이기 위해서이다.

다음을 보자. 1에서 12로 이동할때 

이진법으로 움직이면?
1->2->-3->4->5->6->7->8->9->10  ->11         ->12 :  한칸씩 뛰면 11번 이동, 비효율적임
1--------(2^3)---------->9-----(2^1)---->11-(2^0)->12 :  2진법으로 움직이면 3번 이동, 효율적임

규칙을보면 다음과 같은 점화식을 얻을 수 있다.

parent[N][K] = parent[parent[N][K-1]][K-1];

A ------------> C                parent[A][4] = C
1               17

A ----- B ----> C                parent[A][3] = B , parent[B][3] = C
1        9        17               parent[A][4] = parent[parent[A][3]][3]

1. LCA 로직

 1) 양쪽 노드중 깊이가 깊은 것을 끌어올려 깊이를 맞춘다.( 2진법으로 뛸 수 있는 만큼 높이 뛰기)

 2) if(a == b) return a;

 3) else 높이가 맞춰진 양쪽 노드를 동시에 끌어올린다. 

    단 2진법으로 뛸수 있는만큼 뛰는데, ***부모가 다를경우에만 점프

 4) return parent[a][0]; // a또는 b의 부모 

샘플코드

BFS

    static int MAX =18;
    static int[] depth = new int[MAX];
    static int[][] parent = new int[MAX][32];
    // 2^k = N -> k = logN : parent배열의 열의 사이즈는 logN
    // 2^10 = 10^3 , 2^40 = 2^10^4 = 10^3^4 = 10^12
    // 2^17 = 13만 , 2^18 = 26만 , 2^20 = 104만

    static boolean[] visited = new boolean[MAX];
    static ArrayList<Integer>[] adj = new ArrayList[MAX];
    
    static void bfs(int now) {
        Queue<Integer> q = new ArrayDeque<>();
        q.add(now);

        while (!q.isEmpty()) {
            now = q.poll();
            visited[now] = true;
            for (int next : adj[now]) {
                if (visited[next]) continue;

                parent[next][0] = now;
                for (int j = 1; j < MAX; j++) {
                    parent[next][j] = parent[parent[next][j - 1]][j - 1];
                }

                depth[next] = depth[now] + 1; //// next의 depth는 현재의 depth++;
                q.add(next);

            }
        }
    }

LCA

    static int LCA(int a, int b) {
        // detph 맞추기
        // 0. 항상 a보다 b가 아래에 있는 상태로 만들어주기
        if (depth[a] > depth[b]) {
            int tmp = a;
            a = b;
            b = tmp;
        }

        //1. 양쪽 노드의 깊이를 맞춰주기 (B를 A가 있는 depth까지 끌어올리기)
        // 1 ---------->12 몇층 이동할까?
        // 12---->4-->2->1
        for (int i = MAX-1; i >= 0; i--) {
            if (depth[b] - depth[a] >= (1 << i)) { // 2^i : 이동할 수 있는만큼 이동하기
                b = parent[b][i];
            }
        }

        // 2. a,b 높이가 맞춰진 상태 - 현재 위치가 LCA인 경우?
        if (a == b) { return a; }
        //3. 양쪽을 동시에 2진법으로 끌어올릴수 있는 만큼 끌어올리는데,단 부모가 다르면 이동
        for (int i = MAX-1; i >= 0; i--) {
            if (parent[a][i] != parent[b][i]) { //부모가 다르면 이동
                a = parent[a][i];
                b = parent[b][i];
            }
        }

        return parent[a][0];
    }

N to N ( N<=500)

출발지와 도착지 모두 N개일때 쓰는 알고리즘

시간복잡도가 O(N^3)이므로 N이 적을때만 사용 가능하다.

i지점에서 j 지점까지 갈때의 최단거리가

k 지점을 거쳐서 가면 어느것이 더 최단거리일까? 라는것을 구해주면 된다.

샘플 코드

    
    static int[] d;
    static int N;
    static ArrayList<Node>[] adj = new ArrayList[N+1];
    static void floyd() {
        //1. d배열 INF 채우기
        Arrays.fill(d, INF);

        //2. 입력값으로 들어오는 간선 cost 받기 adj

        for (int k = 1; k <= N; k++) { //경유지가 밖에 있어야함.-> 대상이 되는 경유지를 고정 해야함.
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
    }