이진 탐색 알고리즘
순차 탐색
- 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법
이진 탐색
-
정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
-
이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다.
이진 탐색 동작 예시
값이 4인 원소를 찾기
-
시작점: 0, 끝점: 9, 중간점: 4 (소수점 이하 제거)
중간점 값과 찾고자하는 값 비교하여 중간점 값이 더 크다면 중간점~오른쪽 끝은 확인할 필요가 없다. 끝점을 중간점 앞으로 옮긴다. -
시작점: 0, 끝점: 3, 중간점: 1 (소수점 이하 제거)
중간점 값과 찾고자하는 값 비교하여 중간점 값이 더 작다면 중간점~왼쪽 끝은 확인할 필요가 없다. 시작점을 중간점 뒤로 옮긴다. -
시작점:2, 끝점:3, 중간점: 2 (소수점 이하 제거)
시작점에서 찾고자하는 값을 찾았으므로 탐색을 끝낸다.
이진 탐색의 시간 복잡도
-
단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log2N에 비례함.
-
예를 들어 초기 데이터 개수가 32개일 때
1단계를 거치면 16개 가량의 데이터만 남는다.
2단계를 거치면 8개 가량의 데이터만 남는다.
3단계를 거치면 4개 가량의 데이터만 남는다. -
즉 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 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 ) #시작점을 중간점 오른쪽으로 옮긴다, 다시 탐색을 수행
# n( 원소의 개수 )과 target( 찾고자 하는 값 )을 입력 받기
n, target = list( map( int, input(). split() ) ) # 10 7
# 전체 원소 입력 받기
array = list( map( int, input(). split() ) ) # 1 3 5 7 9 11 13 15 17 19
#이진 탐색 수행 결과 출력
result = binary_search( array, target, 0, n -1 )
if result == None: #아무것도 찾지 못했다
print( "원소가 존재하지 않습니다." )
else:
print( result +1 ) #해당 원소에 1을 더해서 몇번째 원소인지 찾는다 (출력) 4
이진 탐색 반복문 구현
#이진 탐색 소스코드 구현 (반복문)
def binary_serach( array, target, start, end ):
while start <=end:
mid = (start + end) // 2 #중간점 찾는다
#찾은 경우 중간점 인덱스 반환
if array[ mid ] == target:
return mid
#중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
elif array[ mid ] > target:
end = mid -1 #끝점을 중간값보다 1작게 한다
#중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
else:
start = mid + 1 #시작점을 중간값보다 1크게 한다
return None
# n( 원소의 개수 )과 target( 찾고자 하는 값 )을 입력 받기
n, target = list( map( int, input() .split() ) ) #10 7
#전체 원소 입력 받기
array = list( map( int, input() .split() ) ) # 1 3 5 6 9 11 13 15 17 19
#이진 탐색 수행 결과 출력
result = binary_search( array, target, 0, n-1 )
if result == None:
print("원소가 존재하지 않습니다.")
else:
print( result + 1 ) python 이진 탐색 라이브러리
- bisect_left( a, x ): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환
- bisect_right( a, x ): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환
from bisect import bisect_left, bisect_right
a = [1, 2, 4, 4, 8]
x = 4
print( bisect_left( a, x ) ) #출력 2
print( bisect_right( a, x ) ) #출력 4# 값이 특정 범위에 속하는 데이터 개수 구하기
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) ) # 출력 2
#값이 [-1, 3] 범위에 있는 데이터 개수 출력
print( count_by_range( a, -1, 3) ) # 출력6파라메트릭 서치 (Parametric Search)
- 최적화 문제(어떤 함수의 값을 가능한 낮추거나 최대한 높이거나 하는 문제)를 결정 문제(예 혹은 아니오) 로 바꾸어 해결하는 기법
- ex) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
- 일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있음.
문제 : 떡볶이 떡 만들기
문제 설명
오늘 식초는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 식초네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다.
절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다.
예를 들어 높이가 19, 14, 10, 17cm 인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2 cm이다. 손님은 6cm만큼의 길이를 가져간다.
손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.
문제 조건
난이도 3 | 풀이 시간 40분 | 시간제한 2초 | 메모리 제한 128MB
입력 조건
첫째줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어집니다. (1 <=N <=1,000,000, 1 <=M <=2,000,000,000 )
둘째줄에 떡의 개별 높이가 주어진다. 떡 높이의 총합은 항상 M 이상이므로, 손님은 필요한 양만큼 떡을 사갈 수 있다.
높이는 10억보다 작거나 같은 양의 정수 또는 0이다.
출력 조건
적어도 M 만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.
문제 해결 아이디어
적절한 높이를 찾을 때까지 이진 탐색을 수행하여 높이 H를 반복해서 조정하면 된다. (H 높으면 잘리는 값 줄어든다.)
"현재 이 높이로 자르면 조건을 만족할 수 있는가?"를확인한 뒤에 조건의 만족 여부 (예 혹은 아니오)에 따라서 탐색 범의를 좁혀서 해결할 수 있다.
절단기의 높이는 0부터 10억까지의 정수 중 하나이다.
이렇게 큰 탐색 범위를 보면 가장 먼저 이진 탐색을 떠올려야 한다.
- 시작점: 0, 끝점:19, 중간점: 9(=H, 자르는 높이)
이때 필요한 떡의 크기: M=6이므로, 잘린 떡의 길이 25는 최소한을 만족한다. 결과 저장
시작점을 중간점 뒤로 옮긴다.
- 시작점: 10, 끝점: 19, 중간점: 14(=H, 자르는 높이)
이때 필요한 떡의 크기: M=6이므로, 잘린 떡의 길이 9는 최소한을 만족한다. 결과 저장
시작점을 중간점 뒤로 옮긴다. (중간점+1)
- 시작점: 15, 끝점: 19, 중간점: 17(=H, 자르는 높이)
이때 필요한 떡의 크기: M=6이므로, 잘린 떡의 길이 2는 최소한을 만족 하지 못한다. 결과 저장하지 않음
끝점을 중간점 앞으로 옮긴다.(중간점 -1)
- 시작점: 15, 끝점: 16, 중간점: 15
이때 필요한 떡의 크기: M=6이므로, 잘린 떡의 길이 6은 손님이 원하는 길이를 만족한다. 결과 저장
이진탐색을 사용해서 더이상 탐색범위를 줄어들지 못하게 할때까지 시작점과 끝점을 바꾸면서, H(=중간점)을 매번 바꾸어보며 현재 높이로 잘랐을 때 조건을 만족하는지 체크하는 방법으로 최적의 해를 구한다.
중간점의 값은 시간이 지날수록 최적화된 값이 되기 때문에, 과정을 반복하면서 얻을 수 있는 떡의 길이 합이 필요한 떡의 길이(=M)보다 크거나 같을 때마다 중간점의 값을 기록하면 된다.
코드
#떡의 개수(N)와 요청한 떡의 길이(M)을 입력
n, m = 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: #현재 떡의 길이(x)가 높이보다 클 때
total += x - mid #잘린 부분의 떡을 total 변수에 담는다.
#떡의 양이 부족한 경우 더 많이 자르기 (왼쪽 부분 탐색)
if total < m:
end = mid -1 #끝점이 중간점 앞으로 이동
#떡의 양이 충분한 경우 덜 자르기 (오른쪽 부분 탐색)
else:
result = mid #최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
start = mid + 1 #시작점을 중간점 뒤로 이동
#정답 출력
print( result )문제: 정렬된 배열에서 특정 수의 개수 구하기
문제 설명
N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하시오. 예를 들어 수열 {1, 1, 2, 2, 2, 2, 3}이 있을 때 x=2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력한다.
단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 시간 초과 판정을 받는다.
문제 조건
난이도 2 | 풀이 시간: 30분 | 시간 제한: 1초 | 메모리 제한: 128MB | 기출: Zoho 인터뷰
입력 조건
첫째 줄에 N과 x가 정수 형태로 공백으로 구분되어 입력된다.
(1 <= N<=1,000,000), (-109 <= x <=109 )
둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력된다.
출력 조건
수열의 원소 중에서 값이 x인 원소의 개수를 출력한다. 단, 값이 x인 원소가 하나도 없다면 -1을 출력한다.
문제 해결 아이디어
시간 복잡도 O(logN)으로 동작하는 알고리즘을 요구하고 있다.
일반적인 선형 탐색(Linear Search)로는 시간 초과 판정 받는다.
하지만 데이터가 정렬되어 있기 때문에 이진 탐색을 수행할 수 있다.
특정 값(x)이 등장하는 첫 번째 위치와 마지막 위치를 찾아 위치 차이를 계산해 문제를 해결할 수 있다.
전체 탐색 범위에 대해서 이진 탐색 2번 수행한다. 첫 위치, 마지막 위치를 찾게 만든다
방법 : 이진탐색 직접 구현 or 표준 라이브러리로 구현
코드
from bisect import bisect_left, bisect_right
#값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range( array, left_value, right_value ):
right_index = bisect_right( array, right_value )
left_index = bisect_left( array, left_value )
return right_index - left_index #left_value 이상 right_value 이하
n, x = map( int, input() .split( )) #데이터의 개수 N, 찾고자 하는 값 x 입력받기
array = list( map( int, input() .split( ))) #전체 데이터 입력받기
#값이 [x, x] 범위에 있는 데이터의 개수 계산 = x의 개수를 세면 되기 때문
count = count_by_range( array, x, x )
#값이 x인 원소가 존재하지 않는다면
if count == 0:
print(-1)
#값이 x인 원소가 존재한다면
else:
print( count )메모
count_by_range( )
