순차 탐색
가장 기본 탐색 방법으로 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
⇒ 시간만 충분하다면 항상 원하는 데이터를 찾을 수 있다 , 다만 처음부터 순서대로 모두 탐색해야하기 때문에 시간복잡도는 O(N)이다
def sequential_search(n,target,array):
for i in range(n):
if array[i] == target:
return i+1
input_data = input().split()
n = int(input_data[0])
target = input_data[1]
array = input().split()
print(sequential_search(n,target,array))
# 입력
# 5 apple
# banana melon grape apple mango
# 4이진탐색
탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘
- 이진탐색은 배열 데이터가 정렬되어 있어야만 사용할 수 있다.
- 이진탐색은 시작점,끝점,중간점으로 3개의 변수를 사용해 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 과정이다.
- 전체 데이터 개수는 10개지만 3번의 탐색으로 원한는 데이터를 찾을 수 있었다
- 원소의 개수가 절반씩 줄어들어 O(logN)이다.
- 탐색 범위가 2,000만을 넘어가면 이진 탐색으로 문제 접근해볼 것 !
재귀함수 이용
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)
elif array[mid] < target:
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)
반복문 이용
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
elif array[mid] < target:
start = mid+1
return None
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)
이진 탐색 트리
이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조
- 부모 노드보다 왼쪽 자식 노드가 작다
- 부모 노드보다 오른쪽 자식 노드가 크다
*이진탐색 문제는 입력 데이터가 많아 시간초과가 일어날 수 도 있다
그럴땐 sys 라이브러리를 이용하여 입력받는다
import sys
input_data = sys.stdin.readline().rstrip()
print(input_data)
문제 7-2 부품 찾기
문제
전자매장에 부품이 N개 있을때 손님이 주문한 부품들이 있는지 확인하는 문제
이진탐색을 이용
n = int(input())
products = list(map(int,input().split()))
m = int(input())
orderlist = list(map(int,input().split()))
products.sort()
def binary_search(arr,start,end,target):
if start > end :
return None
mid = (start+end)//2
if arr[mid] == target:
return mid
elif arr[mid] > target:
return binary_search(arr,start,mid-1,target)
elif arr[mid] < target:
return binary_search(arr,mid+1,end,target)
for target in orderlist:
result = binary_search(products,0,n-1,target)
if result == None:
print("no ")
else:
print("yes ")
# 입력
# 5
# 8 3 7 9 2
# 3
# 5 7 9
집합 자료형을 이용
n = int(input())
products = set(map(int,input().split()))
m = int(input())
orderlist = list(map(int,input().split()))
for target in orderlist:
if target in products:
print("yes",end=" ")
else:
print("no",end=" ")
집합 자료형
- 집합 자료형은 set() 키워드를 이용해서 집합을 만들 수 있다
- 단 순서가 없고, 중복을 허용하지 않는다.
문제 7-3 떡볶이 떡 만들기
문제
절단기에 높이를 설정하면 줄지어진 떡을 한번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다. 예를 들어 높이가 19,14,10,17cm인 떡이 있을 때 높이 15cm로 설정하면 손님은 총 6cm 떡을 가져갈 수 있다. 손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오
n,m = map(int,input().split())
arr = list(map(int,input().split()))
arr.sort()
start=0
end = arr[n-1]
target = m
mid = (start+end)//2
def binary_search(arr,start,end,target):
result=0
while start<=end:
mid = (start+end)//2
sum = 0
for i in arr :
if i > mid:
sum+=i-mid
if sum >= target :
result = mid
start = mid+1
elif sum < target:
end = mid - 1
return result
result = binary_search(arr,0,arr[n-1],m)
print(result)