코딩 일기장

🐶 문제 주어진 수열 중에서 그 값이 인덱스와 동일한 원소 찾기 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..

🐶 이진 탐색 Binary Search 이미 정렬된 데이터에서 특정 원소를 찾을 때 시작점, 끝점, 중간점을 지정하여 수행함 찾으려는 값과 중간값을 비교하여 중간점 이후 혹은 이전으로 데이터 탐색의 범위를 절반으로 줄일 수 있음 따라서 확인할 때마다 데이터의 개수가 절반으로 줄어들기 때문에 시간 복잡도 = O(logN) 탐색 범위가 1000만을 넘어갈 때 사용하면 좋다는 점! recursion으로 구현한 이진 탐색 const n = 10, target=7; const array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]; function binarySearch(start, end, target) { let mid = Math.floor((start + end) / 2); if(s..