매일개발

https://www.acmicpc.net/problem/2960

문제 조건

문제 이해하기

이 문제는 사실상 에라토스테네스의 체가 뭔지만 바로 풀 수 있는 문제이다.

에라토스테네스의 체는 문제 조건에서 나와있듯이, N보다 작거나 같은 모든 소수를 찾는 알고리즘이다.

알고리즘은 다음과 같다. 

1. 2부터 N까지 모든 정수를 적는다.
2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

알고리즘을 이해하기 위해, N을 7로 설정하여 예를 들어보자. 

1. 2부터 N(=7)까지 모든 정수를 적는다.
2 3 4 5 6 7

2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P(=2)라고 하고, 이 수는 소수이다.
2 3 4 5 6 7 <- 이 중 가장 작은 숫자는 2, P = 2가 되며 이 수는 소수이다.

3. P(=2)를 지우고, 아직 지우지 않은 P(=2)의 배수를 크기 순서대로 지운다.
2 3 4 5 6 7 <- P(=2)를 지우고,
2 3 4 5 6 7 <- 아직 지우지 않은 P(=2)의 배수를 크기 순서대로 지운다.

4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

-> 여기서 P = 2

2 3 4 5 6 7

2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P(=3)라고 하고, 이 수는 소수이다.
2 3 4 5 6 7 <- 이 중 가장 작은 숫자는 3, P = 3이 되며 이 수는 소수이다.

3. P(=3)를 지우고, 아직 지우지 않은 P(=3)의 배수를 크기 순서대로 지운다.
2 3 4 5 6 7 <- P(=3)를 지우고,
2 3 4 5 6 7 <- 아직 지우지 않은 P(=3)의 배수를 크기 순서대로 지운다.

4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

-> 여기서 P = 3

2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P(=5)라고 하고, 이 수는 소수이다.
2 3 4 5 6 7 <- 이 중 가장 작은 숫자는 5, P = 5이 되며 이 수는 소수이다.

3. P(=5)를 지우고, 아직 지우지 않은 P(=5)의 배수를 크기 순서대로 지운다.
2 3 4 5 6 7 <- P(=5)를 지우고,
2 3 4 5 6 7 <- 아직 지우지 않은 P(=5)의 배수를 크기 순서대로 지운다.

4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

-> 여기서 P = 5

2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P(=5)라고 하고, 이 수는 소수이다.
2 3 4 5 6 7 <- 이 중 가장 작은 숫자는 7, P = 7이 되며 이 수는 소수이다.

3. P(=7)를 지우고, 아직 지우지 않은 P(=7)의 배수를 크기 순서대로 지운다.
2 3 4 5 6 7 <- P(=7)를 지우고,
2 3 4 5 6 7 <- 아직 지우지 않은 P(=7)의 배수를 크기 순서대로 지운다.

4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.
-> 모든 수를 지웠음!

-> 여기서 P = 7

지금까지 P의 값으로는 2, 3, 5, 7이 나왔다. 

이 알고리즘을 이용하면 쉽게 N 이하의 소수를 구할 수 있다!

하지만 위의 2960번 문제는 소수를 구하는 문제가 아니라,

N이 주어졌을 때, K번째로 지워지는 수를 구하는 문제이다.

그럼 알고리즘을 그대로 따라서 구현해보자!

문제 풀이 (코드)

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	int n = sc.nextInt();
    	int k = sc.nextInt();
    	boolean[] prime = new boolean[n + 1];
    	
    	int count = 0;
    	for(int i = 2; i <= n; i++) {
    		for(int j = i; j <= n; j += i) {
    			if(prime[j] == false) {
        			count++;
        			prime[j] = true;
    			}

    			if(count == k) {
    				System.out.println(j);
    				System.exit(0);
    			}
    		}
    	}
    }
}

