C++로 정렬된 이진 배열에서 1의 개수 세기

이 튜토리얼에서는 정렬된 이진 배열에서 1의 개수를 찾는 프로그램을 다뤄보겠습니다.

문제의 조건은 다음과 같습니다. 1과 0으로만 구성된 배열이 주어지며, 배열 안에 포함된 1의 개수를 세어 반환해야 합니다.

접근 방법

배열은 1이 먼저 나오고 그 뒤에 0이 오는 형태로 정렬되어 있기 때문에, 처음부터 끝까지 하나씩 확인하는 O(n) 방식 대신 이진 탐색(Binary Search)을 활용할 수 있습니다. 이진 탐색을 사용하면 마지막 1이 등장하는 위치를 O(log n) 시간 복잡도로 찾아낼 수 있어 훨씬 효율적입니다.

알고리즘 동작 원리

1. 배열의 중간 인덱스(mid)를 계산합니다.
2. arr[mid]가 1이면서 mid가 마지막 인덱스이거나 arr[mid+1]이 0이라면, mid+1이 곧 1의 총 개수입니다.
3. arr[mid]가 1이라면 1의 마지막 위치는 더 오른쪽에 있으므로 오른쪽 절반을 재귀적으로 탐색합니다.
4. arr[mid]가 0이라면 왼쪽 절반을 재귀적으로 탐색합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
// 1의 개수를 반환하는 함수
int countOnes(bool arr[], int low, int high){
    if (high >= low){
        int mid = low + (high - low)/2;
        // mid가 마지막 1의 위치인 경우
        if ( (mid == high || arr[mid+1] == 0) && (arr[mid] == 1))
            return mid+1;
        if (arr[mid] == 1)
            return countOnes(arr, (mid + 1), high);
        return countOnes(arr, low, (mid -1));
    }
    return 0;
}
int main(){
    bool arr[] = {1, 1, 1, 1, 0, 0, 0};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Count of 1's in given array is " << countOnes(arr, 0, n-1);
    return 0;
}

실행 결과

Count of 1's in given array is 4

정리

위 코드에서 배열 {1, 1, 1, 1, 0, 0, 0}은 1이 네 번 나오므로 결과로 4가 출력됩니다. 이처럼 정렬된 이진 배열에서는 이진 탐색을 활용하면 선형 탐색보다 훨씬 빠르게 1의 개수를 구할 수 있습니다. 특히 배열의 크기가 클수록 그 성능 차이가 두드러집니다.