배열 A에 여러 개의 요소가 저장되어 있다고 가정해 보겠습니다. 이 배열에서 가장 큰 요소를 찾아야 하는데, 중요한 제약 조건이 하나 있습니다. 바로 조건부 연산자(if, 삼항 연산자 등)를 사용할 수 없다는 것입니다. 예를 들어 A = [12, 63, 32, 24, 78, 56, 20]이라면 결과는 78이 되어야 합니다.
접근 방법: 비트 AND 연산 활용
이 문제는 비트(bitwise) AND 연산을 활용하면 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 먼저 배열 끝에 INT_MAX(모든 비트가 1로 채워진 값)를 추가합니다.
- 배열 내 임의의 두 요소 쌍으로 만들 수 있는 최대 AND 값을 찾습니다.
- 이렇게 얻은 최댓값은 INT_MAX와 원래 배열의 최댓값을 AND 연산한 값이 되며, 이것이 곧 우리가 원하는 결과입니다.
INT_MAX는 모든 비트가 1이므로, 어떤 수 x와 INT_MAX를 AND하면 결과는 항상 x 자신이 됩니다(x & INT_MAX == x). 따라서 추가된 INT_MAX와 배열의 최댓값이 짝을 이루어 만드는 AND 값이 전체 최대 AND 값이 되고, 그 값이 곧 배열의 최댓값입니다.
알고리즘 동작 원리
최대 AND 값은 상위 비트부터 하위 비트까지 한 비트씩 결정해 나가는 그리디(greedy) 기법으로 구합니다. 각 비트 위치마다 해당 비트를 1로 설정한 패턴에 대해 "pattern & arr[i] == pattern"을 만족하는 요소가 두 개 이상 존재하는지 확인하고, 만족한다면 그 비트를 결과에 포함시킵니다. 흥미로운 점은 조건 판단이 필요한 부분을 (count | 1) != 1이라는 비트 연산 표현식으로 대체했다는 것입니다. count가 0 또는 1일 때만 count | 1이 1이 되므로, 이 식은 "count가 2 이상인가"를 조건 연산자 없이 검사하는 역할을 합니다.
예제 코드
#include <iostream>
#include <vector>
using namespace std;
int checkBit(int pattern, vector<int> arr, int n) {
int count = 0;
for (int i = 0; i < n; i++)
if ((pattern & arr[i]) == pattern)
count++;
return count;
}
int findLargestElement(int arr[], int n) {
vector<int> elements_vector(arr, arr + n);
elements_vector.push_back(INT_MAX);
n++;
int res = 0;
for (int bit = 31; bit >= 0; bit--) {
int count = checkBit(res | (1 << bit), elements_vector, n);
if ((count | 1) != 1)
res |= (1 << bit);
}
return res;
}
int main() {
int arr[] = {12, 63, 32, 24, 78, 56, 20};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Largest element is: " << findLargestElement(arr, n);
}실행 결과
Largest element is: 78
마무리
이 방법의 시간 복잡도는 O(32 × N), 즉 사실상 O(N) 수준으로 배열을 선형 시간에 처리합니다. 조건문을 직접 사용하지 않고 비트 연산만으로 최댓값을 찾아야 하는 코딩 인터뷰나 알고리즘 문제에서 유용하게 응용할 수 있는 기법이니, 비트 연산의 성질과 함께 기억해 두면 좋습니다.