코틀린 코딩테스트 강좌, 최소 공통 조상

이번 강좌에서는 “최소 공통 조상” 문제에 대해 알아보고, 코틀린을 사용하여 문제를 해결하는 방법에 대해 단계별로 설명하겠습니다.

문제 설명

주어진 이진 트리에서 두 노드 A와 B의 최소 공통 조상(LCA, Lowest Common Ancestor)을 찾는 문제입니다. 최소 공통 조상은 두 노드를 동시에 포함하는 가장 깊은 노드를 의미합니다.

예를 들어, 아래와 같은 이진 트리가 있다고 가정해 보겠습니다:

        1
       / \
      2   3
     / \
    4   5
    

이 경우 노드 4와 5의 최소 공통 조상은 노드 2입니다. 노드 2는 4와 5의 부모 노드이기 때문입니다.

입력 형식

입력으로는 이진 트리의 루트 노드와 두 개의 노드 A와 B가 주어집니다. A와 B는 트리의 노드 중 하나입니다.

출력 형식

출력은 노드 A와 B의 최소 공통 조상 노드입니다.

문제 해결 전략

1. 재귀적인 접근: 이진 트리의 특성을 이용하여 트리를 재귀적으로 탐색합니다.
2. 기저 조건: 현재 노드가 null이거나 현재 노드가 A 또는 B일 경우 그 노드를 반환합니다.
3. 재귀 호출: 왼쪽 서브트리와 오른쪽 서브트리를 재귀적으로 탐색하게 됩니다.
4. 조상 판단: 왼쪽과 오른쪽에서 각각 반환된 노드가 모두 null이 아닐 경우 현재 노드가 최소 공통 조상입니다.

코드 구현

이제 위의 알고리즘을 코틀린으로 구현해보겠습니다.

data class TreeNode(val value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun lowestCommonAncestor(root: TreeNode?, A: TreeNode?, B: TreeNode?): TreeNode? {
    // 기저 조건
    if (root == null || root == A || root == B) {
        return root
    }

    // 왼쪽과 오른쪽 서브트리 탐색
    val left = lowestCommonAncestor(root.left, A, B)
    val right = lowestCommonAncestor(root.right, A, B)

    // 현재 노드가 LCA인 경우
    return when {
        left != null && right != null -> root // 서로 다른 서브트리에서 발견된 경우
        left != null -> left // 왼쪽 서브트리에서만 발견된 경우
        right != null -> right // 오른쪽 서브트리에서만 발견된 경우
        else -> null // 발견되지 않은 경우
    }
}
    

코드 설명

위의 코드는 다음의 주요 부분으로 나뉩니다:

• data class TreeNode: 이진 트리의 노드를 정의하는 데이터 클래스입니다.
• lowestCommonAncestor: 최소 공통 조상을 찾는 재귀 함수입니다.
• 기저 조건을 확인한 후, 왼쪽 및 오른쪽 서브트리를 탐색하고, 조건에 따라 LCA를 반환합니다.

시간 복잡도 및 공간 복잡도

이 알고리즘의 시간 복잡도는 O(N)입니다. (N은 노드의 수) 모든 노드를 탐색하기 때문입니다.

공간 복잡도는 O(H)이며, H는 트리의 높이에 해당합니다. 이는 재귀 호출 스택에 의한 공간 사용량을 의미합니다.

예제 입력 및 출력

다음과 같은 입력을 고려해볼 수 있습니다:

    입력:
    트리:
        1
       / \
      2   3
     / \
    4   5
    A = 4
    B = 5

    출력:
    2
    

결론

이 강좌에서는 최소 공통 조상 문제의 정의와 해결 방법을 코틀린을 통해 자세히 살펴보았습니다. 이 문제는 다양한 상황에서 자주 발생하는 문제로, 이진 트리의 탐색 기술을 익히신다면 많은 알고리즘 문제를 해결하는 데 도움이 될 것입니다.