주어진 이진 트리에서 최대 독립 집합(LIS)의 크기를 구하는 C++ 프로그램

개요

이 글에서는 주어진 이진 트리에서 가장 큰 독립 집합(Largest Independent Set, LIS)의 크기를 구하는 C++ 프로그램을 다룹니다. 여기서 독립 집합이란 트리에서 간선으로 직접 연결된 노드, 즉 부모-자식 관계에 있는 노드를 동시에 선택하지 않는 노드들의 집합을 의미합니다.

알고리즘

정수 데이터 d, 왼쪽 자식 포인터 l, 오른쪽 자식 포인터 r, 그리고 메모이제이션용 lis 필드를 갖는 구조체 n을 선언합니다.
두 정수 중 더 큰 값을 반환하는 max() 함수를 작성합니다.
루트 노드를 입력받아 해당 서브트리의 LIS 크기를 반환하는 LIS() 함수를 구현합니다.
현재 노드를 제외하는 경우의 크기를 계산합니다.
size_excl = LIS(root->l) + LIS(root->r)
현재 노드를 포함하는 경우의 크기를 계산합니다. 자식 노드는 함께 선택할 수 없으므로, 손자노드 서브트리들의 LIS를 더합니다.
size_incl = 1
if (root->l) size_incl += LIS(root->l->l) + LIS(root->l->r)
if (root->r) size_incl += LIS(root->r->l) + LIS(root->r->r)
두 값 중 최댓값을 결과로 반환하고, 그 값을 노드의 lis 필드에 저장해 같은 서브트리를 반복해서 계산하지 않도록 합니다.
새 노드를 생성하는 newnode() 헬퍼 함수를 작성합니다.

예제 코드

#include <iostream>
using namespace std;
struct n {
    int d;
    int lis;
    struct n *l, *r;
};
int max(int x, int y) {
    return (x > y) ? x : y;
}
int LIS(struct n *root) {
    if (root == NULL)
        return 0;
    if (root->lis)
        return root->lis;
    if (root->l == NULL && root->r == NULL)
        return (root->lis = 1);
    int lis_excl = LIS(root->l) + LIS(root->r);
    int lis_incl = 1;
    if (root->l)
        lis_incl += LIS(root->l->l) + LIS(root->l->r);
    if (root->r)
        lis_incl += LIS(root->r->l) + LIS(root->r->r);
    root->lis = max(lis_incl, lis_excl);
    return root->lis;
}
struct n* newnode(int d) {
    struct n* t = (struct n *) malloc(sizeof(struct n));
    t->d = d;
    t->l = t->r = NULL;
    t->lis = 0;
    return t;
}
int main() {
    struct n *root = newnode(30);
    root->l = newnode(20);
    root->l->l = newnode(10);
    root->l->r = newnode(7);
    root->l->r->l = newnode(9);
    root->l->r->r = newnode(6);
    root->r = newnode(50);
    root->r->r = newnode(26);
    cout << "Size of the Largest Independent Set is " << LIS(root);
    return 0;
}

실행 결과

Size of the Largest Independent Set is 5

출력값 5는 예제 트리에서 루트 노드 30과 네 개의 손자 노드 {10, 9, 6, 26}을 선택한 집합이 서로 인접하지 않으면서 크기가 가장 크기 때문입니다.

핵심 포인트: 메모이제이션

단순 재귀로 이 문제를 풀면 같은 서브트리를 여러 번 중복 계산하여 지수 시간이 걸릴 수 있습니다. 이 코드는 각 노드 구조체에 lis 필드를 두어 한 번 계산한 결과를 캐싱하므로, 모든 노드를 상수 번씩만 방문하게 됩니다.

시간 복잡도: O(n) — 각 노드의 결과를 한 번씩만 계산
공간 복잡도: O(n) — 노드별 캐시 저장 공간과 재귀 호출 스택