이 글에서는 C++ 프로그램을 통해 이진 탐색(Binary Search) 기법으로 배열 내 피크(peak) 요소 중 하나를 찾는 방법을 알아봅니다. 피크 요소란 자신의 이웃한 요소보다 큰 값을 가지는 요소를 의미하며, 이 알고리즘은 가장 먼저 발견되는 피크를 결과로 반환합니다. 시간 복잡도는 O(log(n))으로 매우 효율적입니다.
피크 요소란?
배열에서 피크 요소는 다음 조건 중 하나를 만족하는 요소입니다.
- 양쪽에 이웃이 있는 경우: 인접한 두 요소보다 모두 커야 합니다.
- 경계(첫 번째 또는 마지막) 요소인 경우: 인접한 하나의 요소보다만 크면 됩니다.
알고리즘
시작
PeakElement() 함수는 배열 'arr', 시작 인덱스(start), 끝 인덱스(end)를 인자로 받습니다.
해당 부분 배열의 중간 인덱스(mid)를 계산합니다.
mid가 경계 인덱스이면서 mid의 값이 이웃보다 크면 mid를 피크로 반환합니다.
mid의 값이 양쪽 이웃 값보다 모두 크면 mid를 피크로 반환합니다.
mid 오른쪽 값이 mid보다 크면 두 번째 하위 배열을 PeakElement()의 인자로 전달합니다.
mid 왼쪽 값이 mid보다 크면 첫 번째 하위 배열을 PeakElement()의 인자로 전달합니다.
종료
예제 코드
#include<iostream>
using namespace std;
int PeakElement(int a[], int start, int end) {
int i, mid;
mid = (end+start+1)/2;
if((a[mid] > a[mid+1] && mid == start)||(a[mid] > a[mid-1] && mid == end)) {
return a[mid];
} else if(a[mid] < a[mid-1] && a[mid] > a[mid+1]) {
return a[mid];
} else if(a[mid] <= a[mid+1]) {
return PeakElement(a, mid+1, end);
} else if(a[mid] <= a[mid-1]) {
return PeakElement(a, start,mid-1);
}
}
int main() {
int n, i, p;
cout<<"\nEnter the number of data element: ";
cin>>n;
int arr[n];
for(i = 0; i < n; i++) {
cout<<"Enter element "<<i+1<<": ";
cin>>arr[i];
}
p = PeakElement(arr, 0, n-1);
cout<<"\nThe peak element of the given array is: "<<p;
return 0;
}
실행 결과
Enter the number of data element: 5
Enter element 1: 45
Enter element 2: 26
Enter element 3: 70
Enter element 4: 60
Enter element 5: 15
The peak element of the given array is: 70
동작 원리 살펴보기
위 예제에서 입력된 배열은 [45, 26, 70, 60, 15]입니다. 이 배열에서 70은 왼쪽 이웃인 26과 오른쪽 이웃인 60보다 모두 크기 때문에 피크 요소가 됩니다.
이진 탐색 방식을 사용하기 때문에 매 재귀 호출마다 탐색 범위가 절반씩 줄어듭니다. 따라서 배열의 크기가 아무리 커져도 선형 탐색(O(n))보다 훨씬 빠른 O(log n)의 성능을 유지할 수 있습니다.
참고 사항
예제 코드의 int arr[n]처럼 변수로 배열 크기를 지정하는 것(VLA, 가변 길이 배열)은 GCC 등 일부 컴파일러에서만 지원되며, 표준 C++에는 포함되어 있지 않습니다. 이식성을 높이려면 std::vector<int> 사용을 권장합니다.