이분탐색 및 투포인터

✨ 매개변수 탐색 문제는 보통 mid를 구하고자 하는 값으로 설정한다!
left < right, left = mid + 1, right = mid

1️⃣ 개념

이분탐색

정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법 → 2중 for문 쓰면 시간초과가 날 경우

1. 배열 전체의 중간값을 target과 비교
2. 중간값이 target보다 크면 왼쪽 부분만 선택
3. 왼쪽 부분의 중간값을 다시 target과 비교

list.sort()   # 리스트 오름차순 정렬
left = 0
right = len(list) - 1

while left <= right:
	mid = (left + right) // 2   # 배열의 중간값 구하기 
    
    # 중간값이 target이면 끝
    if list[mid] == target:
    	print(mid + 1)
        break
    
    # 중간값이 target보다 크면 왼쪽 부분 선택
    elif list[mid] > target:
    	right = mid - 1
    
    # 중간값이 target보다 작으면 오른쪽 부분 선택
    else:
    	left = mid + 1

2️⃣ 파이썬 라이브러리

• bisect_left(list, data) - 리스트에 데이터를 삽입할 가장 왼쪽 인덱스를 찾는 함수
• bisect_right(list, data) - 리스트에 데이터를 삽입할 가장 오른쪽 인덱스를 찾는 함수

from bisect import bisect_left, bisect_right

a = [1, 2, 3, 4, 5]   # ⭐️정렬된 리스트에서 사용
print(bisect_left(a, 3))  # 2 
print(bisect_right(a, 3))  # 3 


# ⭐️리스트 안에 있는 특정 숫자의 개수 구하기
print(bisect_right(a, x) - bisect_left(a, x))

3️⃣ 문제 풀이

* 투포인터를 사용해 4개 고르기

for i in range(n):
	for j in range(i+3, n):
    	left, right = i+1, j-1
        
        while left < right:
        	if temp < 0:
            	right -= 1
            else:
            	left += 1

* 연속된 부분 수열의 합 (Level 2)

https://school.programmers.co.kr/learn/courses/30/lessons/178870

def solution(sequence, k):
    n = len(sequence)
    answer = [0, n]
    left, right = 0, 0
    cur = sequence[0]

    while right < n:
        if cur <= k:
            if cur == k and (right - left) < (answer[1] - answer[0]):
                answer = [left, right]
            right += 1
    		
            # 아래 조건 없이 while문 조건을 right < n-1로 설정하면,
            # 마지막 경우 때 정답 갱신 안함
            if right < n:
                cur += sequence[right]
        else:
            cur -= sequence[left]
            left += 1
    
    return answer

* 백준 공유기 설치 (🥇4) -> 매개변수 탐색

https://www.acmicpc.net/problem/2110

집 N개가 (x1, x2, ..., xn) 좌표 위 수직선 위에 있다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로
​

left, right = 1, arr[n-1]-arr[0]   # 집 사이의 최소⭐️, 최대 거리
answer = 0

while left < right:
	mid = (left + right) // 2   # 인접한 두 공유기 사이의 거리 

    cnt = 1   # 공유기 설치한 집 개수 
    ts = arr[0]   # 시작점은 무조건 설치

    for i in range(n):
    	if arr[i] - ts >= mid:  
        	cnt += 1
        ts = arr[i]

    if cnt >= c:  
    	answer = mid
        left = mid + 1   # 더 큰 거리 시도해보기 
    else:   # 조건 충족 못함 -> 공유기 간격 좁혀야 함 
        right = mid

​

매개변수 탐색 문제는 left, right 값을 가능한 최소값, 최대값으로 초기화하는듯
​
+) 프로그래머스 입국심사
https://school.programmers.co.kr/learn/courses/30/lessons/43238
n명이 입국심사를 위해 줄을 서서 기다리고 있다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간이 다르다.
모든 사람이 심사를 받는데 걸리는 시간의 최소값은?

# mid 시간 동안 심사할 수 있는 사람 수 cnt 구하기 
# times는 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열
# A 심사대에서는 a명 심사 가능 + B 심사대에서는 b명 심사 가능 + ...
for i in range(len(times)):
	cnt += (mid // times[i])