C++ 코딩테스트 강좌, 최소 공통 조상

안녕하세요! 이번 강좌에서는 코딩테스트에서 자주 출제되는 개념 중 하나인 ‘최소 공통 조상’에 대해 다루어 보겠습니다. 이 강좌는 C++를 사용하여 문제를 해결하는 방법을 배우는 데 중점을 두고 있습니다. 먼저 최소 공통 조상이 무엇인지, 그리고 이를 찾기 위한 알고리즘을 자세히 설명하겠습니다.

1. 문제 설명

주어진 이진 트리에서 두 개의 노드가 있을 때, 이 노드의 최소 공통 조상을 찾는 문제를 다룰 것입니다. 이진 트리의 노드는 부모 노드와 자식 노드의 관계를 가지며, 각 노드는 고유한 값을 가집니다.

문제 정의

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

입력 형식

  • 이진 트리: 트리의 루트 노드가 주어집니다.
  • 두 노드 A와 B: 두 노드는 트리 내의 유효한 노드입니다.

출력 형식

노드 A와 B의 최소 공통 조상을 반환합니다. 만약 공통 조상이 없다면 nullptr을 반환합니다.

예제 입력

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

예제 출력

최소 공통 조상: 5 (A: 5, B: 1)

2. 알고리즘 접근 방법

최소 공통 조상을 찾기 위해 주로 사용되는 두 가지 접근 방법이 있습니다:

  1. 재귀적인 방법
  2. 탐색 트리의 부모를 저장하여 간접적으로 탐색하는 방법

2.1. 재귀적 접근 방법

가장 일반적인 방법은 트리의 루트에서 시작하여 재귀적으로 탐색하는 것입니다. 두 노드가 현재 노드의 왼쪽 또는 오른쪽 서브트리에 있을 때, 그 서브트리를 계속 탐색합니다. 만약 현재 노드가 A 또는 B를 발견하면 해당 노드를 반환하고, 두 노드를 모두 찾으면 현재 노드를 반환합니다.

2.2. 부모 저장 방법

이 방법은 각 노드의 부모 정보를 저장하는 것입니다. 두 노드의 조상을 부모 정보를 통해 간접적으로 찾아가며 공통 조상을 찾는 방법입니다. 하지만 이 방법은 추가적인 메모리를 사용해야 합니다.

3. C++ 코드 구현

아래는 최소 공통 조상을 찾기 위한 C++ 코드입니다.

#include 
using namespace std;

// 이진 트리 노드 정의
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 최소 공통 조상을 찾는 함수
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    // 기본 사례: root가 nullptr이거나 p 또는 q인 경우
    if (root == nullptr || root == p || root == q) {
        return root;
    }

    // 왼쪽과 오른쪽 서브트리에서 최소 공통 조상 검색
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);

    // 각 서브트리에서 공통 조상이 발견된 경우
    if (left != nullptr && right != nullptr) {
        return root; // 현재 노드가 최소 공통 조상
    }

    // 하나의 서브트리에서만 공통 조상이 발견된 경우
    return left != nullptr ? left : right;
}

// 메인 함수
int main() {
    // 이진 트리 생성
    TreeNode *root = new TreeNode(3);
    TreeNode *n1 = new TreeNode(5);
    TreeNode *n2 = new TreeNode(1);
    TreeNode *n3 = new TreeNode(6);
    TreeNode *n4 = new TreeNode(2);
    TreeNode *n5 = new TreeNode(0);
    TreeNode *n6 = new TreeNode(8);
    TreeNode *n7 = new TreeNode(7);
    TreeNode *n8 = new TreeNode(4);

    root->left = n1;
    root->right = n2;
    n1->left = n3;
    n1->right = n4;
    n2->left = n5;
    n2->right = n6;
    n4->left = n7;
    n4->right = n8;

    // 최소 공통 조상 호출
    TreeNode* ancestor = lowestCommonAncestor(root, n1, n2);
    cout << "최소 공통 조상: " << ancestor->val << endl;

    return 0;
}

4. 코드 설명

위의 코드는 이진 트리에서 두 노드 A와 B의 최소 공통 조상을 찾는 방법을 구현한 것입니다. 이제 각 부분에 대해 설명하도록 하겠습니다.

4.1. TreeNode 구조체

TreeNode 구조체는 이진 트리의 노드를 정의합니다. 각 노드는 정수 값과 왼쪽 및 오른쪽 자식 노드를 가리키는 포인터를 포함합니다.

4.2. lowestCommonAncestor 함수

  • 기본 사례를 처리합니다: root가 nullptr이거나 현재 노드가 A 또는 B인 경우 해당 노드를 반환합니다.
  • 왼쪽과 오른쪽 서브트리에서 각각 최소 공통 조상을 검색합니다.
  • 왼쪽과 오른쪽 서브트리 모두에서 노드를 찾은 경우, 현재 노드를 반환합니다.
  • 하나의 서브트리에서만 발견된 경우 그 서브트리의 조상을 반환합니다.

4.3. 메인 함수

이진 트리를 생성하고, 두 노드 A와 B를 지정하여 최소 공통 조상을 검색하는 함수 호출을 포함합니다. 결과는 콘솔에 출력됩니다.

5. 복잡도 분석

이 알고리즘의 시간 복잡도는 O(N)입니다. 여기서 N은 이진 트리의 노드 개수입니다. 모든 노드를 탐색할 수 있으므로 최악의 경우에는 모든 노드를 확인해야 할 수 있습니다.

공간 복잡도는 O(H)입니다. 여기서 H는 이진 트리의 높이입니다. 최악의 경우에는 스택 깊이가 트리의 깊이와 같아질 수 있습니다.

6. 맺음말

이번 강좌에서는 최소 공통 조상 문제를 다루었습니다. 이 문제는 이진 트리와 관련된 다양한 알고리즘 문제에서 출제되는 빈도가 높기 때문에, 충분히 이해하고 연습하는 것이 중요합니다. 각자의 이해도를 높이기 위해 추가적인 문제를 풀어보는 것도 좋은 방법입니다.

감사합니다! 다음 강좌에서는 또 다른 흥미로운 알고리즘 주제를 다루겠습니다. 질문이나 의견이 있으시면 댓글로 남겨주세요.