LCA

LCA는 Least Common Ancestor의 약자이다. Tree에서의 공통 조상을 찾는 문제에 사용되는 알고리즘이다. 공통 조상이 여러개 있을 수 있으므로, 그 중에 제일 빠른 조상을 LCA로 정의한다. input으로는 서로 다른 두 Node가 주어진다. 이 두 Node를 l과 r이라 하자.

O(n^2)

만약 Node의 depth를 모른다면 이 방법밖에 사실 사용할 수가 없다. 각 l에 대해(l이 root가 될 때까지) 모든 r을 순회한다. 코드를 보면 알겠지만 무조건 찾을 수밖에 없다.

for(Node* l = sl; l != 0; l = l->parent) {
    for(Node* r = sr; r != 0; r = r->parent) {
        if (l == r) return l;
    }
}

O(n)

만약 depth를 안다면, l과 r의 depth를 같게 맞춘 이후에, 양쪽 Node를 만날 때까지 같이 올리면 된다. 구현의 편의를 위해 처음에는 무조건 l의 depth가 크도록 swap을 하는 것이 편하다. 이렇게 구현하면 2중포문이 없기 때문에 worst는 O(n)이다.

if (l->depth < r->depth) swap(l, r);
while(l->depth > r->depth) l = l->parent;
for(;;l = l->parent, r = r->parent) {
    if (l == r) return l;
}

O(log n)

O(log n)로 구현하려면 아래 2진수의 동작방식을 이해할 필요가 있다.

2진수의 힘

당연한 소리지만, 2진수는 모든 10진수를 나타낼 수 있다. 만약에 임의의 Node에 대해서 부모를 적절하게 저장하면 부모로 올라가는 과정을 O(n)이 아닌 O(log n)으로 할 수 있다. 바로, 부모를 저장하는데, 전체 부모를 저장하는 것이 아니라, 1, 2, 4, 8, 처럼 2진수에 쓰이는 숫자의 부모들을 저장하는 것이다. 이렇게 저장하면, 만약 특정 노드의 8번째 부모를 구한다고 했을 때, 특정노드의 4번째 부모의 4번째 부모를 구하는 식으로 생각할 수 있게 된다. 이렇게만 저장해도, 7 = 0111(2진수로) 이기 때문에, 모든 임의의 자연수의 부모를 O(log n) 시간에 찾을 수 있게 된다. 이를 쉽게 구현하기 위해서는 bitmask를 사용하면 된다. 임의의 수만큼의 부모로 가는 코드는 아래와 같다.

struct Node {
    Node* parents[10]; // 최대 2^9의 부모를 저장한다.
};
Node* findParent(Node* cur, int num) {
    int mask = 0x1;
    for(int i = 0; i < 10; ++i, mask <<= 1) {
        if (num & mask) cur = cur->parents[i]; // 2의 지수승만큼의 부모로 이동한다.
    }
    return cur;
}

2^k의 부모를 저장하는 것은 코드상 node->parents[k]를 보는 것으로 구현이 된다. 이를 활용하면 LCA도 구현할 수 있다. 위 테크닉을 활용한다.

if (l->depth < r->depth) swap(l, r);
int diff = l->depth - r->depth;
// 1. depth를 맞춰준다.
int mask = 0x1;
for(int i = 0; i < 10; ++i, mask <<= 1) {
    if (num & mask) l = l->parents[i]; // 2의 지수승만큼의 부모로 이동한다.
}
if (l == r) return l;
// 2. 같아지기 직전까지 올라간다.
for(int i = 10 - 1; i >= 0; --i) {
    Node* nl = l->parents[i];
    Node* nr = r->parents[i];
    if (nl == nr) continue;
    l = nl; r = nr;
}
while(l != r) {
    l = l->parents[0];
    r = r->parents[0];
}
return l;

그런데, 설명중에 한가지 빠뜨린 것이 있다. parents[]의 초기화는 어떻게 할 것인가? 이를 쉽게 하기 위해서는 아래와 같은 수식을 활용한다.

2^k = 2^(k-1) + 2^(k-1)

사실 당연한 수식인데, 생각하긴 사실 쉽지 않다. 이 수식을 활용해서 parents[]를 초기화 할 수 있다.

for(int i = 0; i < 10; ++i) {
    if (n->parents[i - 1] != nullptr)
        n->parents[i] = n->parents[i - 1]->parents[i - 1];
    else n->parents[i] = nullptr;
}

새로운 값이 추가될 때, 위와 같이 Node를 업데이트 하면 된다. 만약 Add가 다 된 상태에서 parents[]를 채워야 한다면, root 부터 시작해서 자식으로 채우면 된다.