kth990303의 코딩 블로그

알고리즘 중급 스터디에서 과제로 해결해야 했던 문제. 포인트를 놓쳐 생각보다 굉장히 많이 삽질했다. 문제는 아래와 같다. https://www.acmicpc.net/problem/24520 24520번: Meet In The Middle 첫 번째 줄에 마을의 수 $N$, 약속의 수 $K$가 주어진다. $(1 \le N, K \le 100\,000)$ 이어지는 줄부터 $N-1$개의 줄에 도로 정보를 나타내는 세 정수 $u$, $v$, $w$가 주어진다. $u$번 마을과 $v$번 마을 사이에 www.acmicpc.net 의식의 흐름 및 해설 N이 10만이기 때문에 DFS O(N)으로 모든 노드를 훑으면 시간초과이다. 따라서 특정 노드만 확인해주면 되는데, 정점들 사이의 거리는 LCA로 O(logn)에 구할 ..

개인적으로 가장 어려워하면서도, 가장 흥미가 있는 주제인 LCA 문제이다. 사실 처음부터 lca 문제를 해결하려던 건 아니고, 트리 문제를 구경하던 중 lca가 떠오르는 문제를 발견하여 lca 연습 겸 풀어본 문제이다. https://www.acmicpc.net/problem/13511 13511번: 트리와 쿼리 2 N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다. 아래의 두 쿼리를 수행하 www.acmicpc.net 상한 시간복잡도: O(NlgN) 사용 알고리즘: LCA LCA 코드 살펴보기 LCA를 O(lgN)의 속도로 찾아내야 상한 시간복잡도를 넘기지 않는다. 루트노드의 번호가 ..