LCA 썸네일형 리스트형 백준 1626 두 번째로 작은 스패닝 트리 LCA - 최소 공통 조상을 사용하는 문제이다. 두 번째로 작은 스패닝 트리를 구할 때, MST에 포함되어있지 않은 에지를 골라서 그 에지가 잇는 두 노드의 경로 중 최대값 에지를 빼는 과정이 필요하다. 두 노드의 최단 경로를 찾을 때 LCA 알고리즘을 사용한다. 여기에, "두 번째로 작은" 이라는 조건이 붙으므로, 추가된 에지 비용과 경로 중 최대값 에지의 비용이 같으면 안된다. 그 다음으로 큰 에지를 골라야 한다. 여기까지 생각해보면, LCA에서 사용한 parents[K][V] 배열은 그대로 있어야 하고, path[K][V]를 만들어서 V에서 2^K 조상까지의 경로를 벡터형식으로 저장을 하면 좋을 것 같다. 나중에 두 노드에서 LCA까지 경로를 전부 아니까 거기서 MST 비용보다 큰 노드를 찾기만 하.. 더보기 백준 15481 그래프와 MST 역시 LCA를 활용하는 문제이다. 저번 정점들의 거리 문제에서 MST의 개념을 살짝 붙이기만 하면 방법을 찾을 수 있다. 에지를 입력받을 때, 인접 행렬을 직접 만드는 것이 아니라, 에지만 저장하는 벡터/배열을 선언하고 나중에 그 에지들을 순회하며 MST를 찾을 수 있게 한다. std::vector adj[N]; std::priority_queue pq; std::vector vEdgeList; 일단 에지를 입력받고 난 다음, 그 에지들을 사용해 MST를 계산한다. MST를 계산하면서 adj(인접행렬)을 채워 이 트리를 사용해 LCA를 구하게 된다. for (int i = 0; i > s >> e >> c; s--; e--;.. 더보기 백준 1761 정점들의 거리 LCA를 활용하는 문제이다. LCA 분류 문제만 풀다보니 거의 같은 코드에 조금만 바꾸는 느낌이 계속 든다. 근데 LCA 알고리즘은 진짜 신기한것 같다. 관련 포스팅을 몇개 연속해서 써도 얘가 돌아가는 매커니즘이 계속 신기하다. 2진수 사고방식을 쉽게 머리속에서 굴릴 수 있는 사람이 처음 만든 것 같은데, 어쩜 저런 생각을 했는지... 각설하고. 이번 문제는 이전에 있었던 도로 네트워크 와 거의 유사하다. 중간중간 코드 몇줄만 바꿀정도. LCA에 대한 개념부터 보고싶다면 LCA 설명 글도 있다. 도로 네트워크에서는 parents[] 배열 이외에 pathMax[K][V], pathMin[K][V] 배열이 존재해 각각 2^K 번째 노드까지 경로 중 cost가 최소인 것과 최대인 것을 저장했었다. 이 문제에서.. 더보기 백준 3176 도로 네트워크 LCA를 활용하는 문제이다. 두 도시를 연결하는 경로는 LCA를 통해 구할 수 있다. 두 노드 u, v에서 LCA까지 이르는 경로를 합치면 두 도시를 있는 최소 경로가 된다. LCA 2 에서는 parents[] 배열에 2^K 번째 부모 노드들을 저장했었는데, 이것을 응용해 2^K 번째 부모 노드까지의 경로에서 에지의 최소값을 저장하는 배열과 최대값을 저장하는 배열을 만들기만 하면 문제를 해결할 수 있다. LCA 2에서 달라질것은, pathMax[] 배열과 pathMin[] 배열을 새로 만든것과, Parents[] 배열을 초기화하거나 갱신할때 새로 만든 두 배열도 값을 넣어준다는 것, 두 노드의 높이를 맞춰주거나 맞춘 후 위로 탐색할때 u와 v가 움직이는것에 맞춰 탐색되는 경로 상 최대/최소값을 찾아준다는.. 더보기 [나만 몰랐던 알고리즘] 최소 공통 조상, LCA 트리 구조에서 조상은 현재 노드 위에 있는 노드들이다. LCA(최소 공통 조상)은 말 그대로 공통 조상 중에서 가장 낮은(높이가 최소인) 조상을 말한다. 트리를 보면, 루트 노트 1은 깊이 0을 가지고, 9번 노드는 깊이 3을 가지는 것을 볼 수 있다. 여기서 10과 5의 공통 조상은 1, 3이 있고 최소 공통 조상은 3이다. LCA를 구하는 방법은, 나이브하게 접근하면 매번 트리를 타고 올라가면서 확인하는 방법이 있다. 가장 확실하지만 시간이 아주 오래 걸릴 수도 있다. 트리가 꼭 균형이 맞는다는 보장이 없으므로 심한 경우에는 노드 갯수만큼의 비교와 count가 필요하다. 따라서 많은 문제에서 LCA는 다른 방법으로 구하게 된다. LCA에서 가장 핵심이 되는 것은 배열 하나의 추가이다. DP와 비슷하다.. 더보기 이전 1 다음
