이번 글에서는 C++ STL을 활용해 정렬된 배열에서 주어진 값의 floor(바닥값)과 ceil(천장값)을 찾는 방법을 알아봅니다.
floor란 배열에서 해당 값보다 작거나 같은 원소 중 가장 큰 값을, ceil은 해당 값보다 크거나 같은 원소 중 가장 작은 값을 의미합니다. 배열이 이미 정렬되어 있다면, STL의 이진 탐색 기반 함수인 lower_bound()와 upper_bound()를 사용해 선형 탐색 없이 O(log n) 시간 안에 답을 구할 수 있습니다.
핵심 개념 정리
- lower_bound(first, last, val): val 이상인 원소가 처음 등장하는 위치의 반복자(iterator)를 반환합니다. floor 계산에 활용됩니다.
- upper_bound(first, last, val): val보다 큰 원소가 처음 등장하는 위치의 반복자를 반환합니다. ceil 계산에 활용됩니다.
두 함수 모두 반복자를 반환하므로, 배열의 시작 주소를 빼주면 해당 원소의 인덱스를 얻을 수 있습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
// 정렬된 배열에서 floor(바닥값) 찾기
void printFloor(int arr[], int n1,
int findFloor[], int n2){
int low;
cout << "Floor : ";
for (int i = 0; i < n2; i++) {
low = (lower_bound(arr, arr + n1, findFloor[i]) - arr);
if (arr[low] > findFloor[i])
cout << arr[low - 1] << " ";
else
cout << arr[low] << " ";
}
cout << endl;
}
// 정렬된 배열에서 ceil(천장값) 찾기
void printCeil(int arr[], int n1,
int findCeil[], int n2){
int up;
cout << "Ceil : ";
for (int i = 0; i < n2; i++) {
up = (upper_bound(arr, arr + n1, findCeil[i]) - arr);
if (arr[up] > findCeil[i] && arr[up - 1] == findCeil[i]) {
cout << arr[up - 1] << " ";
}
else
cout << arr[up] << " ";
}
cout << endl;
}
int main(){
int arr[] = { 1, 2, 4, 7, 11, 12, 23, 30, 32 };
int n1 = sizeof(arr) / sizeof(arr[0]);
cout << "Original Array: ";
for (unsigned int i = 0; i < n1; i++)
cout << " " << arr[i];
cout << "\n";
int find[] = { 1, 3, 5, 7, 20, 24 };
int n2 = sizeof(find) / sizeof(find[0]);
cout << "Values: ";
for (unsigned int i = 0; i < n2; i++)
cout << find[i] << " ";
cout << "\n";
printFloor(arr, n1, find, n2);
printCeil(arr, n1, find, n2);
return 0;
}
실행 결과
Original Array: 1 2 4 7 11 12 23 30 32
Values: 1 3 5 7 20 24
Floor : 1 2 4 7 12 23
Ceil : 1 4 7 7 23 30
동작 원리 살펴보기
floor를 찾는 과정
printFloor() 함수는 lower_bound()로 검색 값 이상이 처음 나타나는 인덱스를 구합니다. 그 위치의 값이 검색 값보다 크다면 배열에 검색 값 이하의 원소가 더 없다는 뜻이므로 바로 앞 원소(arr[low - 1])가 floor가 됩니다. 위치의 값이 검색 값과 같다면 그 값 자체가 곧 floor입니다.
ceil을 찾는 과정
printCeil() 함수는 upper_bound()로 검색 값보다 큰 원소가 처음 나타나는 인덱스를 구합니다. 만약 그 앞 원소(arr[up - 1])가 검색 값과 일치한다면, 배열에 검색 값 자체가 존재하므로 그 값이 ceil입니다. 그렇지 않다면 upper_bound()가 가리키는 값, 즉 검색 값보다 큰 첫 번째 원소가 ceil이 됩니다.
주의할 점
검색 값이 배열의 모든 원소보다 작으면 floor가 존재하지 않고, 모든 원소보다 크면 ceil이 존재하지 않습니다. 실무 코드에서는 이런 경계 조건(boundary case)을 반드시 확인해 범위를 벗어난 접근(out-of-bounds access)이 발생하지 않도록 처리해야 합니다.