전체 글

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 문제 풀이 위상 정렬 문제이다. inDegree 배열을 하나 만든 다음 , 차수가 0이면 Queue에 추가 , 인접한 노드들의 InDegree 차수 1씩 감소 하는식으로 Queue가 비어 있을때 까지 반복하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 ..

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를 weight가 작은 순으로 Queue에 넣은 뒤 ( priorityQueue사용) parent 배열의 크기를 정점의 갯수만큼 정해주고 , union연산으로 disjointSet을 만들어가면서 가중치를 더하는 식으로 하면 된다. 1 2 3 4 5 6 7 8 9 10 11 ..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제 풀이 투 포인터 활용 문제이다. start, end를 0에서 시작하여 목표값 target 보다 크거나 같으면 start 전진, target이 더 크면 end 전진 , end가 전진하다가 끝에 다다르면 종료. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 import java.uti..

https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 문제 풀이 투포인터를 써야하는 문제이다. i < j 를 항상 만족해야 하므로 , start < end 가 만족해야한다. 이걸 안해서 틀렸었음 .. 1. 정렬된 배열이 필요. 2. 왼쪽맨끝 과 오른쪽 맨끝에서 순차적으로 번갈아 가면서 조금씩 접근 조건을 만족한다면 end,start 인덱스 동시에 조정 조건을 만족하지 않는다면 둘 중 하나만 조정..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 풀이 전형적인 이분탐색 문제이다. right left를 정해놓고 진행할때마다 점점 중간값으로 탐색하는 방식으로 하면된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 import java.util.*; import java.io..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제 풀이 TreeMap 으로 이진탐색을하여 이미 존재하는 숫자면 replace로 기존값 +1 처음 들어오는 숫자면 put을 하여 구성을 한 후 , containkey 함수를 호출하여 각 값을 출력하면된다. print함수를 사용하면 최악의 경우 50만번 출력을 해서 시간초과가 났었다. StringBuilder를 사용하여 한번에 출력할 것. 1 2 3 4 5 6 7..

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 문제 풀이 1. 정렬된 배열과 이분탐색으로 들어가야하는데 , 이를 보장하는 자료구조인 TreeSet을 이용한 풀이이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 import java.util.*; import java.io.*; public class Main{ public static void main(..

https://www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 문제 풀이 기본적으로 풀이는 우선순위 큐를 이용한 다익스트라 방법이랑 같다. (포장 하지 않을 경우) 하지만 여기선 추가되어야하는 부분이 거리부분인 distance[] 배열을 2차원으로 만드는것이다. 도로포장을 하지않을때 부터(0) 포장했을때(k)까지 의 거리비용이 달라지기 때문 따라서 distance[도시의갯수][도로포장 개수] 로 해야한다 => distanc..