리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례로 확인하는 방법
# 순차 탐색 소스코드 구현
def sequential_search(n, target, array):
# 각 원소를 하나씩 확인하며
for i in range(n):
# 현재의 원소가 찾고자 하는 원소와 동일한 경우
if array[i] == target:
return i + 1 # 현재의 위치 반환 (인덱스는 0부터 시작하므로 1 더하기)
print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.")
input_data = input().split()
n = int(input_data[0]) # 원소의 개수
target = input_data[1] # 찾고자 하는 문자열
print("앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.")
array = input().split()
# 순차 탐색 수행 결과 출력
print(sequential_search(n, target, array))
데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 순차 탐색의 최악의 경우 시간 복잡도는 O(N)이다.
배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘
- 위치를 나타내는 변수 3개를 사용한다 (시작점, 끝점, 중간점)
- 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다
이진 탐색은 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도가 O(logN)이다.
* 이진 탐색을 구현하는 방법
# 이진 탐색 소스코드 구현 (재귀 함수)
def binary_search(array, target, start, end):
if start > end:
return None
mid = (start+end)//2
# 찾은 경우 중간점 인덱스 반환
if target == mid:
return mid
# 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
elif array[target] < array[mid] :
return binary_search(array, target, start, mid-1)
# 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
else:
return binary_search(array, target, mid+1, end)
# n(원소의 개수)과 target(찾고자 하는 문자열)을 입력받기
n, target = 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
# 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
else:
start = mid+1
return None
# n(원소의 개수)과 target(찾고자 하는 문자열)을 입력받기
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)
코딩 테스트에서 탐색 범위가 2000만을 넘어가면 이진 탐색으로 접근해보자!
처리해야할 개수나 값이 1000만 이상으로 넘어가면 이진 탐색과 같이 O(logN)의 속도를 내는 알고리즘을 떠올려야 문제를 풀 수 있다!
1. 트리 자료구조 중 가장 간단한 형태
2. 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
동빈이네 전자 매장에는 부품 N개가 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자
예를 들어 가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자.
N = 5
[8, 3, 7, 9, 2]
손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다.
M = 3
[5, 7, 9]
이때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes를, 없으면 no를 출력한다. 구분은 공백으로 한다.
입력조건
출력조건
입력예시
5
8 3 7 9 2
3
5 7 9
출력예시
no yes yes
내 풀이
n = int(input())
array = list(map(int,input().split()))
array.sort()
m = int(input())
array2 = list(map(int,input().split()))
array2.sort()
def binary_search(start, end, target):
while start <= end:
mid = (start + end) // 2
if target == array[mid]:
return print('yes', end=' ')
elif target > array[mid]:
start = mid+1
else:
end = mid-1
return print('no', end=' ')
for i in array2:
binary_search(0, len(array), i)
오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다.
절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다.
예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm이다. 손님은 6cm만큼의 길이를 가져간다.
손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.
입력조건
출력조건
입력예시
4 6
19 15 10 17
출력예시
15
내 풀이
n, m = map(int, input().split())
array = list(map(int, input().split()))
def binary_search(start, end, target):
while start <= end:
sum=0
mid = (start + end) // 2
for i in array:
if i > mid:
sum += i-mid
if sum == target:
return print(mid)
elif sum < target:
end = mid - 1
else:
start = mid + 1
array.sort()
binary_search(0, array[-1], m)