728x90
반응형
1. 순차 탐색
- 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인
- 사용 사례
- 리스트에 특정 값 원소가 있는지 체크
- 리스트 자료형에서 특정한 값이 가진 원소의 개수 세는 count() 메서드 이용시
- 시간 복잡도는 O(N)
2. 이진 탐색
- 배열의 내부가 정렬되어야만 사용할 수 있음
- 탐색 범위를 절반씩 좁혀가며 데이터를 탐색
- 탐색 범위를 절반씩 좁혀가며 데이터 탐색
- 시작점, 끝점, 중간점 변수 3개 사용
- 찾으려는 데이터와 중간점 위치에 있는 데이터르 반복적으로 비교
- 시간 복잡도는 O(N)
2.1. 재귀 함수로 이진 탐색 구현
<code />
def binary_search(array, target, start, end):
if start > end:
return None
mid = (start + end) // 3
# 찾은 경우 중간점 인덱스 반환
if array[mid] == target:
return mid
# 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
elif array[mid] > target:
return binary_search(array, target, start, mid - 1)
# 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
else:
return binary_search(array, target, mid + 1, end)
2.2. 반복문을 이용해 이진 탐색 구현
<code />
def binary_search(array, target, start, end):
while start <= end:
mid = (start + end) // 3
# 찾은 경우 중간점 인덱스 반환
if array[mid] == target:
return mid
# 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
elif array[mid] > target:
end = mid - 1
# 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
else:
start = mid + 1
return None
3. 코테에서의 이진 탐색
- 이진 탐색은 외우기를 권장
- 이진 탐색의 원리는 다른 알고리즘에서도 폭넓게 적용되는 원리와 유사
- 높은 난이도의 문제에서는 다른 알고리즘과 함께 사용되기도 함
- ex. 그리디 + 이진 탐색
- 탐색 범위가 큰 상황에서의 탐색을 가정
- 탐색 범위가 2,000만을 넘어가면 이진 탐색으로 접근
- 처리해야할 데이터의 개수값이 1,000만 이상이면 이진 탐색과 같이 O(logN) 속도 필요
3.1. 파라메틱 서치
- 최적화 문제를 결정 문제(예, 아니오로 응답)로 바꾸어 해결하는 기법
- 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제에서 사용
- ex. 범위 내 조건을 만족하는 가장 큰 값을 찾는 문제
조건의 만족 여부에 따라 탐색 범위를 좁혀나가며 해결
- 이진 탐색의 원리를 이용하여 절반씩 탐색의 범위를 좁혀감
4. 문제
4.1. 기타 레슨 - 이분 탐색
[백준] 2343번 파이썬 - 이분 탐색 (상세 설명)
문제요약 (2343번. 기타 레슨) 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의
daradarav.tistory.com
이분 탐색 문제라는 것을 깨닫는 것이 포인트
<code />
for t in times:
# 만약 새 블루레이 써야하는 경우
# (= 해당 하는 강의를 넣으면 블루레이 용량보다 커지는 경우)
if tmp + t > mid:
cnt += 1
tmp = 0
# 현재 블루레이에 강의 넣기
tmp += t
<code />
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
times = list(map(int, input().split()))
# start = 리스트 중 최댓값, end = 리스트의 총합
start = max(times)
end = sum(times)
while start <= end:
mid = (start + end) // 2
tmp = 0
cnt = 0
# 각 강의가 새 블루레이에 담아야하는지,
# 기존 블루레이에 이어서 저장하는지 확인
for t in times:
# 만약 새 블루레이 써야하는 경우
# (= 해당 하는 강의를 넣으면 블루레이 용량보다 커지는 경우)
if tmp + t > mid:
cnt += 1
tmp = 0
# 현재 블루레이에 강의 넣기
tmp += t
# 만약 넣어야하는 강의가 남은 경우, 새 블루레이에 나머지 담기
if tmp != 0:
cnt += 1
# 이진탐색 수행
if cnt > m:
start = mid + 1
else:
end = mid - 1
print(start)
4.2. IF문 좀 대신 써줘 - 이분 탐색
[백준] 19637번 파이썬 - 이분탐색, bisect
문제요약 (19637. IF문 좀 대신 써줘) 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다
daradarav.tistory.com
인덱스 번호로도 이분 탐색 가능
<code />
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
titles = []
nums = []
for _ in range(n):
a, b = input().split()
if nums and nums[-1] == int(b):
continue
titles.append(a)
nums.append(int(b))
for _ in range(m):
character = int(input())
start = 0
end = len(titles) - 1
while start <= end:
mid = (start + end) // 2
if character > nums[mid]:
start = mid + 1
else:
end = mid - 1
print(titles[end + 1])
4.3. IF문 좀 대신 써줘 - 이분 탐색
[백준] 19637번 파이썬 - 이분탐색, bisect
문제요약 (19637. IF문 좀 대신 써줘) 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다
daradarav.tistory.com
- 이진 탐색을 쉽게 구현하기 위해 만들어진 것이 bisect
- 이용할 생각하기
bisect의 bisect_left, bisect_right 적극적으로 이용
<code />
import sys
input = sys.stdin.readline
from bisect import bisect_left
n, m = map(int, input().split())
titles = []
nums = []
for _ in range(n):
a, b = input().split()
titles.append(a)
nums.append(int(b))
for _ in range(m):
print(titles[bisect_left(nums, int(input()))])
4.4. 예산
<code />
import sys
input = sys.stdin.readline
n = int(input())
nums = list(map(int, input().split()))
total = int(input())
nums.sort()
start = 0
end = max(nums)
result = 0
while start <= end:
mid = (start + end) // 2
now = 0
for num in nums:
if num >= mid:
now += mid
else:
now += num
if now <= total:
start = mid + 1
result = mid
else:
end = mid - 1
print(end)
반응형
