날마다 새로운 코딩

1. 문제 : https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 2. 풀이 : Dijkstra 3. 시간복잡도 : O(ElogV) 4. 설명 그림[1]의 그래프에서 시작점이 1번 노드 일 때, 각 노드까지의 최단거리를 구하는 방법은 다음과 같다. 시작점인 1번 노드를 우선순위큐에 삽입한다. 시작점에서 시작점까지의 최단거리는 0이다. 노드 1에서 최단 거리로 방문 할 수 있는 노드를 우선순위큐에 삽입하고, 최단 거리를 갱..

Algorithm/Dijkstra 2021. 7. 7. 22:22

1. 문제 : https://www.acmicpc.net/problem/1944 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 2. 풀이 : Kruskal + BFS 3. 설명 출발 지점에서 로봇과 복제된 로봇이 열쇠까지 이동하는 최단 거리와, 열쇠가 있는 지점에서 복제된 로봇이 다른 열쇠가 있는 지점까지 이동하는 최단 거리를 표현하면 그림[1]과 같다. 각각의 최단 거리는 S지점과, K지점에서의 BFS로 구할 수 있다. 출발 지점과 열쇠가 있는 지점을 넘버링하여 표현을 하면 ..

Algorithm/Kruskal 2021. 7. 5. 22:19

1. 문제 : https://www.acmicpc.net/problem/1185 1185번: 유럽여행 첫 줄에는 방문할 나라의 수 N(5 ≤ N ≤ 10,000)과 이 나라들 사이를 연결하는 길의 수 P(N-1 ≤ P ≤ 100,000)가 주어진다. 두 번째 줄에는 N+1번째 줄까지 i+1번째 줄에는 i번째 나라를 방문할 때 드는 비 www.acmicpc.net 2. 풀이 : Prim 3. 시간복잡도 : O(ElogV) 4. 설명 예제를 그림으로 표현하면 그림[1]과 같다. 모든 나라를 N-1개의 길 만으로 방문해야 하며, 그때의 비용이 최소가 되어야 하므로 MST를 생성해야 함을 알 수 있다. MST를 유지하며 시작 나라에서 모든 나라를 방문하고 시작 나라로 돌아오기 위해서는, 모든 도로를 2번씩 지나..

Algorithm/Prim 2021. 7. 2. 22:47

1. 문제 : https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 2. 풀이 : LCA + BFS 3. 시간복잡도 : O(MlogN) 4. 설명 문제의 예시를 그림으로 표현하면 그림[1]과 같다. 그림[2]와 같이 루트에서부터 BFS를 시작하여 각 노드들의 깊이와 2^0번째 조상, 즉 부모 노드를 확정한다. 루트 노드의 부모인 '-1'값은 조상이 없음을 의미한다. 희소 배열을 sparse라고 했을 때, 아래의 식이 성립하며 그림[3]과 같..

Algorithm/LCA 2021. 7. 1. 22:31

1. 문제 : https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 2. 풀이 : LCA + 오일러 투어 테크닉 3. 시간복잡도 : O(MlogN) 4. 설명 문제의 예시를 그림으로 표현하면 그림[1]과 같다. 루트(1번)에서부터 오일러 투어 테크닉을 사용하여 각 노드들의 진입/진출 순서를 확정한다. 그림[2]에서 진입 순서 배열을 in이라고 하고 진출 순서 배열을 out이라고 하였을 때, 두 노드 a와 b에 대하여 다음이 성립한다. 1. ..

Algorithm/LCA 2021. 6. 27. 21:05

1. 문제 : https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 2. 풀이 : DFS 3. 시간복잡도 : O(N) 4. 설명 그림[1]과 같이 트리의 모든 경로들 중에서 가장 긴 경로의 길이를 트리의 지름이라고 한다. 트리의 지름을 기준으로 원을 그리면 그림[2]와 같다. 트리의 지름을 구하는 방법은 다음과 같다. 1) 임의의 노드 x에서 가장 먼 거리에 있는 노드 a를 찾는다. 2) 노드 a에서 가장 먼 거리에 있는 노드 b..

Algorithm/Tree 2021. 6. 23. 23:16

1. 문제 : https://www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1≤N≤1,000)과 도로의 개수 M(1≤M≤n*(n-1)/2) 이 주어진다. 입력의 두 번째 줄 www.acmicpc.net 2. 풀이 : Kruskal 3. 시간복잡도 : O(ElogE) 4. 설명 문제의 조건은 다음과 같다. 1) 피로도 계산은 최초 조사된 길을 기준으로 한다. 2) 최악의 코스 = 오르막 길이 가장 많은 코스 3) 최적의 코스 = 오르막 길이 가장 적은 코스 각 간선에 오르막길인 경우엔 '0'을 내리막길인 경우엔 '1'의 가중치를 부여하고, 간선들을 가중치..

Algorithm/Kruskal 2021. 6. 21. 23:18

1. 문제 : https://www.acmicpc.net/problem/2406 2406번: 안정적인 네트워크 첫째 줄에 두 정수 n(1≤n≤1,000), m이 주어진다. n은 컴퓨터의 개수이며, m은 연결되어 있는 지사 컴퓨터들의 쌍의 개수이다. 다음 m개의 줄에는 두 정수 x, y가 주어진다. 이는 서로 다른 두 컴퓨터, www.acmicpc.net 2. 풀이 : Kruskal 3. 시간복잡도 : O(ElogE) 4. 설명 문제의 예제는 그림[1]과 같이 표현이 된다. 문제의 조건에서 본사 컴퓨터(1번)는 각 지사의 컴퓨터와연결되어 있는 네트워크를 보유하고 있다. 2번과 3번, 3번과 4번 컴퓨터는 직접 연결되어 있다. 문제에서 네트워크에 고장이 발생하는 경우는 다음과 같다. 1) 직접 연결되어 있..

Algorithm/Kruskal 2021. 6. 19. 23:58