Hello, Freakin world!

www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정� www.acmicpc.net LCA 은 간단하게 트리 구조의 특성을 이용해 단순하게 해결했는데, 이번 문제는 효율성을 고려하지 않으면 풀 수 없었습니다. 영어로 LCA로 검색을 해보면 이 문제에 관해 여러 가지 풀이가 존재한다는 걸 알 수 있습니다. cp-algorithms.com/graph/lca.html Lowest Common Ancestor - O(sqrt(N)) and O(log N) with O(N) preproces..

www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정� www.acmicpc.net 트리 구조의 특성을 생각해보면 풀이를 떠올릴 수 있다. 트리 구조에서 하나의 노드는 다수의 자식을 가질 수 있지만 부모 노드를 오직 하나만 가진다. 그렇기 때문에 각 노드에서 부모 노드의 참조를 저장해두면 두 개의 노드에서 따라올라가면서 최소 공통 조상을 찾을 수 있다. 까다로운건 이 문제에서 입력으로 트리를 구성하기 위해서는 일단 양방향 노드 그래프를 만들어야 되는데, 나는 그냥 한번 임시 트리를 만들..