파이썬 알고리즘 인터뷰 18장을 정리한 내용입니다.
이진 검색
Binary Search(이진 검색)이란 정렬된 배열에서 타겟을 찾는 검색 알고리즘이다.
- 이진 검색은 값을 찾아내는 시간 복잡도가 $O(\log n)$ 이라는 점에서 대표적인 로그 시간 알고리즘이며, 이진 탐색 트리와 유사한 점이 많다
- 이진 탐색 트리가 정렬된 구조를 저장하고 탐색하는 “자료구조” 라면 이진 검색은 정렬된 배열에서 값을 찾아내는 “알고리즘” 자체를 말한다
1
2
3
4
| import math
math.log2(100000000)
'''26.575424...'''
|
- 1억개의 아이템도 27번이면 모두 찾아낼 수 있다
이진 검색 예시
1
| array = [2, 4, 9, 15, 26, 28, 31]
|
- 이진 검색을 이용해서
9 를 찾아볼 것이다 - 배열은 오름차순으로 정렬되어 있다.
Step 1
- 임의의 값인
15 를 선택한다 - 찾을 값과 선택한 값을 비교한다 (9 < 15)
- 찾을 값은
15 를 기준으로 왼쪽에 있다는 것을 알 수 있다
Step 2
15 를 기준으로 왼쪽에 있는 배열을 다시 탐색한다- 임의의 값인
4 를 선택한다 - 찾을 값과 선택한 값을 비교한다 (4 < 9)
- 찾을 값은 선택한 값 오른쪽에 위치한다
Step 3
4 를 기준으로 오른쪽에 있는 배열을 정렬한다- 찾을 값
9 만 존재하며 원하는 값을 찾았다
이진 검색 종료
#65 이진 검색
정렬된 nums를 받아 이진 검색으로 target에 해당하는 인덱스를 찾아라
입력
1
2
3
4
| nums = [-1, 0, 3, 5, 9, 12]
target = 9
# answer = 4
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| def search(nums: list, 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)
|
- 재귀로 이진 검색을 구현한 것이다
- 절반씩 범위를 줄여나가면서 맞을 때까지 재귀 호출을 한다
반복 풀이
1
2
3
4
5
6
7
8
9
10
11
12
| def BS(nums: list, 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
|
이진 검색 모듈
1
2
3
4
5
6
7
| def moduleSearch(nums: list, target: int) -> int:
index = bisect.bisect_left(nums, target)
if index < len(nums) and nums[index] == target:
return index
else:
return -1
|
- 파이썬에 이진 검색 모듈을 이용해서 풀 수 있다
bisect 모듈은 이진 검색 알고리즘이다
이진 검색을 사용하지 않는 index 풀이
1
2
3
4
5
| def NotIndex(nums: list, target: int) -> int:
try:
return nums.index(target)
except ValueError:
return -1
|
- 파이썬에서 제공하는 해당 값의 인덱스를 찾아내는
index() 메소드를 활용한다 - 존재하지 않는 값이면 에러가 발생하기 때문에 예외처리를 해준다
- 이 코드는 이진 검색이 아니며 이진 검색을 요구하는 문제에는 사용하면 안된다
#66 회전 정렬된 배열 검색
특정 피벗을 기준으로 회전하여 정렬된 배열에서 target 값의 인덱스를 출력하라
입력
1
2
| nums = [4, 5, 6, 7, 0, 1, 2]
target = 1
|
피벗을 기준으로 한 이진 검색
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| def search(nums: list, target: int) -> int:
if not nums:
return -1
# 최솟값을 찾기
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
pivot = left
# 피벗 기준 이진 검색
left, right = 0, len(nums)
while left <= right:
mid = left + (right - left) // 2
mid_pivot = (mid + pivot) % len(nums)
if nums[mid_pivot] < target:
left = mid + 1
elif nums[mid_pivot] > target:
right = mid - 1
else:
return mid_pivot
return -1
|
#67 두 배열의 교집합
두 배열의 교집합을 구하라
입력
1
2
| num1 = [1, 2, 2, 1]
num2 = [2, 2]
|
이진 검색으로 일치 여부 판별
1
2
3
4
5
6
7
8
9
| def intersection(num1: list, num2: list) -> set:
res = set()
num2.sort()
for n1 in num1:
# 이진 검색으로 일치 여부 판별
i2 = bisect.bisect_left(num2, n1)
if len(num2) > 0 and len(num2) > i2 and n1 == num2[i2]:
res.add(n1)
return res
|
- 한쪽은 순서대로 탐색, 다른쪽은 정렬해서 이진 검색으로 값을 찾는다
num2 를 정렬한 상태에서 num1 을 순차 반복하면서 num2 를 이진 검색 한다
투 포인터로 일치 여부 판별
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| def intersectioin_two_pointer(num1: list, num2: list) -> set:
res = set()
num1.sort()
num2.sort()
i = j = 0
# 투 포인터 우측으로 이동하며 일치 여부 판별
while i < len(num1) and j < len(num2):
if num1[i] > num2[j]:
j += 1
elif num1[i] < num2[j]:
i += 1
else:
res.add(num1[i])
i += 1
j += 1
return res
|
- 각각의 입력받은 리스트를 정렬한다
- 값이 작은 쪽 배열 포인터가 한 칸씩 앞으로 이동하는 형태이고 어느 한쪽의 포인터가 끝까지 도달하면 종료하게된다
#68 두 수의 합
정렬된 배열을 받아 덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라 (배열의 시작은 1로 한다)
입력
1
2
| numbers = [2, 7, 11, 15]
target = 9
|
투 포인터
1
2
3
4
5
6
7
8
9
| def twoPointer(number: list, target: int) -> list:
left, right = 0, len(number) - 1
while not left == right:
if number[left] + number[right] < target:
left += 1
elif number[left] + number[right] > target:
right -= 1
else:
return [left + 1, right + 1]
|
bisect 모듈
1
2
3
4
5
6
7
| def bisect_slicing(number: list, target: int) -> list:
for k, v in enumerate(number):
expected = target - v
nums = number[k + 1]
i = bisect.bisect_left(nums, expected)
if i < len(nums) and number[i + k + 1] == expected:
return [k + 1, i + k + 2]
|
#69 2D 행렬 검색
mxn 행렬에서 값을 찾아내는 효율적인 알고리즘을 구현하라. 행렬은 왼쪽에서 오른쪽, 위에서 아래 오름차순으로 정렬되어 있다
첫 행의 맨 뒤에서 탐색
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| def searcgMatrix(matrix: list, target: int) -> bool:
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
|
- 첫 행의 맨 뒤 요소를 선택하고 타겟이 더 작으면 왼쪽으로, 크면 아래로 이동한다
파이썬 다운 방식
1
2
| def searchMat(matrix, target):
return any(target in row for row in matrix)
|
- 행렬에 값이 존재하는지 여부를 위에서부터 차례로 한 줄씩 탐색한다
