1. 문제
고정점Fixed Point이란, 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미합니다. 예를 들어 수열 a = {-15, -4, 2, 8, 13}이 있을 때 a[2]=2이므로, 고정점은 2가 됩니다.
하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며, 모든 원소가 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 고정점이 있다면, 고정점을 출력하는 프로그램을 작성하세요. 만약 고정점이 없다며녀 -1을 출력합니다.
단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다.
2. 입력
- 첫째 줄에 N이 입력됩니다. (1≤N≤1,000,000)
이상 기호를 찾았다 - 둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력됩니다. (-10^9≤각 원소의 값 ≤10^9)
지수는 못 찾았다. 숫자를 필요할 때마다 입력해줘야 할 것 같은데 귀찮다
10개월이 지난 지금도 못 찾았다.
3. 출력
- 고정점을 출력한다. 고정점이 없다면 -1을 출력합니다.
4. 풀이
서로 다른 원소오름차순 정렬두 가지 키워드를 가지고 인덱스와 값의 관계를 따져보았다.arr[i] < i: 인덱스가 해당 배열의 값보다 큰 경우,i보다 작은인덱스는 아무리 노력을 해도 고정점이 될 수 없다.
이런 게 태생적 한계인가... 내 머리로 알고리즘 머신이 안 되는 건 태생적 한계가 아닐까...- 반대의 경우도 마찬가지
5. 처음 코드와 달라진 점
- 코드가 달라진 점은 특별히 없고 의문점이 하나 있다.
- 현재 코드는
arr[i]==i일 때i를 return한다. - 근데 고정점이 하나만 있으라는 법은 없는데 현재는 하나만 리턴한다.
- 따로 온라인 저지에 올라온 것도 없어서 테스트가 불가능하다.
- 그래서 저자가 올린 깃허브를 봤는데 마찬가지였다.
- 질문을 올린 상태라서 알게 된다면 수정하겠다.
💡 21.08.06 추가) 고정점은 최대 하나라는 답변을 받았다.
약 10개월이 지난 지금 풀고 있었는데 똑같은 생각으로 고정점 개수를 구하고 있었다.
사람은 바뀌지 않는다.
6. 코드
#include <iostream>
#include <vector>
using namespace std;
vector<int> arr;
int binarySearch(int start, int end) {
while (start <= end){
int mid = (start + end) / 2;
if (arr[mid] == mid) return mid;
if (arr[mid] > mid) end = mid - 1;
else start = mid + 1;
}
return -1;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int tmp;
cin >> tmp;
arr.push_back(tmp);
}
cout << binarySearch(0, n - 1) << endl;
}