코딩 일기장

🐶 문제 주어진 수열 중에서 그 값이 인덱스와 동일한 원소 찾기 ex) 수열 a = {-15, -4, 2, 8, 13}이면 a[2] = 2 이므로 고정점은 2가 됨. 수열은 오름차순으로 정렬되어 있음 고정점이 없다면 -1을 출력함 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 시간 초과가 남 🐶 생각 이 문제 또한 O(logN)의 시간 복잡도를 넘게 되면 시간 초과가 나기 때문에, O(N)의 시간 복잡도를 가진 선형 탐색으로는 풀 수 없다. 따라서 이진 탐색을 구현해야 함! 단순히 이진 탐색 알고리즘을 알기만 하면 쉽게 풀 수 있는 문제이다. 🐶 문제 풀이 import sys N = int(sys.stdin.readline()) nums = list(map(int, sys.stdin.readl..

이 문제는 O(logN)으로 알고리즘을 설계하지 않으면 시간 초과가 나오는 문제이다. 따라서 일반적인 for문을 활용하여 리스트를 탐색하면 시간 초과가 난다! 그렇기에 O(logN)의 시간 복잡도를 가지는 이진 탐색을 활용해야 한다. 직접 이진 탐색을 구현할 수도 있지만 파이썬의 라이브러리와 친숙해지기 위해 bisect 라이브러리를 사용했다. bisect는 특정 숫자 사이에 있는 원소의 개수를 구할 때 유용하게 사용된다. 여기서 주의할 점은 array가 오름차순으로 sorting되어 있어야 한다는 점이다! 해당 문제의 경우 이미 오름차순으로 정렬된 수열이 input값으로 들어온다. bisect_right(array, N) 배열에서 N이 마지막으로 등장하는 인덱스+1을 리턴함 bisect_left(arra..