from bisect import bisect
def binary_search(nums, target):
def bs(start, end):
if start > end:
return -1
mid = (start + end) // 2
if nums[mid] < target:
return bs(mid + 1, end)
elif nums[mid] > target:
return bs(start, mid - 1)
else:
return mid
return bs(0, len(nums) - 1)
assert binary_search(nums=[-1, 0, 3, 5, 9, 12], target=9) == 4
assert binary_search(nums=[-1, 0, 3, 5, 9, 12], target=2) == -1
def binary_search_builtin(nums, target):
idx = bisect.bisect_left(nums, target)
# idx == len(nums) 가능하기 떄문.
"""Return the index where to insert item x in list a, assuming a is sorted.
The return value i is such that all e in a[:i] have e < x, and all e in
a[i:] have e >= x. So if x already appears in the list, a.insert(x) will
insert just before the leftmost x already there.
Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.
"""
if idx < len(nums) and nums[idx] == target:
return idx
else:
return -1이진 트리 구조에 대해서 배움
처음 쓰기에 아직은 활용을 잘 못하지만,
단순히 효율적인 검색이 아니라 교차 계산에도 사용이 가능한듯 함
from typing import List
class Solution:
def twoSum1(self, numbers: List[int], target: int) -> List[int]:
already = set()
for idx, number in enumerate(numbers):
if value not in already:
value = target - number
if value in numbers[idx+1:]:
return [idx+1,numbers[idx+1:].index(value)+idx+2]
already.add(number)
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left, right = 0, len(numbers) - 1
while left < right:
cal_sum = numbers[left] + numbers[right]
if cal_sum > target:
right -= 1
elif cal_sum < target:
left += 1
else:
return left + 1, right + 1
def twoSum(self, numbers: List[int], target: int) -> List[int]:
for idx, cur_num in enumerate(numbers):
expected = target - cur_num
left, right = idx + 1, len(numbers) - 1
while left <= right:
mid = left + (right - left) // 2
if numbers[mid] < expected:
left = mid + 1
elif numbers[mid] > expected:
right = mid - 1
else:
return idx + 1, mid + 1
def twoSum(self, numbers: List[int], target: int) -> List[int]:
for idx, cur_num in enumerate(numbers):
expected = target - cur_num
import bisect
i = bisect.bisect_left(numbers, expected, idx + 1) # 현재 cur_num의 [idx+1~끝] 범위에 target이 있는지 검사
if i < len(numbers) and numbers[i] == expected: # 만약 target이 존재하면
return idx + 1, i + 1
페어 프로그래밍을 진행하면서 직관적으로 하다가 다양한 테스트 케이스에 걸려서 시간을 소비했었음
그래도 두명의 다른 의견이 있으니 다른 방향성을 고루 고민해볼 수 있었음
성능적으로 안좋고, 이진트리를 사용하지도 않았음,
다음에는 배운 자료 구조나 정렬 방식을 잘 활용해야겠음
def bs_rotated(nums, target):
def bs(lst, start, end):
if start > end:
return -1
mid = (start + end) // 2
if lst[mid] < target:
return bs(lst, mid + 1, end)
elif lst[mid] > target:
return bs(lst, start, mid - 1)
else:
return mid
if not nums:
return -1
left = 0
right = len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
added = nums + nums[:left]
result = bs(added, left, len(added) - 1)
return result if result == -1 else result % len(nums)이진 탐색의 활용법에서 좀더 효율적으로 쓰는 법이 나옴
리스트에서 특정 부분을 add 한뒤 그 부분의 길이만큼을 연산에서 고려해주는 방식
[부품 탐색]
import copy
import random
import time
n1 = 1000000
shop1 = random.sample(range(1,1000001),1000000)
m1 = 500000
customer1 = random.sample(range(1,500001),500000)
shop2 = copy.deepcopy(shop1)
customer2 = copy.deepcopy(customer1)
shop3 = copy.deepcopy(shop1)
customer3 = copy.deepcopy(customer1)
def binary_search(nums, target):
def bs(start, end):
if start > end:
return -1
mid = (start + end) // 2
if nums[mid] < target:
return bs(mid + 1, end)
elif nums[mid] > target:
return bs(start, mid - 1)
else:
return mid
return bs(0, len(nums) - 1)
# 1
start_time1 = time.process_time()
shop1.sort()
for i in customer1:
result = binary_search(shop1, i)
if result != None:
pass
else:
pass
end_time1 = time.process_time()
print(f"작동시간1 : {end_time1 - start_time1}")
# 2
start_time2 = time.process_time()
array2 = [0] * 1000001
for i in shop2:
array2[int(i)] = 1
for i in customer2:
if array2[i] == 1:
pass
else:
pass
end_time2 = time.process_time()
print(f"작동시간2 : {end_time2 - start_time2}")
# 3
start_time3 = time.process_time()
array3 = set(shop3)
for i in customer3:
if i in array3:
pass
else:
pass
end_time3 = time.process_time()
print(f"작동시간3 : {end_time3 - start_time3}")
우리는 첫번째 방식으로 풀음
시간은 2번이랑 3번 문제에 비해 10배 정도나 느리게 계산됨
이신탐색을 배웠다고 굳이 쓸 필요는 없다는 것을 배움
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
x_start = 0
x_end = len(matrix[0])-1
y_start = 0
y_end = len(matrix)-1
while 0 <= x_end:
if x_start > x_end:
break
mid = (x_start+x_end)//2
if matrix[0][mid] < target:
x_start = mid+1
elif matrix[0][mid] > target:
x_end = mid-1
else:
return True
while 0 <= y_end:
if y_start > y_end:
break
mid = (y_start+y_end)//2
if matrix[mid][0] < target:
y_start = mid+1
elif matrix[mid][0] > target:
y_end = mid-1
else:
return True
for y in range(y_end+1):
for x in range(x_end+1):
if matrix[y][x] == target:
return True
return False
의견 충돌로 잠시 각자만의 방식으로 품
제법 괴랄하지만, 그래도 나름 성능을 고려했음
페어프로그래밍에 장점은, 제대로 몰입이 가능하도록 하게 해준다는 것 같음
시간 낭비 없이 문제를 전부 풀때까지 우린 몰입을 했음
대신 그만큼 지침.....
달콤살벌