Today I learned
2022/02/04
회고록
항해 99, 알고리즘 3주차
교재 : 파이썬 알고리즘 인터뷰 / 이것이 코딩테스트다(동빈좌)
이분탐색(Binary Search)
참이슬 병뚜껑 아래에 1-50까지 적힌 숫자 맞힐때 쓰던 방법
5번 내로 맞추면 출제자가 마시는 벌칙을 수행시 이분탐색을 하면 출제자가 상당히 불리해진다.
25 -> 12 -> 6 -> 3 -> 50%확률로 출제자 벌칙
아래 이미지를 보고 이분탐색의 컨셉을 이해하자.
문제 설명
Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:
Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
Example 1:
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true
https://leetcode.com/problems/merge-intervals/
이분탐색X2 풀이
def solution(matrix, target):
checker = False
def bin_search():
left = 0
right = len(matrix)-1
while left <=right:
mid = (left + right) // 2
if target > matrix[mid][0]:
left = mid+1
elif target < matrix[mid][0]:
right = mid-1
else:
return mid + 1
mid = max(left,right)
return mid
lineRIdx = bin_search()
def bin_search2(lineLimit):
temp_matrix = matrix[:lineLimit]
i=0
for i in range(lineLimit):
left = 0
right = len(temp_matrix[i])-1
while left <= right:
mid = (left + right) // 2
if target > matrix[i][mid]:
left = mid + 1
elif target < matrix[i][mid]:
right = mid - 1
else:
return True
i += 1
return False
checker = bin_search2(lineRIdx)
return checker
if __name__ == '__main__':
target = 20
matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]
result = solution(matrix, target)
print(f'{result}')
파알인터뷰 책에 나온 색다른 풀이
def solution(matrix, target):
if not matrix:
return False
row = 0
col = len(matrix[0]) -1
while row <= len(matrix) -1 and col >=0:
if target == matrix[row][col]:
return True
elif target < matrix[row][col]:
col-=1
elif target > matrix[row][col]:
row+=1
return False
if __name__ == '__main__':
target = 20
matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]
result = solution(matrix, target)
print(f'{result}')
세로로 이분탐색 후, 가로로 이분탐색하면 문제가 풀릴 것이라고 직관적으로 생각하게 된다.
그렇게 풀었고 실제 책의 풀이와는 다르지만, 리트코드에서 퍼포먼스차이는 없어보였다.
이분탐색 익히기