Dev.baelanche
[백준 1269] 대칭 차집합
Set(집합) 라이브러리를 이용하여 풀었다. 다음번에는 자료구조를 직접 구현해서 풀어야겠다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int an = sc.nextInt(); int bn = sc.nextInt(); TreeSet a = new TreeSet(); TreeSet b = new TreeSet(); for(int i=0; i
[백준 4256] 트리
예제로 트리 구조를 유추해보자. 전위 순회 : 3 6 5 4 8 7 1 2 중위 순회 : 5 6 8 4 3 1 2 7 전위 순회는 루트부터 시작하고, 중위 순회는 루트를 중심으로 왼쪽 서브트리, 오른쪽 서브트리로 나뉜다. 전위 순회의 첫번째가 3이므로 루트 노드는 3이고 5 6 8 4 는 왼쪽 서브트리, 1 2 7 은 오른쪽 서브트리이다. 양 서브트리의 루트(최상단) 노드는 전위 순회의 첫번째 노드 이므로 각각 6, 7 이다. 루트 노트를 찾았으면 또 이등분하여 서브트리를 구한다. 시작 위치, 끝 위치, 루트 노드의 위치를 받아 재귀하여 구현하였다. public class Main { static int pre[]; static int in[]; public static void main(String[]..
[백준 16437] 양 구출 작전
입력값들로 트리를 만들어 후위 순회를 한다. 늑대의 수 - 양의 수가 음수가 될때를 주의해주어야 한다. public class Main { static ArrayList a[]; static char sw[]; static int score[]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); a = new ArrayList[n+1]; sw = new char[n+1]; score = new int[n+1]; for(int i=0; i
[백준 1068] 트리
트리구조를 만든 후 BFS를 두번 수행하여 푼다. 1. BFS로 루트부터 하위 레벨로 순차적으로 접근한다. 2. 제일 하위 레벨의 노드일때는 접근하지 않는다. 3. 첫번째 BFS에서 접근하지 않은 노드들에 다시 접근해서 개수를 센다. public class Main { static ArrayList[] tree; static int[] parents; static boolean[] visited; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new..
[백준 4803] 트리
트리의 성질을 이용하여 풀어야하는 문제이다. 1. 입력값으로 트리를 만든다. 2. DFS 를 통해 컴포넌트 별로 간선 개수, 노드 개수를 각각 구한다. 3. 노드 개수 - 1 = 간선 개수 를 만족해야 트리이다. 4. 양방향으로 구현하였으므로 간선/2 를 해주었다. public class Main { static int tree[][]; static boolean visited[]; static boolean vertexes[]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new..
[백준 11725] 트리의 부모 찾기
입력값으로 트리를 구성한 후 DFS 를 한다. 부모 노드를 저장할 배열을 만들어 DFS 도중에 부모 노드 정보를 저장해주면 된다. public class Main { static int parents[]; static ArrayList nodes; static boolean visited[]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int n = Integer.parseIn..
[백준 1991] 트리 순회
입력이 문자이므로 캐릭터형을 정수형으로 바꾸어 트리를 만들었다. 출력할때만 다시 캐릭터형으로 출력했다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); sc.nextLine(); Tree t = new Tree(n); while(n-->0) { char[] c = sc.nextLine().toCharArray(); t.setChildren(c[0]-65, c[2]-65, c[4]-65); } t.preorder(0); System.out.println(); t.inorder(0); System.out.println(); t.postorder..
[백준 2014] 소수의 곱
풀이 1. 입력한 소수들을 배열에 저장하고 우선순위큐(최소힙)에 담는다. 2. 우선순위큐의 top을 제거하고 top과 1번에서 저장한 배열의 각 인덱스를 곱하여 큐에 담는다. 3. 2번을 반복한다. 위 풀이대로 진행하면 중복된 수들도 큐에 담기게 되는데, 이 부분만 예외처리 하면 시간초과 없이 문제를 풀 수 있다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); PriorityQueue pq = new PriorityQueue(); int k = sc.nextInt(); int n = sc.nextInt(); int a[] = new int[k]; for(int i=0; i