이 글에서는 주어진 배열에서 고정점(Fixed Point)을 찾는 방법을 알아보겠습니다. 고정점이란 배열에서 값이 자신의 인덱스와 동일한 원소를 의미합니다. 즉, arr[i] == i를 만족하는 위치를 찾는 것입니다. 프로그램은 고정점이 존재하면 해당 값을 반환하고, 존재하지 않으면 -1을 반환합니다.
배열에는 음수도 포함될 수 있으며, 데이터는 오름차순으로 정렬되어 있습니다. 특히 이 문제에서는 중복된 원소가 허용된다는 점이 핵심 조건입니다.
접근 방법: 수정된 이진 탐색
정렬된 배열이므로 이진 탐색(Binary Search)을 활용하면 O(log n) 시간 복잡도로 문제를 해결할 수 있습니다. 하지만 일반적인 이진 탐색을 그대로 사용하면 중복 원소가 있는 경우 올바른 답을 찾지 못할 수 있습니다.
예를 들어 중복 값 때문에 고정점이 왼쪽 또는 오른쪽 어느 쪽에 있을지 확신할 수 없기 때문입니다. 이를 해결하려면 다음과 같은 수정이 필요합니다.
- 왼쪽 탐색 시:
min(mid - 1, midValue)부터 시작합니다. midValue가 mid보다 작으면 그 앞쪽 인덱스까지 건너뛰어 탐색 범위를 줄일 수 있습니다. - 오른쪽 탐색 시:
max(mid + 1, midValue)부터 시작합니다. 마찬가지로 midValue가 mid보다 크면 뒤쪽 인덱스로 점프하여 불필요한 탐색을 피합니다.
C++ 구현 예제
#include<iostream>
using namespace std;
int getFixedPoint(int arr[], int left, int right) {
if (right < left)
return -1;
int mid = (left + right) / 2;
int midValue = arr[mid];
// 고정점 발견: 값과 인덱스가 일치
if (mid == arr[mid])
return mid;
// 왼쪽 부분 탐색
int leftindex = min(mid - 1, midValue);
int l = getFixedPoint(arr, left, leftindex);
if (l >= 0)
return l;
// 오른쪽 부분 탐색
int rightindex = max(mid + 1, midValue);
int r = getFixedPoint(arr, rightindex, right);
return r;
}
int main() {
int arr[] = {-10, -5, 2, 2, 2, 3, 4, 7, 10, 12, 17};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"Fixed Point: "<< getFixedPoint(arr, 0, n-1);
}실행 결과
Fixed Point: 2
동작 설명
예제 배열 {-10, -5, 2, 2, 2, 3, 4, 7, 10, 12, 17}에서 인덱스 2의 값은 2이므로 arr[2] == 2를 만족합니다. 따라서 결과로 2가 출력됩니다.
중복 원소가 없는 경우에는 단순히 arr[mid]와 mid를 비교하여 한쪽 방향만 탐색하면 되지만, 중복이 허용되는 이 문제에서는 위와 같이 min/max 연산으로 탐색 경계를 조정해야 모든 경우를 놓치지 않고 확인할 수 있습니다.