이진 탐색
탐색 알고리즘(Search algorithms)
- 자료구조에서 원하는 조건에 맞는 자료를 찾는 것
- 선형 자료구조의 경우, 크게 세 가지 알고리즘이 있음
-> 정렬되지 않은 자료: 선형 탐색
-> 정렬된 자료: 이진 탐색
-> 해싱된 자료: 해시 탐색
선형 탐색(Linear search)
- 순차 탐색(Sequential search)라고도 부르며, 가장 단순한 탐색 방법
- 순서대로 하나씩 비교하기 때문에 O(N)의 시간복잡도를 가짐
이진 탐색(Binary search)
- 이분 탐색이라고도 부르며, 정렬된 자료의 탐색에 최적화된 알고리즘
- 탐색 범위를 절반씩 줄여가기 때문에 시간복잡도는 O(logN)
이진 탐색 과정
- 정렬된 배열에서 30을 찾아가는 과정
이진 탐색 문제 풀이
1) 이진 탐색을 두가지 방법으로 구현하시오.
- 반복문 구조
- 재귀 호출 구조
입력 리스트arr은 정렬되어 있으며, 이진 탐색의 목표는arr에서target을 찾아, 그 인덱스를 출력하는 것이다.
만약target이arr에 속하지 않으면-1을 출력한다. - 매개변수 형식
arr = [10, 20, 40, 50, 60, 70]
target = 40 - 반환값 형식
2
def solution1(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
if arr[mid] > target:
right = mid - 1
else:
left = mid + 1
return -1
def solution2(arr, target, left=0, right=None):
if right is None:
right = len(arr) - 1
if left > right:
return -1
mid = (left + right) // 2
if arr[mid] == target:
return mid
if arr[mid] > target:
return solution2(arr, target, left, mid-1)
else:
return solution2(arr, target, mid+1, right)
if __name__ == '__main__':
arr = [10, 20, 40, 50, 60, 70]
target = 40
sol = solution1(arr, target)
print(sol)
sol = solution2(arr, target)
print(sol)2) 민수는 택배 운송 기사로, 하루에 한번씩 차량을 가득 채워서 운반을 한다.
리스트 weights에는 보유한 택배 상품의 무게가 각각 기록되어 있다.
delivery는 택배 상품을 모두 배송해야 하는 납기까지 남은 일 수이다.
delivery이내에 모든 택배 상품을 배송하려면 필요한 차량의 최소 적재량을 구하시오.
단, 택배 상품은 순서대로 배송해야 한다.
- 매개변수 형식
weights = [3, 2, 2, 4, 1, 4]
delivery = 3 - 반환값 형식
6
def solution(weights, delivery):
left = max(weights)
right = sum(weights)
answer = float('inf')
while left < right:
mid = (left + right) // 2
days = 1
current_weight = 0
for w in weights:
if current_weight + w > mid:
days += 1
current_weight = 0
current_weight += w
if days > delivery:
left = mid + 1
else:
answer = min(answer, mid)
right = mid - 1
return answer
if __name__ == '__main__':
weights = [3, 2, 2, 4, 1, 4]
delivery = 3
sol = solution(weights, delivery)
print(sol)3) 체육관에 농구공을 1개씩 담을 수 있는 통이 일렬로 배치되어 있다.
통의 위치는 정수 배열 buckets로 주어지며, 농구공 총 m개를 통 안에 넣으려고 한다.
i번째 통에 들어있는 농구공과 j번째 통에 들어있는 농구공 사이의 거리는 |buckets[j] - buckets[i]|라고 하자.
이 때, 농구공 사이의 거리 중 가장 가까운 거리가 최대가 되도록 배치하려고 한다.
위 조건에 맞게 배치했을 때 농구공 사이의 최소 거리를 구하시오.
- 입력 예시
buckets = {1, 2, 3, 4, 7}
m = 3 - 출력 예시
3
def solution(buckets, m):
left = 0
right = max(buckets)
buckets.sort()
answer = 0
while left <= right:
mid = (left + right) // 2
n = 1
last = 0
for i in range(1, len(buckets)):
if buckets[i] - buckets[last] >= mid:
last = i
n += 1
if n >= m:
break
if n >= m:
answer = max(answer, mid)
left = mid + 1
else:
right = mid - 1
return answer
if __name__ == '__main__':
buckets = [1, 2, 3, 4, 7]
m = 3
sol = solution(buckets, m)
print(sol)투 포인터(Two pointers)
-
배열에서 두 개의 포인터(인덱스)를 사용하여 원하는 결과를 얻는 방법
-
두개 포인터의 배치 방법
-> 같은 방향에서 시작: 첫 번재 원소에 둘 다 배치
-> 서로 다른 방향에서 시작: 첫 번째 원소와 마지막 원소에 배치 -
다중 for문의 복잡도를 좀 더 선형적으로 풀 수 있음
-> ex) 범위를 다루는 이중 for문()을 으로 해결
예시
- 아래 배열에서 부분합이 9가 되는 구간을 찾는 방법
-> 기존 단순 for문 이용
-> 투 포인터 방법
투 포인터 문제 풀이
1) 문자열 s 를 거꾸로 출력하는 프로그램을 작성하세요.
단, 각 단어의 알파벳 순서는 그대로 출력합니다.
문장에 공백이 여러개일 시, 단어와 단어 사이 하나의 공백을 제외한 나머지 공백은 제거하세요.
- 매개변수 형식
s = " the sky is blue" - 반환값 형식
blue is the sky
def solution(s):
return ' '.join(list(filter(len, s.split(' ')))[::-1])
if __name__ == '__main__':
s = " the sky is blue"
sol = solution(s)
print(sol)2) 유미는 소설 작가로, 최근 작품이 베스트셀러가 되어 큰 부를 거머쥐었다.
유미는 마트에서 저녁에 쓸 요리 재료를 구매하려고 한다. 필요한 요리 재료는 ingredients 배열에 정리해 두었다.
평소에는 무척 검소한 유미는, 처음으로 "여기서부터 저기까지 다 주세요!"라고 외치고 싶어졌다.
마트에 진열된 품목은 items[i]로 주어지며, 유미는 필요한 요리 재료가 모두 포함되는 가장 최소한의 구간을 선택하려고 한다.
이 때 유미가 구매할 구간의 길이를 출력하시오.
- 매개변수 형식
ingredients = ["생닭", "인삼", "소주", "대추"]
items = ["물", "인삼", "커피", "생닭", "소주", "사탕", "생닭", "대추", "쌀"] - 반환값 형식
7
def solution(ingredients, items):
buy_dict = dict()
left, right = 0, 0
result = len(items)
set_a = set(ingredients)
buy_dict[items[left]] = 1
if set_a.issubset(buy_dict.keys()):
result = 1
return result
while left <= right: # O(N)
if set_a.issubset(buy_dict.keys()):
result = min(result, right - left + 1)
if buy_dict[items[left]] == 1:
del buy_dict[items[left]]
else:
buy_dict[items[left]] -= 1
left += 1
else:
right += 1
if right == len(items):
break
if items[right] in buy_dict:
buy_dict[items[right]] += 1
else:
buy_dict[items[right]] = 1
return result
if __name__ == '__main__':
ingredients = ["생닭", "인삼", "소주", "대추"]
items = ["물", "인삼", "커피", "생닭", "소주", "사탕", "생닭", "대추", "쌀"]
sol = solution(ingredients, items)
print(sol)3) 중복되지 않는 정수로 이루어진 배열 arr가 있다. 이 배열에서 중복되지 않게 3개의 수를 골라 더해서, 정수 target과 가장 가까운 숫자를 만들고자 한다. 이 때, 만들 수 있는 가장 가까운 숫자를 출력하시오.
단, target과 거리가 같은 숫자를 2개 만들 수 있을 경우 더 작은 숫자를 반환하시오.
- 입력 예시
arr = [5, 2, 15, 3, 10, 12]
target = 21 - 출력 예시
20 - 예시입출력 설명
21은 세 가지 숫자를 더해서 만들 수 없으나,
2 + 15 + 3 = 20,5 + 2 + 15 = 22두 가지는 모두 만들 수 있다.
문제의 조건에 의해 더 작은 숫자인20을 출력한다.
def solution(arr, target):
N = len(arr)
closest_diff = float('inf')
closest_sum = 0
arr.sort()
for left in range(N - 2):
mid = left + 1
right = N - 1
while mid < right:
curr_sum = arr[left] + arr[mid] + arr[right]
curr_diff = abs(target - curr_sum)
if curr_diff < closest_diff:
closest_diff = curr_diff
closest_sum = curr_sum
elif curr_diff == closest_diff and closest_sum > curr_sum:
closest_sum = curr_sum
if curr_sum < target:
mid += 1
elif curr_sum > target:
right -= 1
else:
return target
return closest_sum
if __name__ == '__main__':
arr = [5, 2, 15, 3, 10, 12]
target = 21
sol = solution(arr, target)
print(sol)이 글은 제로베이스 데이터 취업 스쿨의 강의 자료 일부를 발췌하여 작성되었습니다
