본문 바로가기

전체 글

 (31)
NeetCode 15번 알고리즘 : Search Range Search Array와는 다르게 배열이 주어지는 것이 아닌 어떠한 수의 범위가 주어진다. 이 때, 어떠한 값을 guessing한다고 했을 때 binary search를 사용하면 된다. 그 값이 맞는지에 대해서는 def isCorrect 함수가 black box로 존재하며, 상황에 맞게 isCorrect 함수를 내가 설정하면 된다.  Code# Binary search on some range of valuesdef binarySearch(low, high): while low 0: high = mid - 1 elif isCorrect(mid)  # isCorrect 예시def isCorrect(n): if n > 10: return 1 el..
7/3 코테일지 (2D binary search, dictionary 키 값에 대한 접근) 2D Binary SearchNeetCode (https://neetcode.io/problems/search-2d-matrix)  내 코드밑의 코드를 작성하였는데 시간 초과가 떳다. 답안 코드와 동일하게 O(log(mn))의 시간 복잡도를 가지는 코드이지만 시간 초과가 뜬다.알고리즘을 간단히 설명하자면 먼저 row를 선택하는 알고리즘에서는 target보다 작은 첫 번째 요소를 가진 row 중 가장 높은 row를 선택하는 것이다. 그러한 row가 선택되면 그 row에 대한 binary search를 한번 더 실시한다. 이러한 과정에서 while문 안에서 각 각의 조건문이 실행될 때 R = mid, L = mid를 해주게 되었는데 그 이유는 기존의 방식대로 binary search를 하면 mid가 targ..
NeetCode 14번 알고리즘: Search Array (Binary Search) NeetCode 링크 : https://neetcode.io/courses/dsa-for-beginners/14 Binary Search  Code arr = [1, 3, 3, 4, 5, 6, 7, 8]def binarySearch(arr, target): L, R = 0, len(arr) - 1 while L arr[mid]: L = mid + 1 elif target  ComplexityTime Complexity: O(logn)Space Complexity: O(1)

티스토리툴바