186. 고정점 찾기
-
고정점이란, 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미합니다.
- 예를 들어 수열
a = {-15, -4, 2, 8, 13}
이 있을 때a[2] = 2
이므로, 고정점은2
가 됩니다.
- 예를 들어 수열
-
하나의 수열이
N
개의 서로 다른 원소를 포함하고 있으며, 모든 원소가 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 고정점이 있다면, 고정점을 출력하는 프로그램을 작성하세요.- 만약 고정점이 없다면
-1
을 출력합니다.
- 만약 고정점이 없다면
-
단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다.
-
입력조건
-
첫째 줄에
N
이 입력됩니다. (1 ≤ N ≤ 1,000,000) -
둘째 줄에
N
개의 원소가 정수 형태로 공백으로 구분되어 입력됩니다. (-10^9≤각 원소의 값 ≤10^9)
-
-
출력 조건
- 고정점을 출력한다. 고정점이 없다면
-1
을 출력합니다.
- 고정점을 출력한다. 고정점이 없다면
1. Python
def binary_search(array, start, end):
if start > end:
return None
mid = (start + end) // 2
# 고정점을 찾은 경우 인덱스 반환
if array[mid] == mid:
return mid
# 중간점이 가리키는 값보다 중간점이 작은 경우 왼쪽 확인
elif array[mid] > mid:
return binary_search(array, start, mid - 1)
# 중간점이 가리키는 값보다 중간점이 큰 경우 오른쪽 확인
else:
return binary_search(array, mid + 1, end)
n = int(input())
array = list(map(int, input().split()))
# 이진 탐색(Binary Search) 수행
index = binary_search(array, 0, n - 1)
# 고정점이 없는 경우 -1 출력
if index == None:
print(-1)
# 고정점이 있는 경우 해당 인덱스 출력
else:
print(index)
-
'찾고자 하는 값'이 '중간점'과 동일하다고 가정하고, 탐색을 수행하면 된다.
-
중간점이 가리키는 위치의 값보다 중간점이 작은 경우에는 왼쪽 부분을 탐색하고, 중간점이 가리키는 위치의 값보다 중간점이 큰 경우에는 오른쪽 부분을 탐색하는 것을 반복하면 된다.
2. C++
#include <bits/stdc++.h>
using namespace std;
// 이진 탐색 소스코드 구현(재귀 함수)
int binarySearch(vector<int>& arr, int start, int end) {
if (start > end) return -1;
int mid = (start + end) / 2;
// 고정점을 찾은 경우 중간점 인덱스 반환
if (arr[mid] == mid) return mid;
// 중간점의 값보다 중간점이 작은 경우 왼쪽 확인
else if (arr[mid] > mid) return binarySearch(arr, start, mid - 1);
// 중간점의 값보다 중간점이 큰 경우 오른쪽 확인
else return binarySearch(arr, mid + 1, end);
}
int n;
vector<int> arr;
int main(void) {
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
arr.push_back(x);
}
// 이진 탐색(Binary Search) 수행
int index = binarySearch(arr, 0, n - 1);
// 결과 출력
cout << index << '\n';
}
Author And Source
이 문제에 관하여(186. 고정점 찾기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@corone_hi/186.-고정점-찾기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)