[코딩테스트] 이진 탐색 알고리즘

순차 탐색 : 리스트 안에 있는 특정 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법

이진 탐색 : 정렬되어 있는 리스트에서, 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법으로 시작점/끝점/중간점을 이용해서 탐색 범위를 명시해주어야 한다.

 

이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾는다면,

1.

array = [0,2,4,6,8,10,12,14,16,18]

시작점:array[0]=0, 끝점:array[9]=18, 중간점:array[4]=8(소수점 이하 제거)

찾고자 하는 4가 중간점인 8보다 작다. 그러므로 중간점을 포함하여 오른쪽 부분은 필요가 없으므로 날려보자.

2.

array = [0,2,4,6]

시작점:array[0]=0, 끝점:array[3]=6, 중간점:array[1]=2(소수점 이하 제거)

중간점인 2보다 4가 크다. 그러므로 중간점을 포함하여 왼쪽 부분을 삭제한다.

3.

array = [4,6]

시작점:array[2]=4, 끝점:array[3]=6, 중간점:array[2]=4

우리가 찾고자 하는 값인 4는 array[2]에 존재함을 확인할 수 있다.

 

이진 탐색의 시간 복잡도

단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log₂N에 비례한다.

한번 스텝을 반복할 때마다, 이상적인 경우 절반 정도로 줄어들기 때문이다.

즉, 이진 탐색은 탐색 범위를 절반씩 줄인다.

시간 복잡도 = O(logN)을 보장

 

파이썬 코드

#재귀적 구현
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)

#반복문 구현
def binary_search(array, target, start, end):
	while start <=end:
    	mid = (start+end)//2
        if array[mid] == target:
        	return mid
        elif array[mid] > target: #중간점 값보다 target값이 작다면 왼쪽 확인
        	end = mid-1
		else: #중간점 값보다 target값이 크다면 오른쪽 확인
        	start = mid + 1
    return None
    
#-------구현부-------#
n, target = list(map(int, input().split())) # n(원소의 개수)과 target(찾고자 하는 값)을 입력받기
array = list(map(int, input().split())) #전체 원소 입력받기

result = binary_search(array, target, 0, n-1)
if result == None:
	print("원소가 존재하지 않습니다.")
else:
	print(result+1)

파이썬 이진 탐색 라이브러리

from bisect import bisect_left, bisect_right

