MathTrauma

문제 링크 : https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 어설픈 영어 실력에도 불구하고 원문이 이해하기 쉬워서 그쪽으로 내용을 정리한다. n 개의 점의 좌표가 주어지고 그 점들 중 일부는 m 개의 도로로 연결되어 있다. 아직 연결되지 않은 점들을 최소의 비용(도로의 길이)으로 연결하는 문제이다. 1. 미리 주어진 m 개의 간선(도로)를 제한 나머지 모든 점들 사이에 간선을 만들고 비용 오름차순으로 정렬한다. 2...

문제 링크 : https://www.acmicpc.net/problem/11503 11503번: Tree Edit Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case consists of two lines. The first line contains a string representing T1 and the second line www.acmicpc.net 문제가 길어서 대충 읽었다가 'ordered tree' 라는 조건을 놓쳐서 시간을 많이 허비했다. 자식들의 순서..

문제 링크 : 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 최소 신장 트리를 구하는 데에는 대표적인 두 알고리즘인 Prim 알고리즘과 Kruskal 알고리즘이 있다. 두 가지 모두 구현하고 몇 가지 첨언한다. 1. Kruskal Algorithm 간선의 가중치를 오름차순으로 정렬하여 하나씩 조사한다. 기존에 선택된 간선들과 cycle 을 형성하지 않으면 선택한다. cycle 을 확인하는 방법으로..

문제 링크 : https://www.acmicpc.net/problem/3176 3176번: 도로 네트워크 첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양 www.acmicpc.net 최소 공통 조상을 \(\log(n)\) 시간 이내로 찾을 수 있도록 해주는 것은 이중 배열 prv 이다. 이 배열은 음이 아닌 정수 k 에 대해 \(2^k\) 만큼 앞의 선조에 대한 정보를 기록하고 있다. prv[i][k] 는 i 번 노드의 \(2^k\) 번째 선조로 prv[i][k]=prv[prv[i][k-1]][k-1] 을 만족한다. 도..

문제 링크 : https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 주어진 문제는 root 가 주어진 tree 에서 최소(?)의 공통 조상을 찾기를 요구하는데... 노드(정점) 집합의 크기로 보아 lca(least comman ancestor) 와 관련된 기술을 쓰지 않아도 될 것으로 보인다. 하지만 분류상 '최소공통조상'에 들어 있는 문제이니, 하라는 대로 했다. 각 노드가 자신의 부모만 알고 있..