LCA (Lowest Common Ancestor)

LCA는 이름에서 알 수 있듯이 두 정점 A와 B에서 가장 가까운 공통된 조상을 찾는 알고리즘입니다. 여기에는 2 가지 방법이 있는데요, 하나씩 조상 노드를 살펴보는 방법과 DP를 사용하는 방법이 있습니다. 트리의 depth를 H라고 할 때, 조상 노드를 하나씩 살펴보는 방법으로는 보통 시간복잡도가 O(H)가 나오지만, 최악의 경우 O(N)이 걸릴 수 있습니다. 하지만 DP를 사용하게 된다면? 보통 O(log H)가 걸리지만, 최악의 경우 O(log N)이 걸립니다. DP를 사용하는게 훨씬 빠르죠?

 

그래서 노드의 개수가 매우 많고, 검사해야할 노드가 매우 많은 경우에 DP를 사용한 방법을 활용하면 빠르게 답을 찾을 수 있습니다!

 

 

먼저, 조상 노드를 하나씩 살펴보는 방법은 사실 간단해요.

두 정점 A와 B의 depth를 맞춥니다. 즉, B의 depth가 A의 depth보다 깊은 경우 B의 조상 중에 depth가 A의 depth인 노드를 B에 넣어주는 거죠.

 

 

만약 이런 그래프에서 A가 2, B가 4라면? 노드2와 같은 depth인 3을 B로 두는겁니다.

 

 

 

 

그리고 나서 A와 B 모두 조상 하나씩 위로 올라가보면서 공통인지 아닌지를 검사하는 거죠!!

 

---

 

하지만 저는 DP를 사용한 방법을 보겠습니다^^.. 어차피 같은 알고리즘이라면 좀 더 효율적인 방법을 보자구요!

DP 사용해도 방법은 비슷합니다. 다만 해당 노드의 2^k 위의 조상까지 저장을 해주는 거죠.

 

 

1. 먼저 트리의 depth보다 작거나 같은 수 중에서 가장 큰 2^k의 k를 구합니다. 만약 depth가 3이라면 k=1, depth가 8이라면 k=3이겠죠.

 

 

 

2. DP를 사용해서 sparse table을 만듭니다. 이 때, table[k][v]는 v로부터 2^k만큼 위에 있는 조상 노드를 말합니다. v로부터 2^k만큼 위에 있는 조상이라면, v로부터 2^(k-1)만큼 위에 있는 조상의 2^(k-1)만큼 위에 있는 조상이겠죠? 즉, table[k][v] = table[k-1][table[k-1][v]]이 됩니다.

 

사실 여기서 엥?? 이게 뭔말?? k-1은 뭐고 뭐가 뭐....??? 음..??? 하실 수 있어요. 조금 복잡하기는 하지만 아래 그림을 보면 이해하실 수 있을 거예요!

만약 위의 그래프를 Sparse Table로 나타낸다면 아래와 같은 표가 만들어질 것입니다.

노드20의 2^2 = 4번째 위에 있는 조상은 노드20의 2^1 = 2번째 위에 있는 조상인 노드15의 2^1 = 2번째 위에 있는 조상을 가리킵니다. 2^k는 2배씩 늘어나기 때문에 2^(k-1)은 2^k와의 중간에 위치하기 때문에 여기서 노드15는 그 중간에 있는 노드가 되죠... 아.. 글로 설명하려니 정말 힘드네요. 쓰고 있는 저도 무슨 말인지 헷갈릴 정도ㅋㅋㅋ

 

그래도 그림을 보고 계속 이해하려고 노력해주세요ㅠㅠㅠㅠ

 

 

 

3. 그럼 이제 A와 B의 depth를 맞춰줍니다. 우리는 예시를 들어서 A=18, B=6 이라고 해볼게요.

A(노드18)의 depth는 5이고, B(노드6)의 depth는 2입니다. 그럼 A의 depth를 2로 맞춰줘야겠죠? 그럼 우리는 k=2부터 k=0까지 차례대로 봐줄거예요. A의 depth가 B의 depth와 같아질 때까지 아래와 같은 과정을 반복해줍니다.

 

table[2][18] = 2 👉노드2의 depth는 1입니다. B의 depth인 2보다 얕기 때문에 적합하지 않습니다.

table[1][18] = 10 👉노드10의 depth는 3입니다. B의 depth보다 깊네요? 그럼 A=10으로 저장해줄게요.

 

그럼 다시 k=2부터 살펴보겠습니다.

table[2][10] = 0 👉 없는 노드니까 적합하지 않습니다.

table[1][10] = 2 👉마찬가지로 B의 depth보다 얕기 때문에 적합하지 않습니다.

table[0][10] = 5 👉노드5의 depth는 2입니다. B의 depth와 같네요? 그럼 A=5로 저장해주고, 이 반복과정을 마칩니다.

 

이렇게 depth가 맞춰진 A와 B는 각각 노드5, 노드6이 되었습니다.

 

 

 

4. 마지막으로 A와 B의 조상이 같아질 때까지 조상을 하나씩 살펴봐줍니다. 이번에는 k=0부터 k=2까지 차례대로 봐볼게요.

 

A: table[0][5] = 2

B: table[0][6] = 2

 

앗. k를 더 봐줄 필요 없이 벌써 답이 나왔네요! 이렇게 해서 노드18과 노드6의 LCA는 노드2가 나왔습니다.

 

 

 

만약 트리가 크고 노드가 많은 경우 depth를 같게 맞춘 후에도 조상이 같은지 하나씩 올라가면서 보는게 아니라 2^k의 조상이 같은지 2^k만큼의 조상을 하나씩 검사해줄 수도 있습니다.

 

이 경우에는 그래프가 엄청 커다랗고, LCA의 마지막 단계에서 만약 table[k][a] == table[k][b] 인 노드가 나오더라도, 이 노드가 최소 조상 노드인지는 알 수 없습니다. 여기서 k는 1번째, 2번째, 4번째, 8번째, 16번째... 이렇게 조상을 찾기 때문에 그 사이에 최소 조상이 있을 수도 있기 때문이죠. 따라서 만약 table[4][a] == table[4][b]가 된다면, table[3][a]와 table[3][b]부터 다시 k=0부터 시작하여 최소 조상 노드를 찾아보다가 table[0][a'] == table[0][b'] 인 노드를 찾는 것이 중요합니다 :)

 

 

 

 

 

 

 

---

예전에 삼성 SDS 알고리즘 특강에서 LCA를 다뤘을 때는 머리가 너무 복잡해져서 사실 이해하기가 쉽지 않았어요ㅠㅠ 뭔가 이해하다가 정신줄을 놓아버렸던 기억이... 그래서 나중에 다시 봐야지~ 하다가 이제야 보게 됐네요. 근데 이번에 다시 처음부터 천천히 살펴보니 LCA 알고리즘도 막 그렇게 엄청 어려운 개념은 아니었더라구요?? 좀 복잡하긴 해도 예전만큼 이해 못할 정도는 아니었어요! 뭔가 점점 이해력이 성장하는 느낌🚀