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

C++ 이진 인덱스 트리(BIT)를 활용한 최대 합 증가 부분 수열 구하기

이 문제에서는 n개의 정수로 이루어진 배열 arr[]이 주어지며, C++에서 이진 인덱스 트리(Binary Indexed Tree, BIT)를 사용하여 최대 합 증가 부분 수열을 찾는 프로그램을 작성하는 것이 목표입니다.

문제 설명

배열의 원소들을 이용하여 합이 가장 큰 증가 부분 수열(Increasing Subsequence)을 찾아야 합니다.

  • 증가 부분 수열: 현재 원소의 값이 바로 앞 위치의 원소보다 항상 큰 부분 수열을 의미합니다.
  • 이진 인덱스 트리(BIT): 트리 형태의 자료구조로, 원소를 효율적으로 추가·갱신하고 구간별 값을 빠르게 조회할 수 있습니다.

예시로 이해하기

입력

arr[] = {5, 1, 7, 3, 8, 2}

출력

20

설명

부분 수열 후보:
{5, 7, 8} = 5 + 7 + 8 = 20
{1, 3, 8} = 1 + 3 + 8 = 12
{1, 7, 8} = 1 + 7 + 8 = 16

여러 증가 부분 수열 중 {5, 7, 8}의 합인 20이 가장 크므로 정답은 20이 됩니다.

풀이 접근 방법

이 문제는 이진 인덱스 트리를 활용해 가능한 최대 합(maxSum)을 찾는 방식으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  1. 배열의 원소들을 map에 담아 좌표 압축(coordinate compression)을 수행합니다. 이렇게 하면 값의 크기와 무관하게 BIT의 인덱스 범위를 서로 다른 원소 개수만큼으로 줄일 수 있습니다.
  2. 배열을 순서대로 순회하면서 각 원소에 대해, BIT에서 해당 값 미만의 인덱스 범위에 저장된 최대 합을 조회합니다.
  3. 조회한 최대 합에 현재 원소의 값을 더해 BIT를 갱신(update)합니다. 이는 '현재 원소로 끝나는 증가 부분 수열의 최대 합'을 의미합니다.
  4. 모든 원소를 처리한 뒤 BIT 전체 범위에서 최댓값을 조회하여 반환하면, 그것이 곧 최대 합 증가 부분 수열의 합입니다.

이 알고리즘의 시간 복잡도는 각 원소마다 O(log n) 연산을 수행하므로 전체적으로 O(n log n)이며, 일반적인 동적 계획법(O(n²))보다 효율적입니다.

구현 예제

다음은 위 풀이 과정을 보여주는 C++ 프로그램입니다.

#include <bits/stdc++.h>
using namespace std;

// index까지의 범위에서 최대 합을 조회하는 함수
int calcMaxSum(int BITree[], int index){
    int sum = 0;
    while (index > 0) {
        sum = max(sum, BITree[index]);
        index -= index & (-index);
    }
    return sum;
}

// 새로운 합으로 트리를 갱신하는 함수
void updateTreeVal(int BITree[], int newIndex, int index, int sumVal){
    while (index <= newIndex) {
        BITree[index] = max(sumVal, BITree[index]);
        index += index & (-index);
    }
}

int calcMaxSumBIT(int arr[], int n){
    int uniqCount = 0, maxSum;
    map<int, int> BinaryIndexTree;

    // 좌표 압축: 배열의 고유한 값들에 순위를 부여
    for (int i = 0; i < n; i++) {
        BinaryIndexTree[arr[i]] = 0;
    }
    for (map<int, int>::iterator it = BinaryIndexTree.begin();
    it != BinaryIndexTree.end(); it++) {
        uniqCount++;
        BinaryIndexTree[it->first] = uniqCount;
    }

    // BIT 초기화
    int* BITree = new int[uniqCount + 1];
    for (int i = 0; i <= uniqCount; i++) {
        BITree[i] = 0;
    }

    // 각 원소에 대해 최대 합을 조회하고 트리를 갱신
    for (int i = 0; i < n; i++) {
        maxSum = calcMaxSum(BITree, BinaryIndexTree[arr[i]] - 1);
        updateTreeVal(BITree, uniqCount, BinaryIndexTree[arr[i]],
        maxSum + arr[i]);
    }

    return calcMaxSum(BITree, uniqCount);
}

int main(){
    int arr[] = {5, 1, 7, 3, 8, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"이진 인덱스 트리로 구한 최대 합 증가 부분 수열의 합: "
    <<calcMaxSumBIT(arr, n);
    return 0;
}

실행 결과

이진 인덱스 트리로 구한 최대 합 증가 부분 수열의 합: 20

정리

이처럼 이진 인덱스 트리를 사용하면 각 원소를 처리할 때 이전 원소들의 최대 합을 O(log n) 시간에 빠르게 조회하고 갱신할 수 있습니다. 좌표 압축을 함께 적용하면 값의 범위가 매우 클 때도 메모리를 효율적으로 사용할 수 있어, 최대 합 증가 부분 수열 문제를 안정적으로 해결할 수 있습니다.