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

안녕하세요! 오늘은 스위프트 코딩테스트를 준비하는 여러분을 위해 최소 공통 조상(LCA, Lowest Common Ancestor) 문제를 다뤄보겠습니다. 이 문제는 트리 구조에서 두 노드의 가장 가까운 공통 조상을 찾는 문제로, 다양한 응용이 가능합니다. 그리고 특히 코딩 테스트에서는 자주 등장하는 문제 중 하나입니다.

문제 설명

주어진 이진 트리에서 두 개의 노드가 주어졌을 때, 이 두 노드의 최소 공통 조상을 찾는 함수를 작성하세요. 이진 트리의 노드는 아래와 같이 정의됩니다:

    class TreeNode {
        var value: Int
        var left: TreeNode?
        var right: TreeNode?
        
        init(value: Int) {
            self.value = value
            self.left = nil
            self.right = nil
        }
    }

예를 들어, 다음과 같은 이진 트리가 있을 때:

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

노드 5와 노드 1의 최소 공통 조상은 노드 3입니다. 노드 5와 노드 4의 경우, 최소 공통 조상은 노드 5입니다.

입력 형식

함수는 아래와 같은 형식으로 정의됩니다:

    func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode?

여기서 root는 이진 트리의 루트 노드, p와 q는 각각의 노드를 나타냅니다. 이 노드들은 트리에 존재합니다.

문제 풀이 과정

이 문제를 해결하기 위한 다양한 접근 방법이 있지만, 가장 효율적인 방법 중 하나는 재귀를 활용하는 것입니다. 아래에는 이 방법을 사용하여 문제를 해결하는 과정을 단계적으로 설명하겠습니다.

1단계: 기본 아이디어

트리 탐색을 통해 각 노드에 대해 다음과 같은 세 가지 경우를 고려할 수 있습니다:

  • 현재 노드가 p 또는 q와 일치하는 경우
  • 왼쪽 서브트리에서 p 또는 q를 찾는 경우
  • 오른쪽 서브트리에서 p 또는 q를 찾는 경우

이 경우를 통해 우리는 최소 공통 조상을 유도할 수 있습니다. 두 서브트리에서 각각 하나씩 노드를 찾으면 현재 노드가 최소 공통 조상이 됩니다.

2단계: 재귀 함수 구현

이제 재귀 함수를 구현하여 각 노드에서 두 노드를 찾습니다:

    func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
        // 검사할 노드가 nil인 경우
        guard let current = root else { return nil }

        // 현재 노드가 p 또는 q인 경우
        if current === p || current === q {
            return current
        }

        // 왼쪽과 오른쪽 서브트리에서 각각의 노드 탐색
        let left = lowestCommonAncestor(current.left, p, q)
        let right = lowestCommonAncestor(current.right, p, q)

        // 왼쪽과 오른쪽 서브트리에서 각각 발견한 경우
        if left != nil && right != nil {
            return current
        }

        // 하나의 서브트리에서만 발견한 경우
        return left ?? right
    }

위의 코드에서 guard let 구문을 통해 현재 노드가 nil인지 확인하고, 현재 노드가 p 또는 q와 일치하는지를 검사합니다. 이후 왼쪽과 오른쪽 서브트리에서 재귀적으로 함수를 호출하여 각각의 결과를 left와 right에 저장합니다. 두 서브트리에서 모두 결과를 찾은 경우에는 현재 노드가 최소 공통 조상임을 반환합니다.

3단계: 테스트 케이스 작성

이제 작성한 함수를 테스트하기 위해 몇 가지 테스트 케이스를 추가하겠습니다:

    let root = TreeNode(value: 3)
    let node5 = TreeNode(value: 5)
    let node1 = TreeNode(value: 1)
    let node6 = TreeNode(value: 6)
    let node2 = TreeNode(value: 2)
    let node0 = TreeNode(value: 0)
    let node8 = TreeNode(value: 8)
    let node7 = TreeNode(value: 7)
    let node4 = TreeNode(value: 4)

    // 트리 구조 연결
    root.left = node5
    root.right = node1
    node5.left = node6
    node5.right = node2
    node1.left = node0
    node1.right = node8
    node2.left = node7
    node2.right = node4

    // 테스트
    let lca1 = lowestCommonAncestor(root, node5, node1) // 결과는 3
    let lca2 = lowestCommonAncestor(root, node5, node4) // 결과는 5

테스트 케이스를 실행하여 결과를 확인합니다. 이 경우, 예상 결과가 나오는지 확인한 후 각 노드의 최소 공통 조상을 올바르게 찾는지 검증합니다.

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(N)입니다. 이는 최악의 경우 모든 노드를 탐색해야 하기 때문에 N개의 노드를 가진 트리에서는 최대 O(N)의 시간이 소요됩니다. 또한 공간 복잡도는 O(H)이며, H는 트리의 깊이를 나타냅니다. 이는 재귀 호출 스택의 깊이를 의미합니다.

결론

오늘은 이진 트리에서 최소 공통 조상을 찾는 문제를 스위프트로 해결하는 방법에 대해 알아보았습니다. 이 문제는 코딩 테스트에서 자주 등장하므로, 문제가 주어졌을 때 빠르게 해결할 수 있는 능력을 키우는 것이 중요합니다. 재귀적인 접근 방법을 활용하여 문제를 해결함으로써 코드의 효율성을 높이고, 이해도를 강조했습니다. 다음에도 흥미로운 알고리즘 문제로 찾아오겠습니다!