---
id: "imported/ps/algorithm/graph/lca"
title: "LCA"
description: "LCA는 Least Common Ancestor의 약자이다. Tree에서의 공통 조상을 찾는 문제에 사용되는 알고리즘이다. 공통 조상이 여러개 있을 수 있으므로, 그 중에 제일 빠른 조상을 LCA로 정의한다. input으로는 서로 다른 두 Node가 주어진다. 이 두 Node를 l과 r"
kind: "record"
published: "2023-05-24T00:00:00.000Z"
tags: ["LCA"]
url: "https://www.readiz.com/notes/algorithm/graph/lca/"
markdownUrl: "https://www.readiz.com/notes/algorithm/graph/lca/index.md"
---

# LCA

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

## O(n^2)

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

```cpp
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)`이다.

```cpp
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`를 사용하면 된다. 임의의 수만큼의 부모로 가는 코드는 아래와 같다.

```cpp
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`도 구현할 수 있다. 위 테크닉을 활용한다.

```cpp
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[]`를 초기화 할 수 있다.

```cpp
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` 부터 시작해서 자식으로 채우면 된다.