[이코테 / python ]: 이진 탐색 알고리즘 내용 정리 & 문제 풀이 과정 기록

이진탐색 : 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘 

 

 

 

- 시작점, 중간점, 끝점은 인덱스이다.

- 중간점이 2개 존재하는 경우에는 소수점 이하는 제거하여 중간점을 표시할 수 있다.

 

한 단계를 거칠때마다 데이터의 개수가 반씩 줄어든다.

---

💡코딩테스트에서의 이진 탐색

🫱 코딩 테스트에서 이진 탐색 문제는 탐색 범위가 큰 상황에서의 탐색을 가정하는 경우 多

🫱 탐색 범위가 2000만을 넘어가면 이진 탐색으로 접근해보자

🫱 처리해야할 데이터의 개수나 값이 1000만 단위 이상으로 넘어가면 이진 탐색과 같이 0(logN)의 속도를 내야하는 알고리즘을 떠올려야 풀 수 있는 경우가 많다는 것을 기억하자!!!

 

💡빠르게 입력받기

이진탐색은 입력 데이터가 많거나, 탐색 범위가 매우 넓다. 데이터의 개수가 1000만개를 넘어가거나 탐색 범위의 크기가 1000억 이상이라면 이진 탐색 알고리즘을 의심해보자 !! 😎

 

입력 데이터에 대해 어떻게 하고 있나?

input으로만 처리하고 있다면 이렇게 입력 데이터의 개수가 많은 문제에서는 동작 속도가 느려 시간 초과가 나올 수 있다.

 

따라서 입력 데이터가 많은 문제는 sys 라이브러리의 readline()함수를 이용하여 시간 초과를 피할 수 있다.

import sys

# 하나의 문자열 입력 받기
input_data = sys.stdin.readline().rstrip()

print(input_data)

 

- sys 라이브러리를 사용할 때에는 한줄을 입력할 때마다 rstrip() 함수를 꼭 호출해줘야함.

 

이유는 ?

 

소스 코드에 readline()으로 입력하면 입력 후 엔터가 줄바꿈 기호로 입력되는데 이 공백문자를 제거하려면 rstrip() 함수를 사용해야한다.

 

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

 

- bisect_left 로 이진탐색을 수행하면 원소 4가 들어갈 수 있는 첫 번째 위치인 [2]가 반환된다.

- bisect_right 로 이진탐색을 수행하면 원소 4가 들어갈 수 있는 가장 오른쪽 위치인 인덱스[4]가 반환된다.

 

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

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


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))

 

---

파라메트릭 서치

최적화 문제란 가능한 함수의 값을 최대한 낮추거나 최대한 높이는 것을 의미한다.

1️⃣실전문제1 부품 찾기

이진 탐색으로 해결 

 

이진 탐색 기본 형태

def binary_search(array, target, start, end):
  while 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)
  return None

n =  int(input())
n_list = list(map(int,input().split()))
n_list.sort()

m = int(input())
m_list = list(map(int,input().split()))

for target in m_list:
  result = binary_search(n_list,target,0,n)
  if result != None:
    print("yes", end =' ')
  else:
    print("no", end=' ')

 

💡 리스트 생성 후 정렬할 때 주의사항 

// 이렇게 하면 안된다.
n_list = list(map(int,input().split())).sort()

// 이렇게 해야한다.
n_list = list(map(int,input().split()))
n_list.sort()

 

💡어려웠던 점 & 배운 점 

- 이진 탐색을 수행하고 결과를 어떻게 출력해줄 지가 어려웠다.

이진 탐색 함수는 while문을 통해 재귀적으로 호출된다. while의 조건을 벗어나는 경우에 return None을 작성해주고 함수를 종료하면 된다!!

그리고  함수 호출의 결과가 None이 아닌 경우와 None인 경우로 나누어서 처리해주면 된다.

 

- 출력 시 공백을 어떻게 입력하는지에 대해 알게되었다.

print("yes")
print(" ")

// 이렇게 하면 된다!

print("yes", end= ' ')

계수 정렬로 풀어보기

# 계수 정렬로 풀어보기

n = int(input())
array = [0] * 10000001

for i in input().split():
  array[int(i)] = 1

m = int(input())
x = list(map(int,input().split()))

for i in x:
  if(array[i]==1):
    print("yes", end=' ')
  else:
    print("no", end=' ')

 

n_list를 입력하여 그대로 사용하지 않고, 계수 정렬을 통해 해당 값을 1로 업데이트해주면 된다.

 

집합 자료형을 이용해서 풀어보기

n = int(input())
array = set(map(int,input().split()))

m = int(input())
x= list(map(int, input().split()))

for i in x:
  if i in array:
    print("yes", end=' ')
  else:
    print("no", end=' ')

array 출력 형태

💡배운 점

집합 자료형은 set( ) 함수를 통해 만들 수 있다.

단순히 특정 데이터가 존재하는지 검사할 때에 아주 유용하게 쓸 수 있다.

 

또한 set을 통해 집합을 만들면 정렬도 같이 된다!

2️⃣실전 문제 2  : 떡볶이 떡 만들기

# 떡의 개수 n,  요청한 떡의 길이 m
n,m = map(int,input().split())

# 떡의 길이 리스트
rice_cake_list = list(map(int,input().split()))

# 이진 탐색을 위한 시작점 & 끝점
start = 0
end = max(rice_cake_list)

# 절단기 높이를 저장할 변수 
result = 0

# 이진 탐색 반복문 구현
while(start <= end):
  mid = (start + end )//2
  # 잘린 떡의 길이
  total = 0

  for rice_cake in rice_cake_list:
    if mid < rice_cake:
      total += rice_cake-mid

  if total < m:
    end = mid-1
  else:
    result = mid
    start= mid+1

print(result)

---

파라메트릭 서치 유형 

파라메트릭 서치는 최적화 문제를 결정 문제(예 또는 아니오로 답하는 문제) 로 바꾸어 해결하는 기법을 말한다. 

원하는 조건을 만족하는 가장 알맍은 값을 찾는 문제에 주로 사용된다.

 

예를 들어 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면 이진 탐색으로 결정 문제를 해결하면서 범위를 좁힐 수 있다. 코딩 테스트나 프로그래밍 대회에서 보통 파라메트릭 서치 유형은 이진 탐색으로 해결한다.

 

풀이 아이디어

적절한 높이를 찾을 때까지 절단기의 높이 h를 반복해서 조정하는 것이다.그래서 현재 이 높이로 자르면 조건을 만족할 수 있는가? 를 확인 하고 조건의 만족 여부(예 또는 아니오)에 따라 탐색하는 범위를 좁혀나가면 해결할 수 있다.

 범위를 좁혀나갈 때 이진 탐색의 원리를 이용하여 탐색 범위를 절반씩 좁혀나간다.

 

절단기의 높이(탐색 범위)

1부터 10억까지의 정수 중 하나이다. 

 

이렇게 큰 수를 보면 이진 탐색을 떠올리자!!