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

이 강좌에서는 최소 공통 조상(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
        }
    }

입력

트리의 루트 노드(root)
첫 번째 노드(first)
두 번째 노드(second)

출력

주어진 두 노드의 최소 공통 조상을 반환합니다.

예제

    입력:
        root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]
        first = 5
        second = 1

    출력: 3

    입력:
        root = [1, 2, 3]
        first = 2
        second = 3

    출력: 1

문제 접근법

이 문제를 해결하기 위해서는 다음과 같은 접근법을 사용할 수 있습니다:

트리의 루트를 시작으로 탐색을 진행합니다.
현재 노드가 first 또는 second 노드 중 하나인 경우, 해당 노드를 반환합니다.
왼쪽 자식과 오른쪽 자식에서 각각 재귀적으로 탐색을 진행하여, first와 second 노드를 찾습니다.
왼쪽 및 오른쪽 자식의 탐색 결과가 각각 first와 second를 찾은 경우, 현재 노드가 최소 공통 조상입니다.
왼쪽 또는 오른쪽 자식에서만 first와 second를 찾은 경우 해당 자식 노드를 반환합니다.
아무 것도 찾지 못한 경우 nil을 반환합니다.

스위프트 코드 구현

이러한 접근법을 바탕으로 스위프트 코드를 구현해보겠습니다:

    class TreeNode {
        var value: Int
        var left: TreeNode?
        var right: TreeNode?

        init(value: Int) {
            self.value = value
            self.left = nil
            self.right = nil
        }
    }

    func lowestCommonAncestor(root: TreeNode?, first: Int, second: Int) -> TreeNode? {
        // 기본 케이스: 루트가 nil일 경우
        guard let root = root else {
            return nil
        }

        // 현재 노드가 first 또는 second 노드일 경우
        if root.value == first || root.value == second {
            return root
        }

        // 왼쪽 및 오른쪽 자식에서 재귀적 호출
        let left = lowestCommonAncestor(root: root.left, first: first, second: second)
        let right = lowestCommonAncestor(root: root.right, first: first, second: second)

        // 두 자식에서 모두 찾아진 경우
        if left != nil && right != nil {
            return root
        }

        // 한 쪽에서만 찾아진 경우 반환
        return left ?? right
    }

코드 설명

위 코드는 다음과 같이 동작합니다:

루트 노드가 nil인 경우, nil을 반환합니다.
현재 노드가 찾는 노드 중 하나인 경우, 해당 노드를 반환합니다.
왼쪽 서브트리에서 최소 공통 조상을 찾기 위해 lowestCommonAncestor 함수를 재귀 호출합니다. 동일하게 오른쪽 서브트리에서도 호출합니다.
왼쪽 및 오른쪽 호출 결과가 모두 nil이 아닌 경우, 현재 노드가 최소 공통 조상임을 의미하므로, 현재 노드를 반환합니다.
그렇지 않으면, 왼쪽 또는 오른쪽 결과 중 하나를 반환합니다.

시간 복잡도

이 알고리즘의 시간 복잡도는 O(N)입니다. N은 트리의 노드 수로, 모든 노드를 한 번씩 방문해야 최대 노드 수에 비례한 시간 복잡도가 발생합니다.

공간 복잡도

이 알고리즘의 공간 복잡도 또한 O(H)입니다. H는 트리의 높이로, 재귀 호출에 사용하는 스택 공간입니다. 최악의 경우, 트리가 한쪽으로만 치우쳐 있을 때 O(N)이 될 수 있습니다.

결론

이번 글에서는 최소 공통 조상 문제를 이진트리에서 해결하는 방법과 스위프트로 이를 구현하는 방법에 대해 알아보았습니다. 이 문제는 다양한 기술 면접에서 자주 출제되는 주제이므로, 여러 사례를 연습하여 숙련도를 높이는 것이 중요합니다.

자주 물어보는 질문(FAQ)

질문 1: 이진트리가 아닌 그래프에서 LCA를 찾을 수 있나요?

네, 이진트리가 아닌 일반 그래프에서도 LCA를 찾을 수 있지만, 경우에 따라 더 복잡한 알고리즘이 필요할 수 있습니다. 예를 들어, 하향식(Dynamic programming) 같은 방법이 사용될 수 있습니다.

질문 2: LCA 문제를 해결하는 다른 방법이 있나요?

최소 공통 조상을 찾는 여러 알고리즘이 있습니다. 예를 들어, 부모 포인터를 사용하는 방법이나 비트마스크를 활용하는 방법도 있지만, 그에 대한 사전 처리와 공간 복잡도가 덜 복잡한 방법을 선택하기도 합니다.

질문 3: LCA 문제를 확장할 수 있나요?

네, LCA 문제를 확장하여 K개 이상의 노드에 대해 최소 공통 조상을 찾도록 요구하는 문제도 존재합니다. 이러한 문제는 더 복잡한 구조나 알고리즘을 요구하므로, 연습을 통해 심화된 이해가 필요합니다.

마무리하며

최소 공통 조상 문제는 트리 구조에 대한 깊은 이해를 요구하기 때문에, 알고리즘을 학습하는 데 있어 굉장히 중요합니다. 다양한 종류의 문제를 풀어보며 연습하고, 스스로 이 문제에 대한 이해를 높이는 것이 필요합니다.