42. lowest common ancester [15 2주차]

42. Lowest Common Ancester [15-2주차]

2024년 1월 14일 일요일

오후 5:34

<Lowest Common Ancester>

트리의 두 노드의 공통 조상 중 가장 낮은 곳에 위치하는 것을 찾는 문제이다.

 

<DFS, BFS 를 이용한 풀이>

노드 a, b의 공통 조상을 찾기 위해서는 DFS나 BFS를 사용하면 된다.

a에서 시작하여 b에 도달할 때까지 DFS또는 BFS를 실행한다. b를 방문하게 되면, a에서 b로의 경로가 구해진다. 해당 경로에서, 가장 높은 레벨의 노드가 LCA이다.

(노드마다 해당 노드가 위치한 레벨이 저장되어 있다고 가정한다)

 

O(n)시간이 걸린다.

 

 

<빠른 알고리즘>

각각의 노드가 자신의 1칸, 2칸, 4칸, 8칸, … 위의 조상 노드 번호를 저장한다.

A[i][j] : i번 노드의 2^j 칸 위의 노드 번호. 1<= i <= n, 0<= j <= logn

 

ex) A[i][0] 은 i번 노드의 부모 노드 번호이다.

 

A[i][j+1] = A[A[i][j]][j] 가 성립한다.

• 설명 : 예를 들어 설명하자면, A[i][3] = A[A[i][2]][2] 가 성립한다.

i번 노드의 8칸 위의 노드(A[i][3])는 i번 노드의 4칸 위의 노드의 4칸 위 노드 A[A[i][2]][2] 와 같다.

 

위 등식을 이용하여 위 레벨의 노드부터 아래 레벨의 노드까지 A값을 구하면 총 O(nlogn) 시간이 걸린다. 이는 위 DFS, BFS를 이용한 방법보다 오래 걸리지만, 일단 A값을 구하고 나면, 다음부터는 어떤 노드의 공통 조상이든 더 빠르게 구할 수 있다.

 

노드 a와 b의 최저 공통 조상이 x이고, a가 더 낮은 층에 있다고 하자. 이때, 알고리즘은 다음과 같이 동작한다.

 

a에서 b와 같은 레벨이 될 때까지 위로 올라간다. 올라간 노드를 a' 이라 한다.

 

a', b로부터 A의 링크를 타고 최대한 위로 올라간다. 2^j칸 올라갔다면 A[a'][j]와 A[b][j]에 도달하게 된다.

A[a'][j] 와 A[b][j]의 값이 같다면 j를 1감소시키고 다시 비교한다.

이를 통해 A[a'][j] ≠ A[b][j] 를 만족하는 j의 최댓값 j'을 찾는다.

그 j'에 대한 위치로 이동한다. a'' = A[a'][j'], b'' = A[b][j'] 이라 하자.

a''과 b''에 대해서도 a'과 b에서 했던 것처럼 링크를 타고 올라간 뒤 내려가며 비교하는 과정을 재귀적으로 수행한다. 단, 맨 처음 올라갈 때 최대한 위로 올라가는 대신 2^j'칸만 올라간다.

이러한 재귀 실행을 통해 최초로 조상이 같아지는 순간을 찾으면 된다.

 

이를 통해 LCA를 찾는 데 O(logn)시간이 걸린다.

 

 

<더 빠른 알고리즘>

O(n) 전처리 시간에 O(1) query 시간을 가지는 알고리즘도 존재한다.

 

위 알고리즘은 노드 두 개가 조상, 자손 관계인지 판단하는 알고리즘을 사용한다.

 

자세한 설명은 생략.

 

 

<LCA의 적용>

트리에서 모든 쌍의 shortest path 를 구하는 문제를 풀어 보자.

 

모든 노드에 대해 다익스트라 실행 : 원래는 O(nmlogm) 시간이 걸려야 하나, 트리의 특성에 의해 n~=m 이고 logm이 빠질 수 있어 O(n²)이 걸린다.

 

LCA 사용 : 가장 빠른 LCA 알고리즘을 사용한다면 O(n) + n² * O(1) = O(n²) 시간이 걸린다.