https://www.acmicpc.net/problem/2252

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
public class Main {
	public static void tSort(List<List<Integer>> list, int[] indegree) {
		Queue<Integer> queue= new LinkedList<>();
		Queue<Integer> result= new LinkedList<>();
		for(int i = 0;i < indegree.length; i++) {
			if(indegree[i] == 0) {
				queue.add(i);
			}
		}
		while(!queue.isEmpty()) {
			int node = queue.poll();
			result.add(node);
			
			for(int i = 0; i < list.get(node).size(); i++) {
				int n = list.get(node).get(i);
				indegree[n]--;
				
				if(indegree[n] == 0) {
					queue.add(n);
				}
			}
		}
		int size = result.size();
		for(int i = 0; i < size; i++) {
			System.out.print(result.poll() + 1 + " ");	
		}
	}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int N = scan.nextInt();
		int M = scan.nextInt();
		List<List<Integer>> list = new ArrayList<List<Integer>>();
		int[] indegree = new int[N];
		for(int i = 0; i < N; i++) {
			list.add(new ArrayList());
		}
		
		for(int i = 0; i < M; i++) {
			int front = scan.nextInt() - 1;
			int back = scan.nextInt() - 1;
			list.get(front).add(back);
			indegree[back]++;
		}
		tSort(list, indegree);
		
		scan.close();
	}

}

https://www.acmicpc.net/problem/4386

최소신장트리 문제다.

최소신장트리를 배운지 시간이 지났더니 어떤 개념인지 흐릿하다.

다시 복습을 해보는 걸로!

문제 조건

문제 풀이 (코드)

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    private static int[] parent;
    private static ArrayList<Star> tmpList = new ArrayList<>();
    private static ArrayList<Star> starList = new ArrayList<>();
    private static float answer = 0;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        for (int i = 0; i < n; i++) {
            double x = sc.nextDouble();
            double y = sc.nextDouble();
            tmpList.add(new Star(x, y, 0f));
        }
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        for (int i = 0; i < tmpList.size() - 1; i++) {
            Star star1 = tmpList.get(i);
            double x1 = star1.x;
            double y1 = star1.y;
            for (int j = i + 1; j < tmpList.size(); j++) {
                Star star2 = tmpList.get(j);
                double x2 = star2.x;
                double y2 = star2.y;
                double weight = Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2));
                starList.add(new Star(i, j, weight));
            }
        }
        Collections.sort(starList);
        for (int i = 0; i < starList.size(); i++) {
            Star star = starList.get(i);
            if (!isSameParent((int) star.x, (int) star.y)) {
                answer += star.weight;
                union((int) star.x, (int) star.y); // 연결
            }
        }
        System.out.println(Math.round(answer*100)/100.0);
        
        scan.close();
    }

    private static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            if (x < y) parent[y] = x;
            else parent[x] = y;
        }
    }

    private static int find(int x) {
        if (parent[x] == x) 
            return x;
        else 
            return parent[x] = find(parent[x]);
    }

    private static boolean isSameParent(int x, int y) {
        x = find(x);
        y = find(y);
        return x == y;
    }

    static class Star implements Comparable<Star> {
        double x; 
        double y;
        double weight;

        public Star(double x, double y, double weight) {
            this.x = x;
            this.y = y;
            this.weight = weight;
        }

        @Override
        public int compareTo(Star o) {
            return Double.compare(weight, o.weight);
        }
    }

}

https://www.acmicpc.net/problem/11725

이번 문제는 트리의 부모를 찾는 문제!

언뜻 봤을 때는 되게 쉬워보였는데, 좀 짜증나는 문제였다

사실상 트리는 곁다리고 그래프 문제였기 때문..ㅎㅎ

문제 조건

문제 이해하기

결국 각 노드의 부모 노드를 찾으면 되는 문제이다!

그런데 입력 부분에서 조금 이해가 안 갔었다. 

트리의 노드는 항상 1이며, 루트 없는 트리가 입력으로 주어진다고 한다. 

그리고 입력으로는 트리 상에서 연결된 두 정점이 주어진다. 

예제 입력1을 따라가면서, 그림을 통해 다시 이해해보자!

