문제 https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 설명 i번 도시에서 i번 도시로 가는 최단경로는 0이지만, 일반적인 k번째 최단경로는 0이 아닐 수 있음에 유의한다. 또, k번째 최단경로가 존재하지 않으면 -1을 출력한다. 최단경로에 같은 정점이 여러 번 포함되어도 된다. 도로의 정보를 저장하기 위한 Road 클래스를 만들고 리스트를 만들어 연결관계를 저장한다. 이때, 소요 시간이 ..
문제 https://www.acmicpc.net/problem/11400 11400번: 단절선 첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A www.acmicpc.net 설명 그 간선을 제거했을 때 그래프가 두 개 또는 그 이상으로 나누어지는 간선을 단절선이라 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 간선을 말한다. 먼저 간선 정보를 저장할 CutLine 클래스를 만들고 단절선을 저장할 배열인 cutList를 만든다. 나중에 단절선을 사전순으로 출력해야 하므로 Comparable 인..
문제https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다.www.acmicpc.net 설명각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 구해야 한다.이번 문제에서는 크루스칼 알고리즘을 통해 최소 신장 트리를 구할 것이다.먼저 간선의 정보를 저장할 Edge 클래스를 만든다.우선순위 큐에서 가중치를 기준으로 오름차순으로 정렬하기 위해 Comparable 인터페이스를 이용한다.static class Edge implements Comparable { int current; int dest; int cost; ..
문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 설명 최소 스패닝 트리는 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 이번 문제에서는 프림 알고리즘을 통해 최소 신장 트리를 구할 것이다. 먼저 간선의 정보를 저장할 Edge 클래스를 만든다. 우선순위 큐에서 가중치를 기준으로 오름차순으로 정렬하기 위해 Comparable 인터페이스를 이용한다. c..
문제 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 설명 각 보석은 무게 M와 가격 V를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 C이다. 가방에는 최대 한 개의 보석만 넣을 수 있다. 먼저 보석의 무게와 가치를 저장할 Dia 클래스를 만든다. 가방마다 담을 수 있는 최대 무게가 있으므로 무게가 낮은 보석부터 넣으면서 판단하기 위해 무게..
우선순위 큐의 특징 큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다. 우선순위 큐(Priority Queue)는 먼저 들어온 데이터가 아닌 우선순위가 높은 데이터가 먼저 나가는 자료구조이다. 우선순위 큐를 사용하기 위해서는 Comparable 인터페이스 또는 Comparator 인터페이스를 재정의해야 한다. 각각 compareTo 메소드와 compare 메소드를 재정의해야 되는데 거기서 우선순위 조건을 리턴해주면 우선순위 큐에서 알아서 우선순위대로 정렬해준다. 우선순위 큐는 일반적으로 힙을 이용하여 구현한다. 데이터를 삽입할 때 우선순위를 기준으로 최대 힙 혹은 최소 힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸 뒤 루트 노드를 삭..
문제 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 설명 A와 B의 임의의 부 배열 두 개의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구해야 한다. 먼저 A와 B의 원소를 저장할 배열인 arrA와 arrB를 만든다. 그 다음, A와 B의 모든 부 배열의 각 원소의 합을 저장할 리스트인 sumA와 sumB를 만든다. 모든 부 배열의 각 원소의 합을 저장 한..
문제 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 설명 N개의 정수가 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내야 한다. 매번 하나씩 숫자를 비교하면서 탐색할 수 있지만 시간복잡도를 줄이기 위해 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 이분 탐색을 수행한다. 이분 탐색을 하기 위해서는 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있기 때문에 먼저 입력받은 수를 오름차..
