정렬된 배열이 있고, 이 배열이 우리가 알지 못하는 어떤 피벗(pivot)을 기준으로 회전되었다고 가정해 봅시다. 이때 회전된 배열 안에서 최솟값을 찾아야 합니다. 예를 들어 배열이 [3,4,5,1,2]와 같다면 출력 결과는 1이 됩니다.
문제 해결 접근 방법
회전된 정렬 배열은 두 개의 정렬된 구간으로 나뉘어 있다는 특징이 있습니다. 따라서 처음부터 끝까지 모든 요소를 확인하는 선형 탐색(O(n)) 대신 이진 탐색(Binary Search)을 적용하면 O(log n)의 시간 복잡도로 훨씬 효율적으로 최솟값을 구할 수 있습니다.
핵심 아이디어는 다음과 같습니다. mid 위치의 값과 양쪽 끝 값을 비교하여 어느 쪽 절반이 정렬되어 있는지 판단하고, 정렬된 구간의 경계에 있는 최솟값 후보를 기록한 뒤 탐색 범위를 절반씩 좁혀 나가는 것입니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- low := 0, high := 배열의 마지막 인덱스, n := 배열의 크기, ans := 무한대(INT_MAX)로 초기화합니다.
- low <= high인 동안 다음 과정을 반복합니다.
- mid := low + (high - low) / 2 로 중간 인덱스를 계산합니다.
- arr[low] < arr[mid]이면 왼쪽 절반이 정렬된 상태이므로, ans := min(ans, arr[low])로 갱신하고 low := mid + 1로 이동합니다.
- 그렇지 않고 arr[high] > arr[mid]이면 오른쪽 절반이 정렬된 상태이므로, ans := min(ans, arr[mid])로 갱신하고 high := mid - 1로 이동합니다.
- 그렇지 않고 low == mid이면, ans := min(ans, arr[low])로 갱신하고 low := mid + 1로 이동합니다.
- 그렇지 않고 high == mid이면, ans := min(ans, arr[high])로 갱신하고 high := mid - 1로 이동합니다.
- 반복이 종료되면 ans를 반환합니다.
다음 구현 예제를 통해 더 자세히 이해해 보겠습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findMin(vector<int>& arr) {
int low = 0;
int high = arr.size() - 1;
int n = arr.size();
int ans = INT_MAX;
while(low <= high){
int mid = low + (high - low) / 2;
if(arr[low] < arr[mid]){
ans = min(ans, arr[low]);
low = mid + 1;
} else if(arr[high] > arr[mid]) {
ans = min(ans, arr[mid]);
high = mid - 1;
} else if(low == mid) {
ans = min(ans, arr[low]);
low = mid + 1;
} else if(high == mid) {
ans = min(ans, arr[high]);
high = mid - 1;
}
}
return ans;
}
};
main(){
Solution ob;
vector<int> v = {15,35,85,96,5,6,8,12};
cout << ob.findMin(v);
}입력
[15,35,85,96,5,6,8,12]
출력
5
시간 복잡도 분석
이 알고리즘은 매 반복마다 탐색 범위가 절반으로 줄어들기 때문에 시간 복잡도는 O(log n)입니다. 또한 별도의 추가 배열 없이 몇 개의 변수만 사용하므로 공간 복잡도는 O(1)로 매우 효율적입니다. 위 예제에서 배열 [15,35,85,96,5,6,8,12]는 96을 기준으로 회전된 정렬 배열이며, 알고리즘은 최솟값인 5를 정확히 찾아냅니다.