알고리즘 문제에서 자주 등장하는 극소값(Local Minima) 찾기 문제를 C++로 해결하는 방법을 알아보겠습니다. 핵심은 이진 탐색(Binary Search)의 논리를 응용하여 선형 시간보다 훨씬 빠른 O(log n) 안에 답을 구하는 것입니다.
극소값(Local Minima)이란?
n개의 요소를 가진 배열 A가 있다고 가정해 보겠습니다. 배열 A에서 어떤 요소 A[x]가 자신의 양쪽 이웃 요소보다 작거나 같을 때, A[x]를 극소값이라고 정의합니다. 단, 배열의 맨 앞이나 맨 뒤처럼 경계에 위치한 요소는 이웃이 하나뿐이므로, 존재하는 한쪽 이웃과만 비교하면 됩니다.
만약 배열에 극소값이 여러 개 존재한다면, 그중 아무거나 하나만 반환하면 됩니다.
예를 들어 배열이 [9, 6, 3, 14, 5, 7, 4]라고 할 때, 극소값은 3, 5, 4 세 개입니다. 따라서 이 알고리즘은 3, 5, 4 중 하나만 출력하면 문제가 해결된 것입니다.
이진 탐색을 활용한 접근 방법
모든 요소를 순차적으로 확인하는 대신, 이진 탐색과 유사한 방식으로 탐색 범위를 절반씩 줄여 나갈 수 있습니다. 동작 원리는 다음과 같습니다.
- 탐색 범위의 중간 요소(mid)를 확인합니다.
- 중간 요소가 왼쪽·오른쪽 이웃보다 모두 작거나 같다면 → mid가 곧 극소값이므로 바로 반환합니다.
- 중간 요소가 왼쪽 이웃보다 크다면 → 왼쪽 절반 어딘가에 반드시 극소값이 존재하므로, 왼쪽 범위를 재귀적으로 탐색합니다.
- 중간 요소가 오른쪽 이웃보다 크다면 → 오른쪽 절반에 극소값이 존재하므로, 오른쪽 범위를 재귀적으로 탐색합니다.
이 과정을 반복하면 매번 탐색 범위가 절반으로 줄어들기 때문에, 전체 시간 복잡도는 O(log n)이 됩니다.
C++ 예제 코드
#include<iostream>
using namespace std;
int localMinima(int arr[], int left, int right, int n) {
int mid = left + (right - left)/2;
if ((mid == 0 || arr[mid-1] > arr[mid]) && (mid == n-1 || arr[mid+1] > arr[mid]))
return mid;
else if (mid > 0 && arr[mid-1] < arr[mid])
return localMinima(arr, left, (mid - 1), n);
return localMinima(arr, (mid + 1), right, n);
}
int findLocalMinima(int arr[], int n) {
return localMinima(arr, 0, n-1, n);
}
int main() {
int arr[] = {9, 6, 3, 14, 5, 7, 4};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Local minima is: " << arr[findLocalMinima(arr, n)];
}
실행 결과
Local minima is: 3
코드 설명 및 주요 포인트
localMinima()함수는 현재 탐색 범위 [left, right] 내에서 극소값의 인덱스를 재귀적으로 찾습니다.- 경계 조건(
mid == 0,mid == n-1)을 함께 검사하여 배열의 첫 번째 또는 마지막 요소가 극소값인 경우에도 올바르게 처리합니다. - 왼쪽 이웃이 더 작으면 왼쪽 절반으로, 그렇지 않으면 오른쪽 절반으로 탐색 범위를 좁혀 나갑니다.
- 이 알고리즘이 항상 성공하는 이유는, 탐색 방향의 경계 값이 중간 값보다 작다는 조건이 유지되기 때문입니다. 즉, 해당 방향으로 이동하면 반드시 극소값(또는 배열 끝)에 도달하게 됩니다.
마무리
정렬되지 않은 배열에서도 이진 탐색 아이디어를 활용하면 O(log n) 시간에 극소값을 찾을 수 있습니다. 이는 일반적인 이진 탐색이 '정렬된 배열'을 요구하는 것과 달리, 극소값 문제의 구조적 특성 덕분에 가능한 것입니다. 유사한 응용 문제로 극대값(Local Maxima) 찾기, 회전된 정렬 배열에서의 탐색 등이 있으니 함께 학습해 보시길 추천합니다.