lca 썸네일형 리스트형 BOJ)1761 정점들의 거리 문제:icpc.me/1761 두 정점간의 최단거리를 매 쿼리마다 출력하는 문제이다. 우리가 기본적으로 알고 있는 그래프의 최단거리 알고리즘들은 시간복잡도 때문에 사용할 수가 없다. 하지만 우리는 이 그래프가 트리라는것을 이용하여 매 쿼리를 O(logN) 시간마다 처리해 줄 수있다. 우리는 lca를 이용하여 두 노드의 최단 거리를 계산할 것이다. lca전처리를 위해 dfs를 돌려줄 때 루트에서 부터 자기 자신까지의 거리를 dist배열에 저장해두면 두 노드의 X,Y 의최단 거리는 dist[X]+dist[Y]-2*dist[lca(X,Y)]로 정의 할 수있다. 이를 이용하여 매 쿼리를 logN시간에 처리해주면 된다. 12345678910111213141516171819202122232425262728293031.. 더보기 BOJ)3176 도로 네트워크 문제: icpc.me/3176 N개의 도시와 그 도시를 연결하는 N-1개의 도로 네트워크가 있을 때 두 도시를 연결하는 경로 상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 출력하는 문제이다. 우리는 모든 도시 쌍에는 그 도시를 연결하는 유일한 경로가 있다는데에서 주어진 그래프가 트리임을 유추할 수 있다. 우리는 문제를 해결하기 위하여 LCA를 이용할 것이다. 우리는 LCA를 구할 때 두 도시의 2^i번째 부모를 저장한다. 이 때 우리는 2^i번째 부모를 저장할 뿐만 아니라 x번째 정점 기준으로 2^i번째 부모까지의 모든 간선중에 최솟값과 최댓값을 같이 저장할 수 있다. 이를 이용하여 쿼리를 처리하면 문제를 해결할 수 있다. 1234567891011121314151617181920212223242.. 더보기 LCA(Lowest Common Ancestor) 1개 이상의 노드로 구성 된 사이클이 없는 그래프를 트리라고 합니다. 우리는 트리에서 정의되는 LCA(Lowest Common Ancestor)에 대해서 얘기해 보려 합니다. LCA를 직역하면 최소 공통 조상(?) 정도의 뜻으로 해석되며 두 정점에서 (자신을 포함한)조상들을 거슬러 올라갈 때 처음으로 공통되게 만나는 정점을 지칭합니다. 예를 들기 위해 다음과 같은 트리가 존재한다고 합시다. 이 트리에서 6번 정점과 10번 정점의 LCA를 구하면 다음과 같이 2번 정점이 6번 정점과 10번 정점의 LCA가 됩니다. 이번에는 7번 정점과 10번 정점의 LCA를 구해보겠습니다. 다음과 같이 1번 정점이 7번 정점과 10번 정점의 LCA가 됩니다. 자, 이제 어느정도 LCA의 정의에 대한 감이 오시나요? 마지막.. 더보기 BOJ)11438 LCA 2 문제:icpc.me/11438 이 문제는 LCA (BOJ 11437) 의 풀이도 포함한다. 루트의 번호가 1번인 N개의 정점으로 이루어진 트리가 존재할 때 두 노드의 쌍 M이 주어질 때 두 노드의 LCA를 구하는 문제이다. 여기서 LCA(Lowest Common Ancestor)란 직역하면 최소 공통 조상(?) 이다. 즉 트리의 두 노드가 주어졌을 때 서로의 조상을 거슬러올라갔을 때 가장 먼저 만나는 정점이 LCA가 된다. LCA를 구하는 방법으로 두 노드의 높이(깊이)를 맞춘후에 한칸씩 올라가며 조상이 같아질 때까지 비교하는 방법이 있다. 하지만 이방법은 한번의 쿼리를 처리할 때 O(N)의 시간복잡도를 가지므로 LCA 2문제 같이 M과 N이 10만이면 O(N*M)으로 TLE를 피하기 힘들것이다. 그래서.. 더보기 이전 1 2 다음