bisect_left(a,x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환

bisect_right(a,x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환

*왼쪽, 오른쪽은 동일한 값이 있을 때 x를 어떻게 넣을지를 결정하는 것.

 

값이 특정 범위에 속하는 데이터 개수 구하기

bisect_left, bisect_right를 이용해서 가져온 인덱스를 이용해서

left_value와 right_value 사이에 있는 데이터 개수를 출력하도록 만들 수 있다.

 

파라메트릭 서치(Parametric Search)

최적화 문제를 결정문제(Yes or No)로 바꾸어 해결하는 기법.

최적화 문제란, 어떤 함수의 값을 가능한 낮추거나,최대한 높이거나 하는 등의 문제이다.

이러한 최적화 문제를 바로 해결하기 어려울 때, 그 문제를 여러 번의 결정문제로 바꾸어서 해결할 수 있다.

특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제가 나온다면, 탐색 범위를 좁혀가면서 현재 범위에서 이 조건을 만족하는지? 확인해볼 수 있을 것이다.

코딩 테스트에서 파라메트릭 서치 문제가 나오면 이진 탐색을 이용하자.

 

문제 1. 떡볶이 떡 만들기

떡볶이 떡의 길이는 일정하지 않지만, 한 봉지 않에 들어가는 떡의 총 길이는 맞춰준다.

 

절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다.

높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, H보다 낮다면 잘리지 않는다.

 

예를 들어, 떡의 높이가 19, 14, 10, 17cm이고 절단기 높이(H)가 15cm라면,

자른 뒤 떡의 높이 = 15, 14, 10, 15cm

잘린 떡의 길이 = 4, 0, 0, 2cm

손님이 가져가는 길이 = 6cm

 

손님이 요청한 총 길이가 M일 때, 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성해보자.

 

문제 풀이

'현재 이 높이로 자르면 조건을 만족할 수 있는가?'를 확인해서, 조건의 만족 여부(Yes or No)에 따라서 탐색 범위를 좁혀서 해결할 수 있다.

절단기의 높이가 0부터 10억까지인데, 이렇게 큰 탐색 범위를 보면 시간을 줄이기 위해 이진 탐색이 필수이다.

1. 시작점 :0, 끝점:19, 중간점:9

중간점인 9로 자르면, 잘린 떡의 길이는 10,6,1,8로 손님이 요구하는 떡의 길이 6보다 기니까 결과를 저장하고

높이를 더 증가(오른쪽으로 이동)시켜 본다.

2. 시작점 :10, 끝점: 19, 중간점: 14

중간점인 14로 자르면, 잘린 떡의 길이는 5,1,0,3으로 손님이 요구하는 떡의 길이 6보다 기니까 결과를 저장한다.

높이를 더 증가(오른쪽으로 이동)시켜 본다.

3. 시작점 15, 끝점 19, 중간점 17

중간점인 17로 자르면, 잘린 떡의 길이는 2로 손님이 요구하는 떡의 길이 6보다 짧으므로

왼쪽으로 좀 더 이동해야 한다.

4. 시작점 15, 끝점 16, 중간점 15

15로 자르면 잘린 떡의 길이는 4,2로 손님이 요구하는 떡의 길이 6으로  현재의 높이값을 기록한다.

 

더이상 탐색 범위를 바꾸지 못할 때까지 높이값을 바꾸어서 조건을 만족하는지 체크하는 방식으로 해결한다.

필요한 떡의 크기 이상이라면 결과를 저장하여, 최적의 높이값을 얻는다.

 

중간점의 값은 시간이 지날수록 '최적화된 값'이 되기 때문에, 과정을 반복하면서 얻을 수 있는 떡의 길이 합이 필요한 떡의 길이보다 크거나 같을 때마다 중간점의 값을 기록하면 된다.

 

 

 

n,m = list(map(int,input().split(' '))) #떡의 개수 N과 요청한 떡의 길이 M을 입력
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에 담기
        	total += x-mid
    if total < m : #떡의 양이 부족하다면, 더 많이 자르기(왼쪽 부분을 탐색)
    	end = mid-1
    else: #떡의 양이 충분하다면, 덜 자르기(오른쪽 부분을 탐색)
    	result = mid #최대한 덜 잘랐을 때가 정답이므로 여기서 result에 기록
        start = mid+1 

print(result)

문제 2. 정렬된 배열에서 특정 수의 개수 구하기

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있다고 하자. 이 수열에서 x가 등장하는 횟수를 계산하라. 단, 시간복잡도 O(logN)으로 알고리즘을 설계하지 않으면 시간 초과 판정을 받는다.

 

풀이

일반적인 선형탐색으로는 시간 초과 판정을 받는다.

하지만 데이터가 정렬되어 있으므로 이진 탐색을 수행할 수 있다.

첫 위치를 찾는 이진 탐색과, 마지막 위치를 찾는 이진 탐색을 두 번 수행하면 된다.

bisect 라이브러리를 이용해서 간단히 구해보자.

 

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 = map(int, input().split()) 
array = list(map(int, input().split()))

#값이 [x,x]범위에 있는 데이터의 개수 계산
count = count_by_range(array, x,x)

#값이 x인 원소가 존재하지 않으면 -1을 프린트
if count ==0:
	print(-1)
else:
	print(count)

코딩테스트 준비하기

2023.01.25 - [Data Science] - [코딩테스트] 정렬 알고리즘 비교 및 기초 예제

2023.01.24 - [Data Science] - [코딩테스트] 정렬 알고리즘(2) 퀵 정렬 계수 정렬

2023.01.24 - [Data Science] - [코딩테스트] 정렬 알고리즘(1) 선택 정렬과 삽입 정렬

2023.01.24 - [Data Science] - [코딩테스트] DFS BFS 문제 풀이 실습

2023.01.23 - [Data Science] - [코딩 테스트] DFS BFS 개념 - 스택 큐 자료구조 재귀함수 기초

2022.12.24 - [Data Science] - [코딩테스트] 구현, 시뮬레이션과 완전 탐색

2022.12.23 - [Data Science] - [코딩테스트] 그리디 알고리즘(Greedy), 탐욕법

 

 

 

https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC *내용에 대한 모든 저작권은 해당 영상의 원저작자에게 있습니다.