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

문제 설명

최소 공통 조상(LCA, Lowest Common Ancestor)은 두 노드의 가장 최근 조상 노드를 찾는 문제입니다. 이 문제는 트리 자료구조에서 매우 중요하며, 코딩 테스트 및 면접에서도 자주 출제되는 주제입니다. 이 강좌에서는 자바스크립트를 이용해 LCA를 찾는 방법을 다루고, 실제 알고리즘 문제를 해결하는 과정을 살펴보겠습니다.

문제 정의

주어진 이진 트리와 두 노드 A와 B가 있을 때, 두 노드의 최소 공통 조상을 찾아 반환하는 함수를 작성하세요.

입력 형식

• 노드의 수는 N이며, 1 ≤ N ≤ 10^4입니다.
• 각 노드는 유일한 정수 ID를 가집니다.
• 두 노드의 ID A, B가 주어집니다.

출력 형식

• 두 노드의 최소 공통 조상을 나타내는 노드의 ID를 반환합니다.

예제

예제 1

        입력: 
        트리 구조:
              1
            /   \
          2      3
         / \    / \
        4   5  6   7

        A = 4, B = 5
        출력: 2  // 최소 공통 조상: 2
    

예제 2

        입력: 
        트리 구조:
              1
            /   \
          2      3
         / \    / \
        4   5  6   7

        A = 6, B = 7
        출력: 3  // 최소 공통 조상: 3
    

문제 풀이 과정

1. 트리 노드 구조 정의

먼저 이진 트리를 표현하기 위한 노드 구조를 정의해야 합니다. 각 노드는 적어도 부모 노드와 자식 노드에 대한 정보를 가져야 합니다. 자바스크립트에서는 다음과 같은 방식으로 노드 구조를 정의할 수 있습니다.

    class TreeNode {
        constructor(id) {
            this.id = id;  // 노드의 ID
            this.left = null;  // 왼쪽 자식 노드
            this.right = null;  // 오른쪽 자식 노드
        }
    }
    

2. 트리 생성

문제의 예제 트리를 생성해보겠습니다. 아래 코드에서 트리를 구축하는 방법을 보여줍니다.

    const root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.right = new TreeNode(3);
    root.left.left = new TreeNode(4);
    root.left.right = new TreeNode(5);
    root.right.left = new TreeNode(6);
    root.right.right = new TreeNode(7);
    

3. 최소 공통 조상 찾기

이제 실제로 LCA를 찾는 함수를 구현합니다. 이진 트리에서 최소 공통 조상을 찾는 일반적인 방법은 재귀적으로 트리를 탐색하면서, 두 노드 A와 B가 발견되는 경우 해당 노드를 반환하는 방식입니다.

    function findLCA(root, A, B) {
        if (root === null) {
            return null;
        }

        // 현재 노드가 A 또는 B인 경우
        if (root.id === A || root.id === B) {
            return root;
        }

        const leftLCA = findLCA(root.left, A, B);
        const rightLCA = findLCA(root.right, A, B);

        // 양쪽 자식에서 LCA가 발견된 경우, 현재 노드가 LCA
        if (leftLCA && rightLCA) {
            return root;
        }
        
        return leftLCA !== null ? leftLCA : rightLCA;
    }
    

4. 함수 테스트

이제 작성한 LCA 함수를 테스트해봅시다. 다음 코드로 함수를 호출하여 결과를 출력할 수 있습니다.

    const A = 4;
    const B = 5;
    const lcaNode = findLCA(root, A, B);

    console.log(`최소 공통 조상: ${lcaNode.id}`);  // 출력: 최소 공통 조상: 2
    

복잡도 분석

이 알고리즘의 시간 복잡도는 O(N)입니다. 여기서 N은 노드의 수입니다. 모든 노드를 한 번씩 방문해야 하기 때문입니다. 공간 복잡도는 O(H)로, H는 트리의 높이입니다. 최악의 경우에는 H가 N에 가까울 수 있습니다 (트리가 편향된 경우).

결론

이번 강좌에서는 자바스크립트를 이용하여 최소 공통 조상을 찾는 방법에 대해 자세히 알아보았습니다. 이 개념은 다양한 트리 관련 문제를 해결하는 데 중요한 기초가 되며, 트리 탐색 알고리즘을 이해하는 데 도움을 줄 것입니다. 실제 코딩테스트나 면접에서 자주 출제되므로 반드시 숙지해두시기 바랍니다. 다음 강좌에서는 다른 트리 관련 문제를 다룰 예정이니 기대해 주세요!