코딩 일기장

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

🐶 이진 탐색 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..