[이것이 코딩 테스트다] 이진 탐색 - 고정점 찾기
이진 탐색
찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 방법
✅ 문제
고정점이란, 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미합니다. 하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며, 모든 워노가 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 고정점이 있다면, 고정점을 출력하는 프로그램을 작성하세요. 고정점은 최대 1개만 존재합니다. 만약 고정점이 없다면 -1을 출력합니다.
입력 예시 1
5
-15 -6 1 3 7
출력 예시 1
3
입력 예시 2
7
-15 -4 2 8 9 13 15
출력 예시 2
2
입력 예시 3
7
-15 -4 3 8 9 13 15
출력 예시 3
-1
💻 코드
N = int(input())
data = list(map(int, input().split()))
start = 0
end = len(data) -1
result =0
while start <= end:
mid = (start + end) // 2
# 고정점인지 확인
if data[mid] == mid:
result = mid
break
elif data[mid] > mid:
end = mid - 1
else:
start = mid + 1
result = -1
print(result)
설계
N = int(input())
data = list(map(int, input().split()))
start = 0
end = len(data) -1
result =0
while start <= end:
mid = (start + end) // 2
# 고정점인지 확인
if data[mid] == mid:
result = mid
break
elif data[mid] > mid:
end = mid - 1
else:
start = mid + 1
result = -1
print(result)
이진 탐색으로 중간값과 그 인덱스를 확인한다. 일치하면 중간값이 고정값이다.
중간값이 인덱스보다 크다면 그 인덱스 오른쪽 값들은 자기 인덱스보다 무조건 값이 크다. 따라서 end를 mid - 1로 바꿔 이진 탐색을 계속 진행한다.
중간값이 인덱스보다 작다면 그 인덱스 왼쪽 값들은 자기 인덱스보다 무조건 값이 작다. 따라서 start를 mid + 1로 바꿔 이진 탐색을 계속 진행한다.
📝 정리
문제를 풀기 전에 어떻게 풀어야 할 지 간단히 메모하면서 풀었더니 금세 풀었다. 앞으로 메모하면서 정리한 후 코딩을 해야겠다.
Author And Source
이 문제에 관하여([이것이 코딩 테스트다] 이진 탐색 - 고정점 찾기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@xxwb__/이것이-코딩-테스트다-이진-탐색-고정점-찾기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)