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

C++에서 XOR 연산으로 배열 합계 최소화하기: 최적의 X 값 찾기

문제 설명

크기가 N인 배열이 주어졌을 때, 배열의 각 요소와 어떤 수 X를 XOR 연산한 결과의 합이 최소가 되도록 하는 X를 찾는 것이 이 글의 목표입니다.

예시로 이해하기

입력 배열이 다음과 같다고 가정해 봅시다.
arr[] = {8, 5, 7, 6, 9}

이때 최소 합계는 30입니다.

배열 요소들의 이진수 표현은 다음과 같습니다.
8 : 1000
5 : 0101
7 : 0111
6 : 0110
9 : 1001

X = 5일 때, XOR 연산 후의 결과는 다음과 같습니다.
8 ^ 5 = 13
5 ^ 5 = 0
7 ^ 5 = 2
6 ^ 5 = 3
9 ^ 5 = 12
합계 = 30 (13 + 0 + 2 + 3 + 12)

알고리즘

핵심 아이디어는 각 비트 자리에서 절반을 초과하는 요소들이 해당 비트를 1로 설정하고 있다면, 그 비트를 1로 만드는 X를 선택하는 것입니다. 이렇게 하면 해당 비트 위치에서 더 많은 요소가 0이 되어 전체 합계가 줄어듭니다.

  1. 32비트 정수를 사용하므로 크기가 32인 비트맵(bitMap) 배열을 생성합니다.
  2. 배열을 순회하면서 각 요소에 대해 다음을 수행합니다.
    a. 요소의 0번째 비트가 설정되어 있으면 bitMap[0]의 개수를 증가시킵니다.
    b. 1번째 비트가 설정되어 있으면 bitMap[1]의 개수를 증가시키는 식으로 진행합니다.
  3. 비트맵 배열을 순회하며 X를 찾습니다.
    만약 bitMap[i] > n/2라면, X = X + pow(2, i)를 수행합니다.
  4. 입력 배열을 다시 순회하며 각 요소와 X를 XOR 연산합니다.
  5. 연산된 배열 요소들의 합계를 계산하여 반환합니다.

C++ 구현 예제

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
const int MAX_SIZE = 32;
int getSum(int *arr, int n){
    int bitMap[MAX_SIZE];
    int bitLength = 0;
    int sum = 0;
    int res = 0;
    fill(bitMap, bitMap + n, 0);
    for (int i = 0; i < n; ++i) {
        int num = arr[i];
        int f = 0;
        while (num > 0) {
            int rem = num % 2;
            num = num / 2;
            if (rem == 1) {
                bitMap[f]++;
            }
            ++f;
            bitLength = max(bitLength, f);
        }
    }
    int candidate = 0;
    for (int i = 0; i < bitLength; ++i) {
        int num = pow(2, i);
        if (bitMap[i] > n / 2) {
            candidate += num;
        }
    }
    for (int i = 0; i < n; ++i) {
        sum += arr[i] ^ candidate;
    }
    return sum;
}
int main(){
    int arr[] = {8, 5, 7, 6, 9};
    cout << "Minimum sum: " << getSum(arr, SIZE(arr)) << "\n";
    return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 출력이 생성됩니다.

Minimum sum: 30

동작 원리 정리

이 알고리즘의 시간 복잡도는 O(N × B)입니다. 여기서 N은 배열의 크기, B는 요소들의 최대 비트 길이입니다. 각 비트 위치별로 1의 개수를 세는 과정이 배열 전체를 한 번 순회하며 이루어지고, 이후 최적의 X를 구성한 뒤 최종 합계를 계산하는 방식으로 동작합니다. 절반 초과 기준(> n/2)을 사용하는 이유는, 특정 비트가 1인 요소가 과반수를 넘을 경우 그 비트를 0으로 바꾸는 것이 전체 합계 감소에 더 유리하기 때문입니다.