C++에서 배열 부분 집합의 AND 연산 최솟값 구하기

문제 개요

정수로 이루어진 배열이 주어졌을 때, 배열의 각 부분 집합에 속한 모든 요소를 비트 AND(&) 연산한 값을 구하고, 그 결과들 중 최솟값을 찾아 출력하는 문제입니다.

예시

배열 arr[] = {1, 2, 3, 4, 5}가 주어진 경우, 두 요소씩 짝지은 부분 집합들의 AND 결과는 다음과 같습니다.

(1 & 2) = 0
(1 & 3) = 1
(1 & 4) = 0
(1 & 5) = 1
(2 & 3) = 2
(2 & 4) = 0
(2 & 5) = 0
(3 & 4) = 0
(3 & 5) = 1
(4 & 5) = 4

접근 방식 및 알고리즘

이 문제의 핵심은 비트 AND 연산의 성질에 있습니다. AND 연산은 특정 비트를 1에서 0으로 바꿀 수는 있지만, 0을 다시 1로 되돌릴 수는 없습니다. 따라서 부분 집합에 포함되는 요소가 늘어날수록 AND 결과는 절대 커지지 않고, 같거나 작아집니다.

결국 어떤 부분 집합의 AND 값도 배열 전체 요소를 모두 AND한 값보다 작을 수 없습니다. 즉, 정답은 항상 배열 전체의 AND 값이며, 모든 부분 집합을 일일이 탐색할 필요 없이 배열을 한 번만 순회하면 됩니다.

알고리즘 단계는 다음과 같습니다.

1. result 변수를 배열의 첫 번째 요소 arr[0]으로 초기화합니다.
2. 인덱스 1부터 n-1까지 반복하면서 result = result & arr[i] 연산을 수행합니다.
3. 반복 종료 후의 result 값이 곧 최솟값이므로 이를 반환합니다.

시간 복잡도: O(n)
공간 복잡도: O(1)

C++ 구현

#include <bits/stdc++.h>
using namespace std;
int getMinAndValue(int *arr, int n) {
    int result = arr[0];
    for (int i = 1; i < n; ++i) {
        result = result & arr[i];
    }
    return result;
}
int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Minimum value = " << getMinAndValue(arr, n) << endl;
    return 0;
}

위 프로그램을 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다.

출력 결과

Minimum value = 0

결과 분석

{1, 2, 3, 4, 5}의 전체 AND 값은 0입니다. 앞선 예시에서 보듯이 이미 (1 & 2) = 0처럼 일부 요소만으로 0이 나오며, 여기에 더 많은 요소를 AND해도 값은 0 그대로 유지됩니다. 따라서 배열 전체의 AND 값인 0이 모든 부분 집합 AND 값 중 최솟값이 됩니다.