목록최소공통 조상 (1)

Expert스터디 3.5일차(2016.06.06)

우선순위 큐다음 세 연산을 O(lg n)에 지원한다.insert(x)get_min()remove_min()이런 연산들을 지원하는 자료구조들로는 다음이 있다. 취향에 맞게 선택하면 된다.코딩 쉬움: heap코딩 어려움: AVL, Red-black tree 등의 Balanced Binary Search Trees최소공통조상우선 root를 정한다.d[node][0] = parent[node] d[node][i] = d [ d[node][i-1] ] [i-1] // node로부터 2^i 올라간 정점은 2^(i-1) 올라가고 2^(i-1) 올라간 것과 같다.int goUpward(int A, int depth) // A로부터 depth만큼 올라간 정점 { int power=0; for(int i=1;i depth..
Algorithm/그밖에2 2016. 6. 7. 22:02
이전 Prev 1 Next 다음