C 프로그래밍: 배열에서 최대 AND 값을 가지는 쌍 찾기

이 문제에서는 n개의 양의 정수로 이루어진 배열이 주어지며, 배열 안에서 AND 연산(&)의 결과값이 가장 큰 두 요소의 쌍을 찾아야 합니다.

예시

입력: arr[] = { 4, 8, 12, 16 }
출력: pair = 8 12
최대 AND 값 = 8

입력: arr[] = { 4, 8, 16, 2 }
출력: pair = No possible AND
최대 AND 값 = 0

배열에서 최대 AND 값을 구하는 방법은 '배열 내 최대 AND 값 찾기' 알고리즘과 유사합니다. 프로그램은 해당 AND 값을 만들어내는 실제 요소들의 쌍까지 출력해야 합니다.

요소를 찾는 방법은 간단합니다. 먼저 비트 단위 탐색으로 최대 AND 값(result)을 구한 뒤, 배열 전체를 순회하면서 각 요소와 result를 AND 연산해 봅니다. 만약 arr[i] & result == result가 성립한다면, arr[i]가 최대 AND 값을 생성하는 요소 중 하나라는 의미입니다. 또한 최대 AND 값(result)이 0이라면 조건을 만족하는 쌍이 존재하지 않으므로 "Not possible"을 출력해야 합니다.

알고리즘

int checkBit(int pattern, int arr[], int n)
START
STEP 1: count 변수를 선언하고 0으로 초기화
STEP 2: FOR i = 0 ~ i < n 반복
    IF (pattern & arr[i]) == pattern THEN,
        count를 1 증가
STEP 3: count 반환
STOP

int maxAND(int arr[], int n)
START
STEP 1: res = 0으로 초기화, count 선언
STEP 2: FOR bit = 31 ~ bit >= 0 역순 반복
    count = checkBit(res | (1 << bit), arr, n) 호출
    IF count >= 2 THEN,
        res |= (1 << bit)
STEP 3: IF res == 0
        "no possible AND" 출력
    ELSE
        "Pair with maximum AND= " 출력
        count = 0
        FOR i = 0 ~ i < n && count < 2 반복
            IF (arr[i] & res) == res THEN,
                count 1 증가 후 arr[i] 출력
RETURN res
STOP

동작 원리

이 알고리즘은 상위 비트부터 하위 비트까지 하나씩 확인하면서, 해당 비트가 1로 설정된 값과 AND 연산했을 때 두 개 이상의 배열 요소가 패턴을 만족하는지 검사합니다. 조건을 만족하면 그 비트를 결과값에 포함시키는 방식으로, 그리디(greedy) 기법을 활용해 최대 AND 값을 효율적으로 구할 수 있습니다. 시간 복잡도는 O(n × 32)로 정수의 비트 수에 비례합니다.

예제 코드

#include <stdio.h>
int checkBit(int pattern, int arr[], int n){
    int count = 0;
    for (int i = 0; i < n; i++)
        if ((pattern & arr[i]) == pattern)
            count++;
    return count;
}
// 최대 AND 값 쌍을 찾는 함수
int maxAND(int arr[], int n){
    int res = 0, count;
    for (int bit = 31; bit >= 0; bit--) {
        count = checkBit(res | (1 << bit), arr, n);
        if (count >= 2)
            res |= (1 << bit);
    }
    if (res == 0) // 사용 가능한 쌍이 없는 경우
        printf("no possible and\n");
    else { // 쌍을 출력하는 경우
        printf("Pair with maximum AND= ");
        count = 0;
        for (int i = 0; i < n && count < 2; i++) {
            // 요소를 출력한 후 count 값을 증가시킴
            if ((arr[i] & res) == res) {
                count++;
                printf("%d ", arr[i]);
            }
        }
    }
    return res;
}
int main(int argc, char const *argv[]){
    int arr[] = {5, 6, 2, 8, 9, 12};
    int n = sizeof(arr)/sizeof(arr[0]);
    int ma = maxAND(arr, n);
    printf("\nThe maximum AND value= %d ", ma);
    return 0;
}

실행 결과

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

pair = 8 9
The maximum and value= 8

배열 {5, 6, 2, 8, 9, 12}에서 8과 9를 AND 연산하면 1000₂ & 1001₂ = 1000₂(10진수 8)가 되며, 이것이 배열에서 만들 수 있는 최대 AND 값입니다.