문제https://www.acmicpc.net/problem/13511시간 제한메모리 제한solved.ac 티어2초512MB플래티넘 3풀이 이 문제는 처음에 희소 테이블을 이용하는 문제인 줄 알았지만, 해보다보니 LCA를 응용해야하는 문제임을 알았다. (태그 까보고...) 임의의 두 노드 u, v에서 u -> v로 가는 경로라 함은 암묵적으로 최단경로를 의미한다. 그렇다면 u -> v의 경로는 LCA를 반드시 거칠 것이다. LCA를 구하기 위한 희소 테이블에 해당 조상으로 가기 위한 경로의 비용도 같이 저장한다. 이렇게 하면 LCA와 비용 모두 빠르게 구할 수 있다. 쿼리를 분석해보자. 1번 쿼리는 u -> v로 가는 경로의 비용을 출력하는 쿼리이다. u -> v의 경로는, u -> LCA_uv ->..
문제https://www.acmicpc.net/problem/3584시간 제한메모리 제한solved.ac 티어1초128MB골드 4풀이 밀린 문제 정리하기 LCA편이다. 사실 앞에 정리한 두 문제 11437, 11438번 문제보다도 더 쉬운 문제이다. 단순 난이도로 따지면 3584 문제 조건에 해당 트리는 루트가 있는 트리라고 했기 때문에, 맨 처음 트리를 초기화할 때, 부모가 있는 노드들을 제외한 하나의 노드만이 루트일 것이다. 해당 노드에서부터 트리를 초기화하면 된다.코드#include #define endl '\n'using namespace std;#define MAX_A 15int n,m;vector> tree, graph;vector depths;int target, goal;void mak..
문제https://www.acmicpc.net/problem/11438시간 제한메모리 제한solved.ac 티어1.5초256MB플래티넘 5풀이 밀린 문제 정리하기. LCA 알고리즘 편이다. 저번 문제에서는 O(n) LCA 로 풀 수 있는 문제였지만, 이 문제는 정말 불가능한 문제이다. 겸허히 O(log(N)) LCA를 사용해야 한다. O(n) LCA의 문제는 부모 노드로 이동하기 위해, 본인의 조상 노드를 하나씩 움직여야 하기에 선형시간이 걸리지만, 높이가 클 수록 비효율적일 것이다. 여기서 하나의 의문이 발생한다. 굳이 하나씩 다 이동해야 하는가? 이를 해결하기위해 희소테이블을 사용한다. 트리의 데이터를 저장할때, 본인의 부모노드만 저장했지만, 희소테이블을 적용하여, i번째 노드의 2^0번째 부모, ..
문제https://www.acmicpc.net/problem/11437시간 제한메모리 제한solved.ac 티어3초256MB골드 3풀이 밀린 문제 정리하기. 이번엔 LCA라는 알고리즘편이다. 원래 좀 늦게 정리하려 했는데, 어제 LCA를 활용하는 문제를 푼 김에 정리해본다. LCA 알고리즘은 Lowest Common Ancestor의 약자로, 최소 공통 조상이라는 뜻이다. 사이클 없는 무방향 그래프, 즉 트리에서 임의의 두 노드의 부모 노드를 쭉 나열해보면, 어느 순간 공통된 조상을 가질 것이다. 이중에서, 가장 아래에 있는.... 그러니까 우리가 선택했던 임의의 두 노드 각각과 제일 가까운 부모 노드를 찾는 알고리즘이다. 그래서 최소의 공통된 조상을 찾는 알고리즘이다. 나중에 알고리즘들을 숙달한다면 ..
