나동빈님의 책과 유튜브 강의인 '이것이 코딩 테스트다'를 바탕으로 스스로 공부한 내용을 정리한 글입니다.
참고한 영상의 링크는 아래와 같습니다.
이것이 코딩테스트다 - 이진탐색 알고리즘
순차탐색
- 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다.
- 일반적으로 정렬되지 않는 데이터를 찾아야할 때 사용되며, 리스트 자료형에서 count() 메서드를 이용할 때에 내부에서는 순차 탐색이 수행되곤 한다.
input_data = input().split()
n = int(input_data[0])
target = str(input_data[1])
array = input().split()
def sequential_search(n, target, array):
for i in range(n):
if array[i] == target:
return i + 1
return None
print(sequential_search(n, target, array))- 앞에서부터 순차적으로 탐색하기 때문에 O(N)의 시간 복잡도를 가지고 있다.
이진탐색
- 데이터가 정렬되어 있다고 가정하고 사용하는 알고리즘
- 리스트의 시작, 끝, 중간을 안다고 할때, 찾으려는 데이터와 중간에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는게 이진 탐색 과정이다.
n, target = list(map(int, input().split()))
array = list(map(int, input().split()))
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)
result = binary_search(array, target, 0, n - 1)
if result == None:
print("No 원소")
else:
print(result + 1)
- 리스트가 정렬되어 있다는 가정하여 target과 중간점을 비교하여 데이터를
- (1) 중간점과 같으면 return (2) 중간점과 큰 데이터들과 비교를 지속할지 (3) 중간점보다 작은 데이터들과 비교를 지속할지를 결정한다.
- 재귀함수를 통해 logN의 시간복잡도를 보장해준다.
python의 bisect library 활용해서 값이 특정 범위에 속하는 데이터 개수 구하기
from bisect import bisect_left, bisect_right
def count_by_range(a, left_value, right_value):
# 정렬된 순서를 유지한 채 배열 a에 x를 삽입할 가장 오른쪽 idx 반환
right_index = bisect_right(a, right_value)
# 정렬된 순서를 유지한 채 배열 a에 x를 삽입할 가장 왼쪽 idx 반환
left_index = bisect_left(a, left_value)
return right_index - left_index
a = [1,2,3,3,3,3,4,4,8,9]
print(count_by_range(a,4,4))parametric search
- 최적화 문제를 결정문제로 바꾸어 해결하는 기법
- 예시: 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
실전문제 1
- 입력조건: 첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어진다.
- 둘째 줄에는 떡의 개별 높이가 주어진자. 떡 높이는 총합은 항상 M 이상이므로, 손님은 필요한 양만큼 떡을 사갈 . 수있다. 높이는 10억보다 작거나 같은 양의 정수 또는 0이다.
n, target = list(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 < target:
# mid 기준으로 모든 합이 target보다 적으면 mid가 크다는 의미 > mid를 감소
end = mid - 1
else:
# mid 기준으로 모든 합이 target보다 크거나 같다
# 현재 mid가 가장 좋은 point가 될 수 있지만 증가 가능성 있음 > mid를 증가
result = mid
start = mid + 1
print(result)
실전문제 2
- 입력조건: 첫째 줄에 N과 x가 정수 형태로 공백으로 구분되어 입력됩니다.
- 둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력됩니다.
- 출력조건: 수열의 원소 중에서 값이 x인 원소의 개수를 출력합니다. 단 값이 x인 원소가 하나도 없다면 -1을 출력합니다.
from bisect import bisect_left, bisect_right
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
n,x = list(map(int, input().split()))
array = list(map(int, input().split()))
count = count_by_range(array, x, x)
if count == 0:
print(-1)
else:
print(count)이 문제의 KEY는 일반적인 선형탐색을 하면, 시간초과판정을 받기 때문에 O(LogN)으로 탐색으로 수행하는 이진탐색 알고리즘을 사용해야 한다라는 제한조건이 존재한다.
