tree 썸네일형 리스트형 [나만 몰랐던 알고리즘] MST 구하기 - Kruskal's Algorithm Minimun Spanning Tree는 모든 노드를 잇는 사이클이 없는 그래프 중 간선(edge)의 가중치 합이 최소가 되는 트리(그래프)이다. 글로 봤을땐 저게 뭔가 싶은데 그림으로 한번 보자 위 사진과 같은 그래프에서, 모든 노드를 포함하는 부분 그래프를 신장 부분 그래프라고 한다. 여기서 간선이 어떻게 연결되는지에 따라 여러개의 신장 부분 그래프를 만들 수 있는데, 이 중 간선의 합이 최소가 되는 신장 부분 그래프를 MST라고 하고, 오늘 정리할 알고리즘은 이 MST를 찾는 Kruskal 알고리즘이다. 알고리즘을 크게 정리하면, 모든 에지를 Cost 순으로 정렬되는 Priority Queue에 넣는다. PQ에서 하나를 뽑는다 -> 이 에지의 출발점과 도착점이 연결되어 있지 않다면 트리에 추가한다... 더보기 [나만 몰랐던 알고리즘] 최소 공통 조상, LCA 트리 구조에서 조상은 현재 노드 위에 있는 노드들이다. LCA(최소 공통 조상)은 말 그대로 공통 조상 중에서 가장 낮은(높이가 최소인) 조상을 말한다. 트리를 보면, 루트 노트 1은 깊이 0을 가지고, 9번 노드는 깊이 3을 가지는 것을 볼 수 있다. 여기서 10과 5의 공통 조상은 1, 3이 있고 최소 공통 조상은 3이다. LCA를 구하는 방법은, 나이브하게 접근하면 매번 트리를 타고 올라가면서 확인하는 방법이 있다. 가장 확실하지만 시간이 아주 오래 걸릴 수도 있다. 트리가 꼭 균형이 맞는다는 보장이 없으므로 심한 경우에는 노드 갯수만큼의 비교와 count가 필요하다. 따라서 많은 문제에서 LCA는 다른 방법으로 구하게 된다. LCA에서 가장 핵심이 되는 것은 배열 하나의 추가이다. DP와 비슷하다.. 더보기 이전 1 다음
