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

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

이 문제에서는 N개의 원소로 이루어진 배열 arr[]이 주어지며, 우리의 목표는 이진 인덱스 트리(Binary Indexed Tree, 펜윅 트리)를 활용해 C++로 최대 합 증가 부분 수열(Maximum Sum Increasing Subsequence)을 찾는 프로그램을 작성하는 것입니다.

문제 이해를 위한 예시

입력

arr[] = {4, 1, 9, 2, 3, 7}

출력

13

설명

가장 합이 큰 증가 부분 수열은 1, 2, 3, 7이며, 그 합은 13입니다.

해결 접근 방법

이 문제는 일반적인 동적 계획법(DP)으로도 O(N²)에 해결할 수 있지만, 배열의 크기가 클 경우 비효율적입니다. 이때 이진 인덱스 트리(BIT)를 사용하면 O(N log N)의 시간 복잡도로 문제를 해결할 수 있습니다.

핵심 아이디어는 다음과 같습니다.

  • 배열의 값들을 좌표 압축(Coordinate Compression)하여 인덱스로 매핑합니다.
  • 각 원소를 순회하면서, 현재 원소보다 작은 값들까지 고려했을 때 얻을 수 있는 최대 합을 BIT에서 조회합니다.
  • 조회한 최대 합에 현재 원소 값을 더해 BIT를 갱신(update)합니다.

C++ 구현 예제

아래는 위 접근 방식을 구현한 전체 코드입니다.

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

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

// newIndex 위치에 val(최대 합)을 반영하며 갱신하는 함수
void updateBIT(int BITree[], int newIndex, int index, int val){
    while (index <= newIndex){
        BITree[index] = max(val, BITree[index]);
        index += index & (-index);
    }
}

// 최대 합 증가 부분 수열을 계산하는 함수
int maxSumIS(int arr[], int n){
    int index = 0, maxSum;
    map<int, int> arrMap;

    // 좌표 압축: 값들을 정렬된 순위로 매핑
    for (int i = 0; i < n; i++){
        arrMap[arr[i]] = 0;
    }
    for (map<int, int>::iterator it = arrMap.begin(); it != arrMap.end(); it++){
        index++;
        arrMap[it->first] = index;
    }

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

    // 각 원소에 대해 최대 합 계산 후 BIT 갱신
    for (int i = 0; i < n; i++){
        maxSum = calcMaxSum(BITree, arrMap[arr[i]] - 1);
        updateBIT(BITree, index, arrMap[arr[i]], maxSum + arr[i]);
    }
    return calcMaxSum(BITree, index);
}

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

실행 결과

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

동작 원리 상세 설명

1. 좌표 압축: map<int, int>를 사용해 배열 내 서로 다른 값들을 오름차순으로 정렬된 순위(1부터 시작하는 인덱스)로 변환합니다. 이렇게 하면 값 자체가 아니라 순위를 기준으로 BIT를 운영할 수 있어 메모리와 연산이 효율적으로 관리됩니다.

2. 최대 합 조회(calcMaxSum): 현재 원소보다 작은 값들의 순위 범위(arrMap[arr[i]] - 1)까지 BIT를 탐색하며, 지금까지 계산된 최대 부분 수열 합을 가져옵니다. BIT의 특성상 이 탐색은 O(log N)에 완료됩니다.

3. BIT 갱신(updateBIT): 조회한 최대 합에 현재 원소의 값을 더한 결과를 해당 순위 위치부터 상위 노드까지 전파하며 갱신합니다. 이 과정 역시 O(log N)입니다.

4. 최종 결과: 모든 원소를 처리한 뒤 BIT 전체에서 최대값을 조회하면, 그것이 곧 최대 합 증가 부분 수열의 합입니다.

시간 복잡도 분석

  • 시간 복잡도: 각 원소마다 조회와 갱신에 O(log N)이 소요되므로 전체 O(N log N)입니다. 기존 DP 방식의 O(N²)보다 큰 폭으로 개선됩니다.
  • 공간 복잡도: 좌표 압축용 맵과 BIT 배열에 O(N)의 공간이 필요합니다.

이처럼 이진 인덱스 트리를 활용하면 대규모 입력에서도 최대 합 증가 부분 수열 문제를 효율적으로 해결할 수 있습니다.