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

코딩 테스트 준비생들을 위한 알고리즘 문제 풀이 강좌입니다. 이번 글에서는 최소 공통 조상을 구하는 알고리즘을 다루고, 이를 해결하기 위한 다양한 전략과 자바 코드를 설명하겠습니다.

문제 정의

주어진 이진 트리에서 두 노드의 최소 공통 조상(LCA: Lowest Common Ancestor)을 찾는 문제입니다. LCA는 두 노드의 조상 중에서 가장 낮은 노드를 의미합니다. 이 문제는 트리 구조와 재귀적인 탐색 방법을 이해하는 데 중요한 예제입니다.

예를 들어, 다음과 같은 이진 트리가 주어진다면:

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

문제 접근법

이 문제를 해결하기 위해서는 다양한 접근법이 있을 수 있지만, 가장 일반적인 방법은 깊이 우선 탐색(DFS: Depth First Search)을 사용하는 것입니다. 아래의 두 가지 접근 방법을 통해 문제를 해결하는 방식을 살펴보겠습니다.

1. 재귀적 DFS 접근법

재귀를 사용하여 이진 트리를 탐색하면서 각 노드가 두 노드의 조상인지 확인하는 방법입니다. 기본적인 아이디어는 다음과 같습니다.

현재 노드가 null인 경우 null을 반환합니다.
현재 노드가 처음 찾으려는 노드 중 하나인 경우 현재 노드를 반환합니다.
좌측 및 우측 자식 노드를 재귀적으로 호출하여 결과를 받습니다.
좌측 및 우측 자식 노드에서 반환된 값이 모두 null이 아닌 경우, 현재 노드가 최소 공통 조상입니다.
그 외의 경우에는 null이 아닌 자식을 반환합니다.

2. 부모 노드 맵을 이용한 탐색

이 방법에서는 각 노드의 부모를 저장하는 맵을 먼저 만든 후, 다음과 같은 과정을 진행합니다.

첫 번째 노드부터 시작하여 부모 노드를 맵에 저장합니다.
두 번째 노드의 조상을 저장한 후, 각 조상을 부모 맵에서 확인합니다.
첫 번째 노드에서 두 번째 노드의 조상으로 올라가면서 최초로 만나는 조상이 최소 공통 조상입니다.

자바 코드 구현

이제 위에서 설명한 두 접근법을 사용하여 자바 코드로 구현해보겠습니다.

첫 번째 접근법: 재귀적 DFS

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        if (left != null && right != null) {
            return root;
        }
        return left != null ? left : right;
    }
}

두 번째 접근법: 부모 노드 맵 이용

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private Map parentMap = new HashMap<>();
    
    public void buildParentMap(TreeNode root) {
        if (root.left != null) {
            parentMap.put(root.left, root);
            buildParentMap(root.left);
        }
        if (root.right != null) {
            parentMap.put(root.right, root);
            buildParentMap(root.right);
        }
    }
    
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        buildParentMap(root);
        
        HashSet ancestors = new HashSet<>();
        
        while (p != null) {
            ancestors.add(p);
            p = parentMap.get(p);
        }
        
        while (!ancestors.contains(q)) {
            q = parentMap.get(q);
        }
        return q;
    }
}

테스트 케이스

이 구현을 검증하기 위해 몇 가지 테스트 케이스를 살펴보겠습니다:

트리: 위의 예시와 같이 구성하고, 노드 5와 1의 LCA를 찾습니다. 결과는 3이어야 합니다.
트리: 또한, 노드 5와 4의 LCA를 찾습니다. 결과는 5이어야 합니다.
트리: 노드 6과 7의 경우 LCA는 5이어야 합니다.

결론

이번 글에서는 자바를 사용하여 이진 트리의 최소 공통 조상을 찾는 방법에 대해 자세히 알아보았습니다. 재귀적 접근법과 부모 노드 맵을 이용한 접근법을 통해 LCA를 효과적으로 찾을 수 있습니다. 이러한 알고리즘을 이해하고 구현하는 것은 프로그래밍 인터뷰에서 좋은 평가를 받을 수 있는 기초가 됩니다.

문제 해결 능력을 기르는 것은 중요하며, 다양한 문제를 풀고 경험을 쌓는 것이 필요합니다. 충분한 연습을 통해 코딩 테스트에 대비하세요!