godvicii   7달 전

보통 아래에서 부모 하나씩 올리면서 Depth를 맞춘후 동시에 부모를 올리면서 공통조상을 찾았는데,

특정 케이스에 대해 시간이 많이 잡아먹히더군요.

O(logN)번만에 하는 방법이 있다던데 혹시 아시는분들은 가르쳐주실수 있나요?

algogogo   7달 전

다이나믹 프로그래밍을 이용하여 O(logN)의 시간복잡도로 LCA문제를 해결할 수 있습니다.

D[i][j] : i 노드의 2^j 번째 조상 이라고 정의하면,

D[i][0] = i 노드의 부모노드

D[i][j] = D[D[i][j-1]][j-1] 이 됩니다.


말씀하신 기존의 LCA를 찾는 방식인 부모노드를 하나씩 올리며 찾는 방법에서 ->

두 노드의 레벨이 다를 때, 레벨이 같아질 때까지 더 큰 레벨에 있는 것을 2^k 씩 위로 올리고

-> 두 노드의 레벨이 같아지면, 그 다음에는 같은 노드가 될때까지 2^k씩 위로 올려주면 됩니다.

따라서 이 경우, 최악의 경우에도 O(logN)로 문제를 해결할 수 있습니다.


아래 간단한 소스 코드를 첨부합니다.

감사합니다.

plzrun   7달 전

appa   7달 전

algogogo님께서 적으신 글에 이어서 D배열을 다 구했다면, 아래와 같은 과정을 거쳐서 두 노드 a와 b의 최소높이공통조상을 찾을 수 있습니다.

http://hongjun7.tistory.com/49

parent[x][y] : 노드 y의 2^x 높이 위의 조상노드 ( 위에 algogogo님께서 적으신 댓글의 D[y][x]와 정의가 같습니다.)

제 코드를 보시면 lca 함수 내에서 for문이 K에서 0까지 수행하다가 높은 높이에서부터 분기되는(부모가 달라지는) 최초의 지점에 대해 재귀적으로 작동합니다.

이 때 해당 높이(2^i 위에서 갈라졌을 때의 i)에 관한 정보를 인자로 넣어주어 그 다음 for문에서는 i에서부터 0까지 수행하므로 총 (log 트리의 높이)만큼의 시간이 걸리게 됩니다.

kimdr123   7달 전

우오.. 클래스.. 

댓글을 작성하려면 로그인해야 합니다.