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<=n;i*=2)
    {
        if(depth & i) A = d[A][power];
        ++power;
    }
    return A;
}
int LCA(int A, int B) // depth[A] > depth[B] 가정
{
    // A와 B의 높이를 맞춘다.
    A = goUpward(A, depth[A]-depth[B]);

    if(A==B) return A;

    for(int i=[lg n];i>=0;--i)
        if(d[A][i]!=d[B][i]) A=d[A][i], B=d[B][i];
    return d[A][0];
}

- 문제

1. 11437

2. 11438

3. 2014

4. 3090

5. 3119