🔊본 포스팅은 '(이코테 2021) 이것이 취업을 위한 코딩 테스트다 with 파이썬' 유튜브 강의를 수강하고 정리한 글입니다.
- 순차 탐색
: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법- 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용한다.
- 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소(데이터)를 찾을 수 있다는 장점이 있다.
- 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 순차 탐색의 최악의 경우 시간 복잡도는 O(N)이다.
# 순차 탐색 소스코드 구현
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))- 이진 탐색
: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
이진 탐색은시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다.
동작 방법
이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾는 예시를 살펴봅시다.
[Step 1] 시작점: 0, 끝점: 9, 중간점: 4(소수점 이하 제거)
중간점에 위치하는 값인 '8'과 찾고자 하는 값인 '4'와 비교하여 어떤 값이 더 큰지 비교
만약 찾고자 하는 값보다 중간점의 값이 더 크다면 중간점에서부터 오른쪽에 위치한 값들은 확인할 필요가 없다.[Step 2] 시작점: 0, 끝점: 3, 중간점: 1(소수점 이하 제거)
중간점에 위치하는 값인 '2'보다 우리가 찾고자 하는 값인 '4'가 더 크기 때문에
중간점을 포함해서 왼쪽에 있는 데이터는 확인할 필요가 없다.[Step 3] 시작점:2, 끝점: 3, 중간점: 2(소수점 이하 제거)
재귀적으로 구현한 이진탐색
# 이진 탐색 소스코드 구현 (재귀 함수)
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(찾고자 하는 값)을 입력 받기
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
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)파이썬 이진 탐색 라이브러리
bisect_left(a,x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환
bisect_right(a,x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환
값이 특정 범위에 속하는 데이터 개수 구하기
from bisect import bisect_left, bisect_right
값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(a, left_value, right_value):
right_index = bisect_right(a, right_value)
left_index = bisect_left(a, left_value)
return right_index - left_index
# 배열 선언
a = [1,2,3,3,3,3,4,4,8,9]
# 값이 4인 데이터 개수 출력
print(count_by_range(a,4,4))
# 값이 [-1,3] 범위에 있는 데이터 개수 출력
print(count_by_range(a,-1,3))[ 예제 2 ] 떡볶이 떡 만들기
문제 설명
오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했습니다. 오늘은 떡볶이 떡을 만드는 날입니다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않습니다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰줍니다.
절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단합니다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않습니다.
예를 들어 높이가 19,14,10,17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15,14,10,15cm가 될 것입니다. 잘린 떡의 길이는 차례대로 4,0,0,2cm입니다. 손님은 6cm만큼의 길이를 가져갑니다.
손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하세요.
n, m = map(int, input().split())
arr = list(map(int, input().split()))
start, result = 0, 0
end = max(arr)
while(start <= end):
sum = 0
mid = (start + end) // 2
for a in arr:
if a > mid:
sum += a - mid
if sum < m:
end = mid - 1
else:
result = mid
start = mid + 1
print(result)[ 예제 2 ] 정렬된 배열에서 특정 수의 개수 구하기
문제 설명
N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다.
이때 이 수열에서 x가 등장하는 횟수를 계산하세요.
예를 들어 수열 {1,1,2,2,2,2,3}이 있을 때 x=2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력한다.
단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 시간 초과 판정을 받습니다.
문제 해결
- 이중 for문 x
- 선형탐색x, 이진탐색으로
from bisect import bisect_left, bisect_right
def countNum(arr, left, right):
right_idx = bisect_right(arr, right)
left_idx = bisect_left(arr, left)
return right_idx - left_idx
n, m = map(int, input().split())
arr = list(map(int, input().split()))
print(countNum(arr, m, m))
