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

안녕하세요, 여러분! 오늘은 파이썬을 이용한 코딩 테스트에서 자주 등장하는 문제 중 하나인 “최소 공통 조상 구하기”에 대해 알아보겠습니다. 이 강좌에서는 최소 공통 조상을 의미하는 ‘Lowest Common Ancestor (LCA)’를 찾는 알고리즘에 대해 상세히 설명하며, 관련된 예제 문제 및 그 해결 과정을 함께 살펴보겠습니다.

1. 문제 정의

주어진 이진트리에서 두 노드 A와 B의 최소 공통 조상을 찾는 문제입니다. 최소 공통 조상이란 두 노드를 동시에 부모로 가지는 가장 깊은 노드를 의미합니다. 예를 들어, 다음과 같은 이진트리가 있다고 가정해봅시다.

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

위 트리에서 노드 5와 노드 1의 최소 공통 조상은 노드 3입니다. 그러나 노드 5와 노드 4의 최소 공통 조상은 노드 5입니다.

2. 문제 요구 사항

  • 입력: 이진트리의 루트 노드와 두 노드 A, B
  • 출력: A와 B의 최소 공통 조상 노드를 반환

3. 알고리즘 접근법

최소 공통 조상을 찾기 위한 여러 접근법이 있지만, 가장 간단한 방법은 DFS(깊이 우선 탐색)를 이용하는 것입니다. DFS 알고리즘을 사용하면 각 노드를 방문하면서 A와 B를 찾고, 두 노드의 공통 조상을 추적할 수 있습니다.

3.1 DFS 탐색 방법

DFS를 사용하여 이진트리를 탐색하면서 현재 노드가 두 노드 A와 B 중 하나와 일치하는지 확인합니다. 일치하는 경우 해당 노드를 반환합니다. 그렇지 않다면 두 개의 서브트리에서 각각 A와 B를 찾습니다. 다음 단계로 이 두 서브트리의 결과를 결합하여 최소 공통 조상을 찾습니다.

3.2 구현

이제 문제를 해결하기 위한 코드를 작성해 보겠습니다.


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

def lowest_common_ancestor(root, node1, node2):
    if root is None:
        return None

    # base case: if the current root is one of the nodes
    if root == node1 or root == node2:
        return root

    # look for node1 and node2 in the left and right subtrees
    left_lca = lowest_common_ancestor(root.left, node1, node2)
    right_lca = lowest_common_ancestor(root.right, node1, node2)

    # If both left_lca and right_lca are not None, it means
    # one node is present in one subtree and the other is present in the other subtree
    if left_lca and right_lca:
        return root

    # Otherwise return the non-null value
    return left_lca if left_lca is not None else right_lca

4. 코드 설명

먼저, 이진 트리의 각 노드를 나타내는 TreeNode 클래스를 정의합니다. 이 클래스는 각 노드의 값과 왼쪽, 오른쪽 자식 노드를 저장합니다. 다음으로, lowest_common_ancestor 함수를 정의하여 주어진 루트 노드에서 시작하여 두 개의 노드인 node1과 node2의 최소 공통 조상을 찾습니다.

4.1 기본 조건

루트 노드가 None인 경우에는 None을 반환합니다. 현재 루트가 node1 또는 node2와 동일한 경우에는 해당 노드를 반환합니다.

4.2 재귀적 탐색

그 후, 왼쪽 서브트리와 오른쪽 서브트리 각각에서 재귀적으로 LCA를 찾습니다. 두 서브트리에서 모두 발견된 노드가 있을 경우 현재 노드가 최소 공통 조상입니다. 그렇지 않으면 발견된 노드를 반환합니다.

5. 테스트 케이스

함수를 테스트하기 위해 다음의 트리를 구성해 보겠습니다.

            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)
        

# Test case 1: Finding LCA of 5 and 1
lca = lowest_common_ancestor(root, root.left, root.right)  # should return TreeNode(3)

# Test case 2: Finding LCA of 5 and 4
lca = lowest_common_ancestor(root, root.left, root.left.right.right)  # should return TreeNode(5)

6. 결론

이번 강좌에서는 파이썬을 사용하여 이진 트리에서 최소 공통 조상을 찾는 방법을 알아보았습니다. DFS 알고리즘을 통해 문제를 해결하는 과정을 살펴보았으며, 이를 통해 이진 트리에 대한 이해를 높일 수 있었습니다. 다음 강좌에서는 보다 복잡한 이진 트리 문제를 다룰 예정이니, 많은 관심 부탁드립니다!

이 글을 통해 여러분께서 LCA 문제를 이해하고, 이를 해결할 수 있는 능력을 키우셨기를 바랍니다. 감사합니다!