탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘
순차탐색
리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
def sequential_search(n, target, array) :
for i in range(n) :
if array[i] == target :
return i + 1
data = input().split() # 원소 개수, 찾을 문자열 입력
n = int(data[0]) # 원소 개수
target = data[1] # 찾을 문자열
array = input().split() # n만큼 문자열 입력
print(sequential_search(n, target, array))
이진탐색
찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교
def binary_search(array, target, start, end) :
if start > end :
return None
mid = (start + end) // 2
# 찾은 경우 중간점 인덱스 반환
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)
n, target = list(map(int, input().split()))
array = list(map(int, input().split()))
result = binary_search(array, target, 0, n - 1)
if result == None :
print("원소가 존재하지 않습니다.")
else :
print(result + 1)
트리 자료구조
노드와 노드의 연결로 표현하며 여기에서 노드는 정보의 단위로써 어떠한 정보를 가지고 있는 개체로써 이해한다.
이진 탐색 트리
이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조
빠르게 입력받기
느린 input() 함수 대신 sys 라이브러리의 readline() 함수 사용import sys input_data = sys.stdin.readline().rstrip()
부품 찾기
💡 이진 탐색 알고리즘
def binary_search(array, target, start, end) :
while start <= end :
mid = (start + end) // 2
# 찾은 경우 중간점 인덱스 반환
if array[mid] == target :
return mid
# 중간점 값이 찾을 값보다 큰 경우 왼쪽 확인
elif array[mid] > target :
end = mid - 1
# 중간점 값이 찾을 값보다 작은 경우 오른쪽 확인
else :
start = mid + 1
return None
n = int(input()) # 개수
array = list(map(int, input().split())) # 전체 원소
array.sort()
m = int(input()) # 찾을 원소 개수
x = list(map(int, input().split())) # 찾을 원소
for i in x :
result = binary_search(array, i, 0, n - 1)
if result != None :
print("yes", end=' ')
else :
print("no", end=' ')
💡 계수 정렬
n = int(input()) # 개수
array = [0] * 1000001
# 전체 원소 값에 해당하는 인덱스의 값 1
for i in input().split() :
array[int(i)] = 1
m = int(input()) # 찾을 원소 개수
x = list(map(int, input().split())) # 찾을 원소
for i in x :
if array[i] == 1:
print('yes', end=' ')
else :
print('no', end=' ')
💡 집합 자료형 - set() 함수는 집합 자료형 초기화
n = int(input()) # 개수
array = set(map(int, input().split())) # 전체 원소 집합 자료형(set)에 기록
m = int(input())
x = list(map(int, input().split()))
for i in x :
if i in array :
print('yes', end=' ')
else :
print('no', end=' ')
떡볶이 떡 만들기
💡 이진 탐색 문제 & 파라메트릭 서치 유형 (최적화 문제를 결정 문제로 바꾸어 해결하는 기법) - 원하는 조건을 만족하는 가장 알맞은 값
n, m = map(int, input().split()) # 개수, 길이
array = list(map(int, input().split())) # 개별 길이
start = 0
end = max(array)
result = 0
while(start <= end) :
total = 0
mid = (start + end) // 2
for x in array :
# 자르고 남은 길이
if x > mid :
total += x - mid
if total < m :
end = mid - 1
else :
result = mid
start = mid + 1
print(result)