Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 구현하는 인접 레벨 노드를 제외한 이진 트리의 최대 합 구하기

이 문제에서는 양수로만 구성된 이진 트리(binary tree)가 주어집니다. 목표는 인접한 두 레벨의 노드를 동시에 선택할 수 없다는 조건을 지키면서 트리 전체에서 얻을 수 있는 최대 합(maximum sum)을 구하는 프로그램을 C++로 작성하는 것입니다.

문제 설명

여기서 말하는 최대 합은 트리의 노드 값들을 더하되, 합계에 포함된 노드들이 서로 인접한 레벨(부모-자식 관계)에 걸쳐 있지 않도록 선택했을 때 얻을 수 있는 가장 큰 값을 의미합니다.

예제로 이해하기

루트(레벨 1)에서 출발하는 경우와, 루트의 자식 노드들(레벨 2)에서 출발하는 경우를 각각 계산해 비교해 보겠습니다.

21

결과 설명

루트를 시작점으로 삼으면 합 = 5 + 3 + 8 + 1 = 17이 됩니다.
반면 루트의 자식 노드들을 시작점으로 삼으면 합 = 2 + 6 + 9 + 4 = 21이 됩니다.

두 경우 중 더 큰 값인 21이 이 트리의 최대 합입니다.

해결 접근 방식

maxSum을 구하기 위해 반드시 지켜야 할 조건은 "인접한 요소는 함께 선택할 수 없다"는 것입니다. 이를 위해 다음과 같은 방식으로 접근합니다.

  1. 루트 노드(레벨 1)에서 시작하는 합을 하나 계산합니다.
  2. 루트의 자식 노드(레벨 2)에서 시작하는 또 다른 합을 계산합니다.
  3. 현재 노드에서 합을 확장할 때는 인접 레벨 규칙 때문에 바로 다음 레벨이 아니라 그다음 레벨, 즉 손자 노드(grandchildren)들을 대상으로 삼습니다.

이 과정을 재귀적으로 반복하여 각 분기의 maxSum을 구하고, 마지막으로 "레벨 1에서 시작하는 합"과 "레벨 2에서 시작하는 합" 중 더 큰 값을 최종 결과로 반환합니다.

C++ 구현 예제

아래 프로그램은 위에서 설명한 해결 방식이 실제로 어떻게 동작하는지 보여줍니다.

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int data;
    Node* left, *right;
    Node(int item){
        data = item;
    }
};
int getMaxSum(Node* root);
int findSumFromNode(Node* root){
    if (root == NULL)
        return 0;
        int sum = root->data;
    if (root->left != NULL){
        sum += getMaxSum(root->left->left);
        sum += getMaxSum(root->left->right);
    }
    if (root->right != NULL){
        sum += getMaxSum(root->right->left);
        sum += getMaxSum(root->right->right);
    }
    return sum;
}
int getMaxSum(Node* root){
    if (root == NULL)
        return 0;
        return max(findSumFromNode(root), (findSumFromNode(root->left) + findSumFromNode(root->right)));
}
int main(){
    Node* root = new Node(5);
    root->left = new Node(2);
    root->right = new Node(10);
    root->left->left = new Node(4);
    root->left->right = new Node(6);
    root->right->right = new Node(9);
    cout<<"The maximum sum from a tree with adjacent levels not allowed is "<<getMaxSum(root);
    return 0;
}

출력 결과

The maximum sum from a tree with adjacent levels not allowed is 24

동작 원리와 성능 팁

findSumFromNode() 함수는 특정 노드에서 시작하는 합을 계산합니다. 현재 노드의 값을 더한 뒤, 인접 레벨 규칙에 따라 왼쪽·오른쪽 자식의 자식들, 즉 손자 노드부터 getMaxSum()을 호출해 나머지 합을 더합니다.

getMaxSum() 함수는 "현재 노드에서 시작하는 경우"와 "자식 노드들에서 시작하는 경우"를 비교해 더 큰 값을 반환함으로써, 어느 레벨에서 출발하더라도 인접 레벨 충돌이 발생하지 않도록 보장합니다.

위 코드는 재귀 호출 과정에서 같은 노드를 여러 번 반복 계산할 수 있으므로, 트리가 깊어지면 실행 시간이 빠르게 증가할 수 있습니다. 메모이제이션(memoization)을 적용해 노드별 계산 결과를 캐싱하면 트리의 노드 수에 비례하는 O(n) 시간 복잡도로 성능을 개선할 수 있습니다.