날마다 새로운 코딩

1. 문제 : https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 2. 풀이 : Kruskal 3. 시간복잡도 : O(ElogE) 4. 설명 모든 대학교를 최단 거리로 연결을 해야 하는 문제다. 단, 문제의 조건에따라 남초 대학교와 여초 대학교를 연결하는 도로로만 최단 거리가 구성되어야 하고 모든 대학교를 연결하는 경로가 없을 경우 -1을 출력한다. 그림[1]에서 남초 대학교는 파란색으로 여초 대학교는 빨간..

Algorithm/Kruskal 2021. 6. 19. 22:38

1. 문제 : https://www.acmicpc.net/problem/9373 9373번: 복도 뚫기 각 테스트 케이스마다 센서에 감지되지 않고 복도를 지나갈 수 있는 원형 물체의 최대 반지름을 부동소수점 실수로 한 줄에 출력한다. 물체는 매우 정밀하게 움직일 수 있다고 가정한다. 만약 www.acmicpc.net 2. 풀이 : Kruskal 3. 시간복잡도 : O(N2logN) 4. 풀이 그림[1]과 같이 센서가 배치 되어있다고 생각해보자. 문제 조건에의해 왼쪽벽은 x=0인 직선이 되고, 오른쪽벽은 x=20인 직선이 된다. 각 센서들간의 거리를 '두 점 사이의 거리 - 각 센서의 반지름'으로 구해보면 그림[2]와 같다. 이어서, 각 센서들과 벽과의 거리를 구하면 그림[3]과 같다. 거리가 짧은 순서대..

Algorithm/Kruskal 2021. 6. 14. 22:02

1. 문제 : https://www.acmicpc.net/problem/14950 14950번: 정복자 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재 www.acmicpc.net 2. 풀이 : Prim 3. 시간복잡도 : O(ElogV) 4. 설명 문제의 조건은 다음과 같다. 1. 처음 점거하고 있는 도시는 1번 도시이다. 2. 한번 정복한 도시는 다시 정복하지 않는다. 3. 도시를 정복한 후에는, 정복한 도시의 수 만큼 추가 비용이 발생한다. 4. 모든 도시를 최소의 비용으로 정복한다. 1, 2, 4 조건에 의해 1번 도시를 시작점으로하는 MST를 생성하고, ..

Algorithm/Prim 2021. 6. 13. 23:27

1. 문제 : https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 2. 풀이 : Kruskal 3. 시간복잡도 : O(ElogE) 4. 설명 문제의 조건은 아래와 같다 1. 분리된 두 마을 사이의 길은 없앤다. 2. 각 분리된 마을 안에서 임의의 두 집 사이에 경로는 항상 존재하며, 길은 더 없앨 수 없다. 3. 길의 유지비의 합을 최소로 한다. 분리되기 전 하나의 마을에대해 MST를 생성한다. 완성된 MST에..

Algorithm/Kruskal 2021. 6. 12. 00:24

1. 문제 : https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 2. 풀이 : Kruskal 3. 시간복잡도 : O(ElogE) 4. 설명 kruskal 알고리즘을 사용하여, 최소 스패닝 트리를 만들어 문제를 해결한다. 그림[1]과 같이 가중치 오름차순 순으로 모든 간선들을 우선순위큐에 삽입한다. 우선순위큐에서 간선을 하나씩 빼내면서 union-find를 진행한다. 그림[5]에서 1번 컴퓨터와 2번 컴퓨터는 이미 3번 컴퓨터를 통해 연결되어 동일한 네트워크상에 있으므로, 1번 컴퓨터와 2번 컴퓨터는 연결하지 않는다. 그림[7]에서 2번..

Algorithm/Kruskal 2021. 6. 10. 22:23

1. 문제 : 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 2. 풀이 : Prim 3. 시간복잡도 : O(ElogV) 4. 설명 그림[1]과 같이 주어진 그래프를 인접리스트로 표현한다. 시작점까지의 가중치는 없으므로 시작점의 번호인 7과 가중치 0을 우선순위큐에 삽입한다. 우선순위큐는 가중치의 오름차순으로 정렬한다. 그림[2]와 같이 7번 노드를 방문 처리 후, 7번 노드에서 갈 수 있는 노드의..

Algorithm/Prim 2021. 6. 7. 21:16

1. 문제 : https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 2. 풀이 : Union-Find 3. 시간복잡도 : O(logN) 4. 설명 입력값으로 들어오는 사용자ID(String)를 숫자(Integer)로 변경하여 Union-Find를 사용한다. 첫번째 줄의 입력값 Fred(0)와 Barney(1)을 union하면 그림[1]과 같고, 두 사람의 친구 네트워크에는 2명이 존재한다. 두번째 줄의 입력값 Barney(1)와 Betty..

Algorithm/Union-Find 2021. 6. 6. 00:03

1. 문제 : https://www.acmicpc.net/problem/1572 1572번: 중앙값 중앙값이란, 수열을 정렬했고, 그 크기가 N일 때, 1부터 시작해서 (N+1)/2번째 있는 원소가 그 수열의 중앙값이다. 예를 들어, {1, 2, 6, 5, 4, 3}에서는 3이고, {11, 13, 12, 15, 14}에서는 13이다. 오세준은 1 www.acmicpc.net 2. 풀이 : Indexed Tree 3. 시간복잡도 : O(NlogN) 4. 설명 단순하게 1부터 N까지 반복하면서 K개씩 정렬을하고 중앙값을 찾으면 풀릴 것 같지만 타임아웃이 발생하여 문제를 풀 수가 없다. 이 문제는 인덱스 트리에 K개의 입력값을 유지하면서 중앙값을 탐색하여 풀 수 있다. N=6, K=3, 입력값의 범위 0 ~ ..

Algorithm/Indexed Tree 2021. 6. 3. 23:19