배열이 주어졌을 때, 최소 하나의 비어 있지 않은 부분 배열(하위 배열)의 비트 AND 연산 결과가 될 수 있는 모든 정수를 찾는 문제를 해결해 보겠습니다. 예시는 다음과 같습니다.
입력 : nums[ ] = { 3, 5, 1, 2, 8 }
출력 : { 2, 5, 0, 3, 8, 1 }
설명:
2는 부분 배열 {2}의 비트 AND 값입니다.
5는 부분 배열 {5}의 비트 AND 값입니다.
0은 부분 배열 {1, 2}, {2, 8}, {1, 2, 8}의 비트 AND 값입니다.
3은 부분 배열 {3}의 비트 AND 값입니다.
8은 부분 배열 {8}의 비트 AND 값입니다.
1은 부분 배열 {1}, {3, 5}, {3, 5, 1}의 비트 AND 값입니다.
입력 : nums[ ] = { 2, 6, 3, 8, 1 }
출력 : { 1, 8, 3, 6, 2, 0 }문제 해결 접근 방법
이 문제에 적용할 수 있는 간단한 접근 방법은 다음과 같습니다.
가능한 모든 비어 있지 않은 부분 배열을 찾습니다.
배열을 순회하면서 부분 배열 내 각 요소에 대한 비트 AND 연산을 계산합니다.
중복된 값을 제거하기 위해 모든 결과를 set(집합)에 저장합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int main(){
int arr[] ={ 2, 6, 3, 8, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
// 각 AND 연산의 결과를 저장하기 위한 set 선언
unordered_set<int> result;
int val;
// 모든 가능한 비어 있지 않은 부분 배열을 탐색하는 중첩 반복문
for (int i = 0; i < n; ++i){
for (int j = i, val = INT_MAX; j < n; ++j){
val = val & arr[j];
// AND 연산 결과 저장
result.insert(val);
}
}
cout << "모든 가능한 숫자: ";
// set의 모든 값 출력
for (auto i = result.begin(); i != result.end();i++)
cout << *i << " ";
return 0;
}
실행 결과
모든 가능한 숫자: 1 8 3 6 0 2
코드 설명
AND 연산의 모든 결과를 저장하기 위해 set을 선언합니다. unordered_set을 사용하면 자동으로 중복이 제거됩니다.
'val' 변수를 INT_MAX로 초기화합니다. INT_MAX는 모든 비트가 1로 설정된 값이므로, 첫 번째 요소와 AND 연산을 수행할 때 해당 요소의 값이 그대로 유지됩니다.
바깥쪽 반복문은 부분 배열의 시작 인덱스(i)를 결정하고, 안쪽 반복문은 i번째 인덱스부터 시작하는 모든 부분 배열을 탐색합니다.
각 요소를 순차적으로 AND 연산하여 누적 결과를 계산하고, 그 값을 결과 set에 저장합니다.
마지막으로 결과 set에 저장된 모든 값을 출력합니다.
시간 복잡도 분석
이 접근 방법의 시간 복잡도는 O(n²)입니다. 두 개의 중첩 반복문을 사용하여 모든 부분 배열을 탐색하기 때문입니다. 여기서 n은 배열의 길이입니다. 공간 복잡도 역시 최악의 경우 O(n²)까지 증가할 수 있습니다. 다만 흥미로운 점은, 비트 AND 연산의 특성상 값이 누적될수록 비트가 꺼지기만 하고 다시 켜지지 않으므로, 실제 서로 다른 결과값의 개수는 이론적 최대치보다 훨씬 적을 수 있다는 것입니다.
결론
이 튜토리얼에서는 가능한 모든 부분 배열에 대해 비트 AND 연산을 계산하는 간단한 접근 방식으로 문제를 해결하는 방법을 살펴보았습니다. 또한 이를 구현한 C++ 프로그램도 함께 확인했습니다. 동일한 로직을 Java, C, Python 등 다른 프로그래밍 언어로도 손쉽게 작성할 수 있습니다. 이 튜토리얼이 도움이 되었기를 바랍니다.