자바 코딩테스트 강좌, 최소 공통 조상

문제 정의

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

문제 풀이

1. 문제 분석

주어진 이진 트리에서 두 노드의 최소 공통 조상을 찾기 위해서는 다음과 같은 두 가지 조건을 충족해야 합니다:

• 노드 A의 조상인 노드 B가 존재해야 합니다.
• 노드 C의 조상인 노드 B도 존재해야 합니다.

이러한 관계를 성립시키기 위해 이진 트리를 순회하며 각 노드에 대해 부모 노드를 추적할 수 있습니다.

2. 알고리즘 설계

우선, 이진 트리에서 특정 노드를 찾기 위해 DFS(Depth First Search) 또는 BFS(Breadth First Search)와 같은 탐색 기법을 사용할 수 있습니다.

최소 공통 조상을 찾기 위한 구체적인 알고리즘은 다음과 같습니다:

1. 루트 노드부터 시작하여 트리를 탐색합니다.
2. 양쪽 서브트리에서 주어진 두 노드를 찾습니다.
3. 만약 각각의 서브트리에서 한 개의 노드를 찾으면 현재 노드가 최소 공통 조상입니다.
4. 모두 찾지 못한 경우, null을 반환합니다.

3. 자바 코드 구현

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class LCA {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 베이스 케이스
        if (root == null || root == p || root == q) {
            return root;
        }

        // 왼쪽과 오른쪽 서브트리에서 LCA를 찾습니다.
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // 둘 다 찾은 경우, 현재 노드가 LCA입니다.
        if (left != null && right != null) {
            return root;
        }

        // 한쪽 서브트리에서 찾은 경우 그 결과를 반환합니다.
        return left != null ? left : right;
    }
}
    

4. 코드 설명

위의 코드에서 핵심 포인트는 다음과 같습니다:

• 재귀적으로 호출하여 현재 노드가 null인지 또는 찾고자 하는 노드인지 확인합니다.
• 왼쪽 및 오른쪽 서브트리에서 최소 공통 조상을 찾고, 둘 다 찾았다면 현재 노드를 반환합니다.
• 끝으로 한쪽 서브트리에서만 발견한 경우 해당 노드를 반환하며, 그 외에는 null을 반환합니다.

5. 시간 복잡도

이 알고리즘의 시간 복잡도는 O(N)으로, 컬렉션의 각 노드를 한 번씩 방문하기 때문입니다. N은 트리의 노드 수입니다.

6. 공간 복잡도

공간 복잡도는 O(H)로, H는 트리의 높이입니다. 최악의 경우, 이진 트리가 한쪽으로 치우쳐 있을 경우 최대 높이는 N이 될 수 있습니다.

실전 코드 테스트

문제를 실제로 테스트하기 위해 예제 트리를 생성하고 LCA를 구하는 코드를 작성해 보겠습니다.

public class Main {
    public static void main(String[] args) {
        // 이진 트리 생성
        TreeNode root = new TreeNode(3);
        TreeNode node5 = new TreeNode(5);
        TreeNode node1 = new TreeNode(1);
        TreeNode node6 = new TreeNode(6);
        TreeNode node2 = new TreeNode(2);
        TreeNode node0 = new TreeNode(0);
        TreeNode node8 = new TreeNode(8);
        TreeNode node7 = new TreeNode(7);
        TreeNode node4 = new TreeNode(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;

        // LCA를 찾기 위한 객체 생성
        LCA lcaFinder = new LCA();
        TreeNode lca = lcaFinder.lowestCommonAncestor(root, node5, node1);
        System.out.println("LCA of 5 and 1: " + lca.val); // 출력: 3

        lca = lcaFinder.lowestCommonAncestor(root, node5, node4);
        System.out.println("LCA of 5 and 4: " + lca.val); // 출력: 5
    }
}
    

결론

이번 글에서는 이진 트리에서 최소 공통 조상을 찾는 문제를 다루며, 문제 정의, 알고리즘 설계, Java 코드 구현, 코드 테스트까지의 전 과정에 대해 설명하였습니다. 이 문제는 다양한 상황에서 응용될 수 있으며, 알고리즘 및 데이터 구조의 기초적인 개념을 이해하는 데 큰 도움이 됩니다.

이를 통해 자바로 코딩테스트를 준비하는 데 유용한 알고리즘 패턴을 익힐 수 있으며, 문제 해결 능력을 키우는 데 기여할 것입니다.