날마다 새로운 코딩

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