기록방

👉 문제링크 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 🔸 문제 분석 🔸 N개의 도시와 도시 사이를 연결하는 M개의 단방향 도로가 존재한다. 도로 하나 당 1의 거리를 갖는다. X번 도시에서 시작해 최단거리가 정확히 X 거리만큼 떨어진 도시의 목록을 출력한다. 🔸 문제 풀이 🔸 하나의 노드에서 다른 모든 노드들의 최단 거리를 구해야 하므로 다익스트라 알고리즘을 사용한다. N은30만개인데, 우선순위 큐를 활용해 O(NlogN)으로 해결..

👉 문제링크 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 🔸 문제 분석 🔸 N개의 집과 M개의 집 사이를 연결하는 길이 있다. 서로 이어지지 않는 마을 2개를 만드려고 하는데, 각 마을 안에서는 집끼리 길이 연결되어 있어야 한다. 길의 유지비 합의 최소값을 출력한다. 🔸 문제 풀이 🔸 마을 안에서 집 사이에 길이 연결되어 있어야 하고, 그 가중치가 최소가 되어야 하므로, 두 개의 최소 신장 트리(MST) 가 만들어져야 한다. 여기서는 크루스칼(Kruskal) 알고리즘을..

👉 문제링크 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 🔸 문제 분석 🔸 최소 신장 트리(MST, Minimum Spanning Tree)를 구현하는 문제이다. 크루스칼(Kruskal)과 프림(Prim) 알고리즘이 있는데, 여기서는 크루스칼을 사용했다. 🔸 문제 풀이 🔸 크루스칼 알고리즘의 기본 형태를 구현한다. 간선을 가중치 기준으로 오름차순 정렬하기 위해 우선순위 큐를 사용했다. 사이클 방지를 위해 같은 집합에 포함되어있는지 확인이 필요하므로 Union-..

👉 문제링크 27172번: 수 나누기 게임 《보드게임컵》을 준비하다 지친 은하는 보드게임컵 참가자들을 경기장에 몰아넣고 결투를 시키는 게임 《수 나누기 게임》을 만들었습니다. 《수 나누기 게임》의 규칙은 다음과 같습니다. www.acmicpc.net 🔸 문제 분석 🔸 최대 10만개의 서로 다른 수가 적힌 카드가 있다. 이때 수는 1~100만 사이의 정수이다. 카드들을 서로 결투를 벌여서 나누어 떨어지면, 나누는 수는 +1, 나누어진 수는 -1 점을 받는다. 모든 카드들을 결투시켜 최종 점수를 출력한다. 🔸 문제 풀이 🔸 N이 10만이므로 O(NlogN)로 비교하면, 100억번으로 제한 시간인 1초를 초과하게 된다. 에라토스테네스의 체를 활용해서 소수가 아닌, 카드 숫자의 배수 인덱스만 확인해서 결투를 진..

👉 문제링크 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 🔸 문제 분석 🔸 N개의 꼭지점으로 이루어진 다각형의 정보가 주어진다. 다각형의 넓이(면적)을 소수점 둘째 자리에서 반올림하여 첫째 자리까지 출력한다. 🔸 문제 풀이 🔸 신발끈 공식 (Shoelace formula)의 전형적인 연습 문제이다. x좌표와 y좌표를 입력받아 공식을 구현하고, 소수점 첫째 자리까지 반올림해 출력한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io...