BinarySearch

LeetCode 74. Search a 2D Matrix 🗓️ Daily LeetCoding Challenge August, Day 7 Simple Search Think from-simple-to-complex! First, I just simply search over the matrix and check if target value is in each line. Fortunately, this code didn’t trigger TLE. class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: for i in range(len(matrix)): if matrix[i][-1] >= target: if target in matrix[i]: return True else: return False Binary Search However in order to improve runtime, it’s better to use binary search than just checking with in. Similar to the previous simple search code. ...

LeetCode 1870. Minimum Speed to Arrive on Time 🗓️ Daily LeetCoding Challenge July, Day 26 (23.07.26) 으아아… bruteforce로 풀었더니 TLE (Time Limit Exceeded)… 그래서 binary-search로 풀어도 여전히 TLE. 하… C++나 Java는 잘만 통과하는거 같은데 ‘[1,1,10000000]’ 같은 예시가 나오면 time complexity가 $ O(10^7) $ 이 되어버려서 파이썬은 삐빅- 실패!를 외친다ㅜㅜ binary search 이분 탐색 풀이 아래 코드처럼 깔끔하게 풀었는데도 TLE 오류가 떴다. 아무래도 함수 따로 하는 것 조차도 시간 복잡도에 기여하는듯, 한번에 코드를 작성하는 식으로 다시 재구성해보기로 했다. ...

LeetCode 852. Peak Index in a Mountain Array 🗓️ Daily LeetCoding Challenge July, Day 25 (23.07.25) LeetCode에서는 일명 Daily Challenge를 제공하는데, 하루에 하나씩 풀어나가면 다양한 알고리즘 문제들을 풀어볼 수 있어서 유익하다. 보통 다른 문제들은 Editoral 부분이 잠금되어있어 Premium User가 아니면 읽지 못하는데, Daily Challenge만큼은 공개되어 자신의 풀이와 비교해볼 수 있다. LeetCode에 입문한지 이제 겨우 3일이지만, 다른 알고리즘 사이트에 비해서 체계가 확실히 잘 잡혀있어서 유저들에게 매우 편리하게 다가온다. 이번 문제는 배열의 증가하다가 감소하는 수열의 극값의 index을 구하는 문제다. 보자마자 이분탐색(binary-search) 알고리즘을 사용해야겠다고 생각이 들었다. 문제 조건에서도 O(logn) 시간 복잡도를 사용하라고 제시되어있기에 확신을 가지고 문제를 풀었다. ...

백준 1654번 바로가기 나의 풀이 # 입력 n, m = map(int,input().split()) lines = [] for _ in range(n): lines.append(int(input())) start,end = 1,max(lines) # 처리 while start <= end: mid = (start + end) // 2 temp = 0 for l in lines: temp += (l // mid) if temp >= m: start = mid + 1 else: end = mid-1 print(end) CODE REVIEW 이분탐색을 응용해서 해결하는 문제. 처음 봤을 때에는 막막했는데, 최종 자른 선의 길이를 기준으로 이분 탐색을 실시해서 답을 찾아내었다. start=1, end=max(lines)로 설정했는데, 만일 end=min(lines)로 설정하면 [1,100,100,100,100]같은 input의 경우 1을 출력해서 문제가 발생한다.

백준 2805번 바로가기 첫 번째 풀이 # 입력 n, m = map(int,input().split()) tree = list(map(int,input().split())) h = max(tree) current = 0 # 함수 def relu(x): if x>0: return x else: return 0 # 처리 while current < m: temp = 0 for t in tree: temp += relu(t-h) current = temp h -= 1 print(h+1) 두 번째 풀이 # 입력 n, m = map(int,input().split()) tree = list(map(int,input().split())) start,end = 1,sum(tree) # 함수 def relu(x): if x>0: return x else: return 0 # 처리 while start <= end: mid = (start + end) // 2 temp = 0 for t in tree: temp += relu(t-mid) if temp >= m: start = mid + 1 else: end = mid-1 print(end) CODE REVIEW 첫 번쨰 풀이에서는 브루트포스로 h를 max(tree)에서 1씩 내려가며 확인하는 방식을 취했다. 시간초과 에러로 탈락… 이분탐색 알고리즘을 활용해보자. 두 번째 풀이에서는 이분탐색을 활용해서 해결했다. h의 범위를 start,end로 잡고 start=end될 때 까지 반복했다. 자른 나무의 길이를 어떻게 구현할까 고민하다가, 머신러닝에서 activation function 중 하나인 relu를 가지고 구현했다. 근데 메모리 아끼기 위해서는 relu()함수 대신 if t>h: temp+=t-mid로 구현하는게 나을 것 같긴 하다.