파이썬 코딩테스트 강좌, 최소 공통 조상

안녕하세요! 이번 강좌에서는 알고리즘 문제 중 하나인 ‘최소 공통 조상(LCA, Lowest Common Ancestor)’에 대해 알아보겠습니다. 최소 공통 조상 문제는 트리 구조에서 두 노드가 주어졌을 때, 이 두 노드의 가장 가까운 공통 조상을 찾는 문제입니다. 이 문제는 다양한 분야에서 매우 중요하며, 많은 면접에서도 자주 출제되곤 합니다.

문제 설명

주어진 이진 트리(이진 탐색 트리 포함)에서 두 노드의 값이 주어질 때, 이 두 노드의 최소 공통 조상을 찾으세요.

입력

노드의 수 N (1 ≤ N ≤ 1000)
N개의 노드의 값
두 개의 노드 값 A, B (A, B는 트리에 존재함)

출력

두 노드의 최소 공통 조상의 값을 출력합니다.

문제 이해하기

최소 공통 조상 문제는 트리를 구성하는 데이터 구조의 특성과 노드의 상관 관계를 이해하는 데 도움이 됩니다. 공통 조상이란 두 노드에서 공통적으로 올라가면서 만나는 노드를 의미합니다. 예를 들어, 트리가 다음과 같다고 가정해보겠습니다.

              3
            /   \
          5      1
         / \    / \
        6   2  0   8
           / \
          7   4

이 트리에서 5와 1의 최소 공통 조상은 3이며, 6과 4의 최소 공통 조상은 5입니다.

해결 전략

최소 공통 조상을 찾는 기본적인 방법은 아래와 같습니다:

트리를 순회하며 주어진 두 노드의 경로를 저장합니다.
각 경로에서 마지막으로 만나는 노드를 찾습니다.

이 방법은 직관적이고 간단하지만, 비효율적인 경우가 있습니다. 대신에 아래와 같은 좀 더 효율적인 방법을 사용할 수 있습니다.

효율적인 방법

이진 트리에서 LCA를 찾는 효율적인 방법으로는 깊이 우선 탐색(DFS)을 이용한 방법이 있습니다. 이 방법은 주어진 두 노드의 값을 가진 노드들을 재귀적으로 탐색하며, 양쪽 노드가 발견되면 그 노드를 반환합니다.

코드 구현

이제 우리는 이 알고리즘을 파이썬으로 구현해보겠습니다. 다음은 LCA를 찾기 위한 코드입니다:


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def lowest_common_ancestor(root, p, q):
    # 기저 조건
    if not root or root == p or root == q:
        return root

    # 왼쪽과 오른쪽에서 LCA를 재귀적으로 찾기
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)

    # 각 자식 노드가 존재하는 경우
    if left and right:
        return root
    return left if left else right

# 테스트 케이스
if __name__ == "__main__":
    # 트리 구성
    root = TreeNode(3)
    root.left = TreeNode(5)
    root.right = TreeNode(1)
    root.left.left = TreeNode(6)
    root.left.right = TreeNode(2)
    root.right.left = TreeNode(0)
    root.right.right = TreeNode(8)
    root.left.right.left = TreeNode(7)
    root.left.right.right = TreeNode(4)

    # 노드 p와 q 설정
    p = root.left  # 5
    q = root.right  # 1

    # LCA 계산
    lca = lowest_common_ancestor(root, p, q)
    print(f"최소 공통 조상: {lca.val}")

알고리즘 분석

이 알고리즘은 트리의 각 노드를 한 번만 방문하므로, 시간 복잡도는 O(N), 공간 복잡도는 O(H)입니다. 여기서 N은 노드의 수이고, H는 트리의 높이입니다. 최악의 경우에는 H가 N과 같으므로, 전체적인 시간과 공간 복잡도는 O(N)입니다.

결론

이번 강좌에서는 최소 공통 조상 문제에 대해 알아보았습니다. 이 문제는 많은 경우의 수를 고려해야 하지만, 올바른 알고리즘을 통해 간단히 해결할 수 있습니다. 실제 문제를 해결할 때는 트리의 구조와 노드 간의 관계를 확실히 이해한 후에 접근하는 것이 중요합니다. 다음 강좌에서는 다른 알고리즘 문제를 다뤄보겠습니다. 감사합니다!