자바 코딩테스트 강좌, 최소 공통 조상 구하기 2

문제 설명

주어진 이진 트리에서 두 노드의 최소 공통 조상(LCA)을 찾는 문제는 다양한 알고리즘 문제 해결에서 중요하게 다뤄집니다. 이 문제는 특히 트리 구조를 이해하고 재귀적인 사고를 요구합니다. 이 글에서는 최소 공통 조상을 구하는 방법을 심층적으로 살펴보겠습니다.

문제 정의

이진 트리의 루트 노드와 두 노드 A, B가 주어질 때, A와 B의 최소 공통 조상을 찾는 문제를 해결해야 합니다. 최소 공통 조상은 다음 조건을 만족하는 가장 깊은 (최하위) 노드로 정의됩니다:

노드 A와 B의 모든 조상이 포함되어야 합니다.
노드 LCA는 A와 B가 위치한 서브트리 안에 존재해야 합니다.

제약 조건

주어진 이진 트리는 다음과 같은 제약을 가집니다:

노드의 수는 1 이상 10^4 이하입니다.
각 노드는 서로 다른 값을 가지고 있습니다.
A와 B는 반드시 트리에 존재하는 노드입니다.

문제 해결 전략

1. 트리 구조 이해하기

트리는 계층적 데이터 구조로 노드와 간선으로 구성됩니다. 이진 트리의 경우, 각 노드는 최대 두 개의 자식을 가질 수 있습니다. 트리의 깊이를 기반으로 최소 공통 조상을 찾기 위해 다음과 같은 자원을 확보해야 합니다.

2. 알고리즘 선택

후보 알고리즘으로는 DFS(Depth-First Search)를 사용할 수 있습니다. 이 접근 방식은 다음과 같은 단계로 진행됩니다:

루트 노드에서 시작하여 좌우 서브트리를 탐색합니다.
두 노드 A 및 B가 각각의 서브트리에 존재하는 경우, 현재 노드가 LCA가 됩니다.
A 또는 B가 하나의 서브트리에만 존재하는 경우, 해당 노드를 반환합니다.
둘 다 존재하지 않으면 null을 반환합니다.

파이썬 구현


# 이진 트리 노드 정의
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# LCA 찾기
def lowestCommonAncestor(root, p, q):
    if root is None:
        return None
    
    if root == p or root == q:
        return root
    
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    
    if left and right:
        return root
    return left if left else right

구현 설명

1. TreeNode 클래스

먼저, TreeNode 클래스를 정의하여 각 노드의 값을 저장합니다. 노드는 값 (val) 외에도 왼쪽 자식 (left)과 오른쪽 자식 (right) 노드를 각각 참조합니다.

2. lowestCommonAncestor 함수

주어진 루트 노드에서 시작하여 재귀적으로 호출하여 두 노드 A와 B의 LCA를 찾아냅니다. 기저 사례로는 노드가 null이거나 루트가 A 또는 B일 경우, 현재 노드를 반환합니다.

각각의 서브트리에서 LCA를 찾는 중이기 때문에, 왼쪽 서브트리와 오른쪽 서브트리에서 반환된 값이 모두 존재하면, 현재 노드가 LCA가 됩니다.

3. 문제 해결

이제 이 알고리즘을 사용하여 주어진 이진 트리의 두 노드 A, B에 대한 LCA를 찾을 수 있습니다. 알고리즘의 시간 복잡도는 O(N)이며, N은 노드의 수입니다.

성능 검증

이 알고리즘을 다양한 입력에 대해 테스트하여 성능을 검증할 수 있습니다. 예를 들어, 입력으로 다음과 같은 이진 트리를 고려해 볼 수 있습니다.


    # 예시 트리 생성
    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 = root.left         # Node with value 5
    q = root.left.right.right  # Node with value 4

    ancestor = lowestCommonAncestor(root, p, q)
    print(ancestor.val)  # Expected output: 5

결론

이번 강좌에서는 자바 코딩테스트의 중요한 개념 중 하나인 최소 공통 조상 구하기에 대해 심도 있게 다루었습니다. 이 알고리즘은 다양한 상황에서 활용될 수 있으며, 트리 구조를 이해하는 데 매우 유용합니다. 문제 해결 과정과 알고리즘 분석을 통해 코딩 테스트 대비에 도움이 되길 바랍니다.

추가적인 질문이 있다면 댓글로 남겨 주세요. 감사합니다!