📌 65) 이진 검색 ( 리트코드 704. Binary Search)
✔ 풀이1 (재귀 풀이)
class Solution:
def search(self, nums: List[int], target: int) -> int:
def binary_search(left, right):
if left <= right:
mid = (left + right) // 2 #중간 인덱스
if nums[mid] < target: #타겟은 중앙의 오른쪽에 위치
return binary_search(mid + 1, right)
elif nums[mid] > target: #타겟은 중앙의 왼쪽에 위치
return binary_search(left, mid - 1)
else: #타겟이면
return mid
else:
return -1
return binary_search(0, len(nums) - 1)✔ 풀이2 (반복 풀이)
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
else:
return mid
return -1✔ 풀이3 (이진 검색 모듈 이용)
import bisect
class Solution:
def search(self, nums: List[int], target: int) -> int:
#bisect모듈의 bisect_left(list, target)은 list에 target을 정렬순으로 삽입할때
#넣을 수 있는 위치 중 가장 왼쪽에 위치한 위치를 반환하는 함수
idx = bisect.bisect_left(nums, target)
if idx < len(nums) and nums[idx] == target:
return idx
return -1✔ 풀이4 (이진 검색 사용하지 않는 index 풀이)
import bisect
class Solution:
def search(self, nums: List[int], target: int) -> int:
try:
return nums.index(target)
except ValueError:
return -1🔮 이진 검색 알고리즘 버그
- 중앙의 위치를 구하는 풀이 mid = (left + right) // 2에서 버그 발생
- 수학적으로는 문제 없지만 컴퓨터과학에서는 문제를 일으킬 만한 소지가 있음
- 왜? 자료형에는 최대값이 존재하기 때문!
- 즉, 두 수의 합이 자료형의 최대값을 넘어선다면 (int형일 때 231-1을 넘어선다면) 오버플로(Overflow)발생함
- 사실 파이썬은 임의 정밀도 정수형을 지원하기 때문에 이 문제에서 자유롭지만, 자료형이 엄격한 언어들에는 발생할 수 있는 문제이기때문에 주의가 필요함
따라서 중앙의 위치를 구하는 풀이를 다음과 같이 수정한다.
- mid = left + (right - left) // 2
📌 66) 회전 정렬된 배열 검색 ( 리트코드 33. Search in Rotated Sorted Array )
✔ 풀이 (피벗을 기준으로 한 이진 검색)
class Solution:
def search(self, nums: List[int], target: int) -> int:
#특정 피벗을 기준으로 회전되 배열
#최솟값의 인덱스 = 특정 피벗
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] < nums[right]: #최솟값은 mid인덱스 포함 왼쪽에 위치
right = mid
else: #nums[mid] >= nums[right]일때, 최솟값은 mid인덱스 오른쪽에 위치
left = mid + 1
pivot = left
#target값의 인덱스 찾기
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
real_mid = (mid + pivot) % len(nums) #진짜 중앙값의 위치 (모듈로 연산)
if nums[real_mid] < target:
left = mid + 1
elif nums[real_mid] > target:
right = mid - 1
else:
return real_mid
return -1📌 67) 두 배열의 교집합 ( 리트코드 349. Intersection of Two Arrays )
✔ 풀이1 (브루트 포스로 계산) 👉 시간복잡도 O(n2)
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
result = set()
for num1 in nums1:
for num2 in nums2:
if num1 == num2:
result.add(num1)
return result✔ 풀이2 (이진 검색으로 일치 여부 판별) 👉 시간복잡도 O(nlogn)
import bisect
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
#한쪽은 순서대로 탐색하고, 다른 쪽은 정렬해서 이진 검색으로 값을 찾으면
#시간복잡도 O(nlogn)이 됨
result = set()
nums2.sort() #이진 검색은 정렬 된 배열에서 사용해야함
for num1 in nums1:
idx = bisect.bisect_left(nums2, num1)
if idx < len(nums2) and num1 == nums2[idx]:
result.add(num1)
return result✔ 풀이3 (투 포인터로 일치 여부 판별) 👉 시간복잡도 O(nlogn)
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
#양쪽 다 정렬하여 투 포인터로 풀이
nums1.sort()
nums2.sort()
result = set()
i, j = 0, 0 #각각 nums1,nums2의 포인터
while i < len(nums1) and j < len(nums2):
if nums1[i] < nums2[j]:
i += 1
elif nums1[i] > nums2[j]:
j += 1
else:
result.add(nums1[i])
i += 1
j += 1
return result📌 68) 두 수의 합II ( 리트코드 167. Two Sum II - Input array is sorted)
✔ 풀이1 (투 포인터) 👉 시간복잡도 O(n)
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left, right = 0, len(numbers) - 1
while left < right:
if numbers[left] + numbers[right] < target:
left += 1
elif numbers[left] + numbers[right] > target:
right -= 1
else:
return left + 1, right + 1✔ 풀이2 (이진 검색) 👉 시간복잡도 O(nlogn)
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
for i, n in enumerate(numbers):
expected = target - n
left, right = 0, 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:
#인덱스 다를 때
if i != mid:
return i + 1, mid + 1
#인덱스 같을 때, 양쪽옆에 있는 값 중 같은 값 있으면 그 인덱스를 return
if numbers[mid] == numbers[mid + 1]:
return i + 1, mid + 2
elif numbers[mid] == numbers[mid - 1]:
return i + 1, mid
else:
break #while문 빠져나오고 for문 다음 반복✔ 풀이3 (bisect모듈 + 슬라이싱)
import bisect
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
for i, n in enumerate(numbers):
expected = target - n
idx = bisect.bisect_left(numbers[i + 1:], expected)
if idx < len(numbers[i + 1:]) and numbers[i + idx + 1] == expected:
return i + 1, i +idx + 2👉 실행 속도가 2510ms로 2초 이상 소요됨
👉 슬라이싱은 편리하고 빠른 모듈이지만, 무분별하게 남용하다 보면 속도 저하의 주범이 될 수 있음
👉 성능 개선 해야함
✔ 풀이4 (bisect모듈 + 슬라이싱 최소화)
import bisect
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
for i, n in enumerate(numbers):
expected = target - n
nums = numbers[i + 1:]
idx = bisect.bisect_left(nums, expected)
if idx < len(nums) and numbers[i + idx + 1] == expected:
return i + 1, i +idx + 2👉 풀이3에서 슬라이싱을 줄이기 위해 nums 변수에 한 번만 사용해 담아두는 형태로 개선함
👉 1128ms로 풀이3에 비해 2배가량 속도가 빨라졌지만 투 포인터에 비해 많이 느림
👉 조금 더 개선이 필요함
✔ 풀이5 (bisect모듈 + 슬라이싱 제거)
import bisect
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
for i, n in enumerate(numbers):
expected = target - n
idx = bisect.bisect_left(numbers, expected, i + 1)
if idx < len(numbers) and numbers[idx] == expected:
return i + 1, idx + 1👉 bisect모듈의 기능을 활용하여 139ms로 속도 개선 성공
🔮 슬라이싱 성능
- 파이썬의 슬라이싱은 매우 효율적이고 빠름
- 근데 왜 위와 같은 상황이 발생했을까?
👉 슬라이싱은 매번 새롭게 객체를 생성해서 할당하고, 엄청나게 큰 배열의 경우 슬라이싱으로 새로운 객체를 생성하는 데 상당한 시간이 들기 때문이다. - ex 👇
#case1
a = [x for x in range(100000000)]
print(id(a)) #4365568832
b = a
print(id(b)) #4365568832
#=>여기서 b변수는 a변수 객체를 참조만 하면 되기 때문에 둘은 동일한 ID를 갖고 있음
#case2
c = a[:]
print(id(c)) #4365788800
#=>여기서 c변수는 슬라이싱으로 할당했기때문에 객체 참조가 아닌 요소 전체,
#즉 1억개를 모두 복사하는 과정을 거침 - 매우 큰 배열의 경우 슬라이싱을 하게 되면, 전체를 복사하는 과정이나 배열의 길이를 계산하는 부분에서 상당한 시간이 소요되므로 주의가 필요하다.
📌 69) 2D 행렬 검색II ( 리트코드 240. Search a 2D Matrix II )
✔ 풀이1 (첫 행의 맨 뒤에서 탐색)
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
row, col = 0, len(matrix[0]) - 1 #matrix[row][col] 행, 렬
while row < len(matrix) and col >= 0:
if matrix[row][col] < target: #target보다 작을 때
row += 1
elif matrix[row][col] > target: #target보다 클 때
col -= 1
else: #target과 같을때
return True
return False✔ 풀이2 (pythonic way)
👉 파이썬 all(), any() 함수 사용하여 pythonic way로 풀이
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
return any([target in row for row in matrix])