문제 개요
정수로 이루어진 정렬된 배열이 주어졌을 때, 배열의 요소 중 주어진 값 K보다 작거나 같은 요소가 몇 개인지 세는 것이 이 글의 목표입니다. 단순히 처음부터 끝까지 확인하는 방법과, 배열이 정렬되어 있다는 특성을 활용한 이진 탐색 방법 두 가지를 살펴보겠습니다.
입력 예시 1
Arr[]= { 1, 2, 3, 14, 50, 69, 90 } K=12출력
K 이하인 숫자의 개수: 3
설명
숫자 1, 2, 3이 12보다 작거나 같습니다.
입력 예시 2
Arr[]= { 12, 13, 13, 13, 14, 50, 54, 100 } K=14출력
K 이하인 숫자의 개수: 5
설명
숫자 12, 13, 13, 13, 14 다섯 개가 14보다 작거나 같습니다.
방법 1: 단순 접근 방식 (선형 탐색)
알고리즘 설계
정수 배열 Arr[]과 값 K를 입력받습니다.
함수 smallorEqual(int arr[], int k, int len)은 arr[]에서 K 이하인 요소의 개수를 반환합니다.
개수를 저장할 변수 count를 0으로 초기화합니다.
for 반복문으로 i=0부터 i<len까지 배열을 순회합니다.
각 요소 arr[i]가 k 이하이면 count를 증가시킵니다.
배열이 오름차순으로 정렬되어 있으므로, arr[i]가 k보다 커지는 순간 반복문을 종료(break)해도 됩니다.
반복문이 끝나면 count에는 조건을 만족하는 숫자의 총 개수가 저장됩니다.
count를 결과로 반환합니다.
구현 코드
#include <bits/stdc++.h>
using namespace std;
int smallorEqual(int arr[],int k,int len){
int count = 0;
for (int i = 0; i < len; i++){
if(arr[i]<=k)
{ count++; }
else
{ break; }
}
return count;
}
int main(){
int Arr[] = { 1,5,11,12,19,21,32,53,70,100 };
int K = 21;
int Length= sizeof(Arr)/sizeof(Arr[0]);
cout <<"Numbers smaller or equal to K: "<<smallorEqual(Arr,K,Length);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Numbers smaller or equal to K: 6
이 방식의 시간 복잡도는 최악의 경우 O(n)입니다. 배열의 모든 요소를 확인해야 할 수 있기 때문입니다.
방법 2: 효율적인 접근 방식 (이진 탐색 활용)
알고리즘 설계
정수 배열 Arr[]과 값 K를 입력받습니다.
함수 binarySearch(int arr[], int k, int len)은 arr[]에서 K 이하인 요소의 개수를 반환합니다.
인덱스 low=0, high=len-1로 초기화하고 mid=(low+high)/2로 계산합니다.
변수 index를 -1로 초기화합니다.
while 반복문을 low<=high 조건이 만족되는 동안 수행합니다.
arr[mid]의 값을 확인합니다. arr[mid] <= k라면 index=mid로 갱신하고 low=mid+1로 설정해 오른쪽 절반을 계속 탐색합니다.
그렇지 않다면 high=mid-1로 설정해 왼쪽 절반을 탐색합니다.
while 반복문이 종료되면 index는 k 이하인 마지막 숫자의 인덱스가 됩니다.
배열 인덱스가 0부터 시작하므로 index+1을 결과로 반환합니다. 인덱스 0부터 index까지의 모든 숫자가 k 이하이기 때문입니다.
구현 코드
#include <bits/stdc++.h>
using namespace std;
int binarySearch(int arr[],int k,int len){
int low = 0;
int high = len -1;
int mid = (high+low)/2;
int index = -1;
while(low <= high){
mid =( low + high ) / 2;
if(arr[mid] <= k){
index = mid;
low = mid+1;
}
else{
high=mid-1;
}
}
return (index+1);
}
int main(){
int Arr[] = { 1,5,11,12,19,21,32,53,70,100 };
int K = 21;
int Length= sizeof(Arr)/sizeof(Arr[0]);
cout <<"Numbers smaller or equal to K: "<<binarySearch(Arr,K,Length);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Numbers smaller or equal to K: 6
마무리 및 성능 비교
두 방식 모두 동일한 결과를 반환하지만 성능에는 큰 차이가 있습니다. 선형 탐색은 O(n), 이진 탐색은 O(log n)의 시간 복잡도를 가지므로, 배열의 크기가 클수록 이진 탐색 방식이 압도적으로 유리합니다.
참고로 실무에서는 직접 이진 탐색을 구현하는 대신 C++ 표준 라이브러리의 std::upper_bound를 사용하면 더 간결하게 처리할 수 있습니다. upper_bound(arr, arr+len, k) - arr를 호출하면 k보다 큰 첫 번째 요소의 위치가 반환되는데, 이 값이 곧 k 이하인 요소의 개수와 같습니다.