고정점 찾기
📌문제고정점이란 수열의 원소 중 그 값이 인덱스와 동일한 원소를 의미한다. 하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며, 모든 원소가 오름차순으로 정렬되어 있다. 이때 이 수열에서 고정점이 있다면 고정점을 출력하는 프로그램을 작성하시오. 고정점은 최대 1개만 존재한다.단 시간복잡도 O(logN)으로 알고리즘을 설계하시오. 📌풀이O(logN)으로 고정점을 찾으려면 선형 탐색으로는 시간 제한에 맞게 문제를 해결할 수 없음이진 탐색을 수행해서 빠르게 고정점을 찾아야 함찾고자하는 값이 중간점과 동일하다고 가정하고 탐색 수행중간점이 가리키는 위치의 값보다 중간점이 작은 경우, 왼쪽 부분을 탐색중간점이 가리키는 위치의 값보다 중간점이 큰 경우, 오른쪽 부분을 탐색 📌코드def binary_searc..
코딩테스트
2024. 12. 12. 10:15