C++에서 인접 요소를 고려하지 않고 배열의 최대 세트 비트 합 구하기

이 문제에서는 정수 배열 arr[]가 주어지며, 인접한 요소를 고려하지 않고 배열에서 얻을 수 있는 최대 세트 비트(set bit) 합을 계산하는 프로그램을 C++로 작성해야 합니다.

문제 설명

주어진 배열 arr[]의 각 숫자에 대해 세트 비트(이진수 표현에서 값이 1인 비트)의 개수를 구합니다. 그다음, 서로 인접하지 않는 요소들을 선택했을 때 얻을 수 있는 세트 비트 합, 즉 a[i] + a[i+2] + ... 형태의 합 중에서 최댓값을 찾아야 합니다.

예제를 통한 문제 이해

입력

arr[] = {1, 4, 6, 7}

출력

4

설명

배열의 각 요소를 이진수로 나타내면 다음과 같습니다.

arr[] = {01, 100, 101, 111}
비트 개수 배열 = {1, 1, 2, 3}

요소를 교대로 선택했을 때의 비트 개수 합은 다음과 같습니다.

arr[0] + arr[2] = 1 + 2 = 3
arr[1] + arr[3] = 1 + 3 = 4

두 경우를 비교하면 최대 합은 4입니다.

해결 접근 방법

이 문제는 다음 단계로 해결할 수 있습니다.

1. 배열의 각 숫자에 대해 세트 비트의 개수를 계산합니다.
2. 짝수 인덱스(0, 2, 4, ...)에 위치한 요소들의 세트 비트 합을 구합니다.
3. 홀수 인덱스(1, 3, 5, ...)에 위치한 요소들의 세트 비트 합을 구합니다.
4. 두 합 중 더 큰 값을 반환합니다.

선택 가능한 조합은 인덱스 0부터 시작하는 경우와 인덱스 1부터 시작하는 경우 단 두 가지뿐이므로, 이 두 경우만 비교하면 최댓값을 손쉽게 구할 수 있습니다.

세트 비트 계산 방법

countSetBit 함수는 n & (n-1) 연산을 활용합니다. 이 연산은 수 n에서 가장 오른쪽에 있는 세트 비트를 제거하는 효과가 있으므로, n이 0이 될 때까지 반복하면 세트 비트의 총개수를 효율적으로 셀 수 있습니다. 이 기법은 브라이언 커니핸(Brian Kernighan) 알고리즘으로도 알려져 있습니다.

솔루션 구현 예제

#include<iostream>
using namespace std;
int countSetBit(int n){
    int setBits = 0;
    while(n) {
        setBits++;
        n = n & (n - 1);
    }
    return setBits;
}
int findMaxBitAltSubArray(int arr[], int n){
    int EvenSum = countSetBit(arr[0]);
    int OddSum = 0;
    for (int i = 1; i < n; i++){
        if(i % 2 == 0){
            EvenSum += countSetBit(arr[i]);
        } else {
            OddSum += countSetBit(arr[i]);
        }
    }
    if(EvenSum >= OddSum){
        return EvenSum;
    }
    return OddSum;
}
int main() {
    int arr[] = {1, 4, 6, 7};
    int n = 4;
    cout<<"The maximum set bit sum in the array without considering adjacent elements is "<<findMaxBitAltSubArray(arr, n);
    return 0;
}

출력 결과

The maximum set bit sum in the array without considering adjacent elements is 4

복잡도 분석

시간 복잡도: O(n × log M) — n은 배열의 크기, M은 배열 내 최댓값입니다. 각 숫자의 세트 비트 개수를 세는 데 최대 log M번의 연산이 필요합니다.

공간 복잡도: O(1) — 추가적인 메모리를 사용하지 않는 상수 공간 알고리즘입니다.