C++로 배열에서 K비트 차이가 나는 모든 쌍의 개수 구하기

이 튜토리얼에서는 배열 안에서 이진 표현상 K비트만큼 서로 다른 쌍의 개수를 구하는 프로그램을 다룹니다.

배열과 정수 K가 주어졌을 때, 우리의 목표는 두 수의 이진 표현을 비교했을 때 정확히 K개의 비트가 서로 다른 쌍의 개수를 찾는 것입니다.

핵심 아이디어

두 숫자를 XOR(^) 연산하면, 서로 다른 비트 자리에만 1이 설정됩니다. 따라서 XOR 연산 결과에서 1의 개수(즉, 해밍 거리)가 K와 같다면 해당 쌍은 조건을 만족하는 쌍입니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

// 이진 표현에서 1인 비트의 개수를 세는 함수
int count_bit(int n){
    int count = 0;
    while (n) {
        if (n & 1)
            ++count;
        n >>= 1;
    }
    return count;
}

// 조건을 만족하는 쌍의 개수를 세는 함수
long long count_pair(int arr[], int n, int k) {
    long long ans = 0;
    for (int i = 0; i < n-1; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int xoredNum = arr[i] ^ arr[j];
            if (k == count_bit(xoredNum))
                ++ans;
        }
    }
    return ans;
}

int main() {
    int k = 2;
    int arr[] = {2, 4, 1, 3, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Total pairs for k = " << k << " are " << count_pair(arr, n, k) << "\n";
    return 0;
}

출력

5

코드 설명

count_bit 함수

정수의 이진 표현에서 1로 설정된 비트의 개수를 계산합니다. n & 1 연산으로 최하위 비트가 1인지 확인하고, n >>= 1로 비트를 오른쪽으로 한 칸씩 시프트하며 모든 비트를 검사합니다.

count_pair 함수

배열의 모든 가능한 쌍 (i, j)에 대해 두 원소를 XOR 연산한 뒤, 그 결과의 1비트 개수가 k와 일치하면 정답 카운터를 증가시킵니다. 중복 없이 모든 쌍을 검사하기 위해 j는 항상 i보다 큰 인덱스부터 시작합니다.

main 함수

예제 배열 {2, 4, 1, 3, 1}과 k = 2를 사용하여 결과를 출력합니다. 실제로 이 배열에서 이진 표현상 2비트가 다른 쌍은 총 5개입니다.

시간 복잡도

이 방법은 모든 쌍을 검사하므로 시간 복잡도는 O(n²)입니다(n은 배열의 크기). 배열의 크기가 매우 클 경우 해시맵 등을 활용한 최적화를 고려할 수 있습니다.