LCA2 [BOJ] 백준 11437번: LCA www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정� www.acmicpc.net LCA는 최소 공통 조상 (Lowest Common Ancestor)로 두 노드를 잇는 가장 짧은 경로 중 깊이가 가장 얕은 노드입니다. 아래 트리에서 빨간 노드와 하늘색 노드의 LCA는 초록색 노드가 됩니다. "트리 노드의 부모 노드는 유일하므로 루트를 향해 거슬러 올라가면서 가장 처음으로 공통된 노드를 찾자!" 아이디어를 기반으로 좀 더 빠르게 위로 올라갈 수 없을까 하는 고민이 생기게 됩니다. 효율.. 2020. 9. 22. [BOJ] 백준 3176번: 도로 네트워크 백준문제 3176번: 도로 네트워크 문제 N개의 도시와 그 도시를 연결하는 N-1개의 도로로 이루어진 도로 네트워크가 있다. 모든 도시의 쌍에는 그 도시를 연결하는 유일한 경로가 있고, 각 도로의 길이는 입력으로 주어진다. 총 K www.acmicpc.net 이번 포스팅은 LCA와 LCA에서의 노드간 가중치, 특성 등을 다루는 방법을 논의한다. LCA는 공통 부모노드를 찾는 알고리즘으로 2^i 번째 부모노드만을 고려하여 ( i >= 0, 인 정수) 의 lgN 복잡도로 빠르게 수행 가능하다. 이때 두 노드를 잇는 경로에서 각 경로의 distance (cost)를 다루는 문제에서 j번째 노드부터 2^i번째 부모까지의 거리 요소를 dist[i][j]로 저장하면 역시 lgN의 복잡도로 다룰수있다. (LCA찾는 .. 2020. 7. 5. 이전 1 다음