입력으로는 

7 // 노드의 개수
1 6
6 3
3 5
4 1
2 4
4 7

이 주어진다. 

(1) 처음에 1 6이 주어진다. 

1이 6과 연결되어 있다는 것인데, 문제에서 루트는 항상 1이라고 했기 때문에

1의 자식 노드로 6을 넣어준다. 

(2) 6 3이 주어진다. 

6과 연결되려면 3을 6의 자식 노드로 넣는 수밖에 없다!

(3) 3 5가 주어진다.

위와 마찬가지로 5는 3의 자식 노드가 된다!

(4) 4 1이 주어진다.

1번과 똑같다. 루트는 항상 1이기 때문에,

4가 1과 연결되려면 4는 1의 자식 노드여야 한다.

(5) 2 4가 주어진다.

2와 4가 연결되려면?

당연히 2가 4의 자식노드가 되어야 한다.

(6) 4 7이 주어진다.

4와 7 연결? 4와 7이 연결되려면 7이 4의 부모노드거나 자식노드여야 하는데,

이미 4의 부모노드는 1로 확정이 되었다. 그러므로, 7은 4의 자식노드!

이제 트리를 다 구성했으며, 

2번 노드부터 차례대로 부모 노드를 출력하면 된다.

(나는 그냥 출력하면 된다고 생각했다. 그런데 아니었다.^^)

문제에서 2번 노드부터 차례대로 부모노드를 출력하라고 한다. 

나는 여기서 큰 착각을 했었다. 

파란색으로 적은 것처럼 노드의 번호를 매겨서, 2번 노드부터 부모 노드를 

1 1 6 4 4 5 이런 식으로 출력하면 된다고 생각했는데

문제가 그렇게 쉬울 리가 없지.. 이 방식이 전혀 아니었다.

(배고파서 정신이 나갔나보다. 문제 이해를 전혀 못 하고 있다..)

일단 출력값으로는

4
6
1
3
1
4

위의 값이 나와야하고, 이 값이 나오려면 트리에서 2를 찾아, 이 노드의 부모 노드인 4를 출력하고

3을 찾아, 부모 노드인 6을 출력

4를 찾아, 부모 노드인 1을 출력

5를 찾아, 부모 노드인 3을 출력

6을 찾아, 부모 노드인 1을 출력

7을 찾아, 부모 노드인 4를 출력해야 한다.

그러면 4 6 1 3 1 4으로, 알맞은 출력값이 나온다. 

아이디어 도출하기

트리를 어떤 식으로 구성해야 하는지 이해했고,

어떤 식으로 출력하는지도 이해했다.

근데 다 망했다

트리 만들고, 노드 하나하나 탐색해서 부모 노드 찾아서 했더니 시간 초과 나온다.

한마디로 위에 쓴 방법 아니라는 것!

지금까지 한 건 모두 삽질이었다! 행복하네..

DFS 써서 풀어야 한다..

최종 코드는 아래에 있는 것이다 (풀이는 나중에..)

문제 풀이 (코드)

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
	static int[] parents;
	static List<Integer>[] list;
	static boolean[] visit;
	static int n;
	
	private static void dfs(int v) {
		visit[v] = true;
		for(int i : list[v]) {
			if(!visit[i]) {
				parents[i] = v;
				dfs(i);
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		
		list = new ArrayList[n + 1]; parents = new int[n + 1];
		for(int i = 1; i <= n; i++) {
			list[i] = new ArrayList<>();
		}
		
		visit = new boolean[n+1];
		for(int i = 0; i < n - 1; i++) {
			int a = scan.nextInt();
			int b = scan.nextInt();
			
			list[a].add(b); 
			list[b].add(a);
		}
		
		dfs(1);
		for(int i = 2; i <= n; i++) {
			System.out.println(parents[i]);
		}
			
		scan.close();
	}
}

개짜증나. . 나중에 풀이 추가하고 수정하면서 이 멘트도 지워야지..