n개의 노드(0부터 n-1까지 번호가 매겨짐)로 구성된 트리가 있다고 가정해 보겠습니다. 트리는 parent 배열로 주어지며, parent[i]는 노드 i의 부모 노드를 나타냅니다. 트리의 루트는 0번 노드입니다. 우리가 해야 할 일은 주어진 노드의 k번째 조상을 찾는 것이고, 만약 해당 조상이 존재하지 않는다면 -1을 반환하면 됩니다.
예를 들어 입력이 다음과 같다고 해보겠습니다.
그렇다면 출력은 2가 됩니다. 노드 6의 첫 번째 조상은 5이고, 두 번째 조상은 2이기 때문입니다.
문제 해결 접근 방식
이 문제는 단순히 k번 반복하며 부모를 따라 올라가는 방법(O(k))보다 더 효율적으로 풀 수 있습니다. 핵심 아이디어는 분할 정복(Divide and Conquer)을 활용하는 것입니다.
solve() 함수를 정의합니다. 이 함수는 parent, node, k 세 개의 인자를 받습니다.
node가 -1이라면(루트 위로 더 올라갈 수 없다면) -1을 반환합니다.
k가 1이라면 바로 parent[node]를 반환합니다.
k와 (k-1)의 비트 AND 연산 결과가 0이라면, 즉 k가 2의 거듭제곱이라면 문제를 절반으로 나눕니다.
→ solve(parent, solve(parent, node, k/2), k/2)를 반환합니다.그 외의 경우에는 k에서 최상위 비트(msb)만큼 떼어낸 뒤 처리합니다.
→ msb = 2^(k의 비트 길이 - 1)로 계산하고, solve(parent, solve(parent, node, k-msb), msb)를 반환합니다.
이 방식은 매 단계마다 k가 절반으로 줄어들거나 최상위 비트가 제거되므로, 전체 시간 복잡도가 O(log k)로 크게 개선됩니다.
구현 예시
아래 구현을 통해 더 잘 이해해 보겠습니다.
def solve(parent, node, k):
if node == -1:
return -1
elif k == 1:
return parent[node]
elif not (k & k-1):
return solve(parent, solve(parent, node, k >> 1), k >> 1)
else:
msb = 1 << (k.bit_length()-1)
return solve(parent, solve(parent, node, k-msb), msb)
parent = [-1,0,0,1,2,2,5,5]
node = 6
k = 2
print(solve(parent, node, k))입력
parent = [-1,0,0,1,2,2,5,5], node = 6, k = 2
출력
2