대기업 코딩테스트 준비 5 : 이진 탐색

ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소스코드 저장소입니다. (github.com)

ndb796/python-for-coding-test

이진 탐색

• 순차 탐색 : 맨 앞에서부터 하나씩 확인
  • 정렬되지 않은 데이터
• 이진 탐색:
  • 정렬된 데이터
  • ​ O(logN)

• 파라메트릭 서치

  • 최적화 문제 > 결정 문제
    • 원하는 조건을 만족하는 가장 알맞은 값 찾기
    • 범위가 어마어마하게 큰 조건

• 떡 썰기

  • 필요한 길이보다 크면 시작점 증가
  • 필요한 길이보다 크면 끝점 감소
    • 중요한 것은 중간점

- 입력이 많으면 sys.stdin.readline()쓰기
  - 엔터가 줄 바꿈 기호로 입력되어 제거
  - 이진 탐색 문제는 입력이 많거나 탐색 범위가 매우 넓음

- set 자료형
  - 특정 자료가 있나 없나 판단에 매우 좋음

# 떡 썰기
# 떡의 개수(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:
            total += x - mid
    # 떡볶이 양이 부족한 경우 더 많이 자르기 (오른쪽 부분 탐색)
    if total < m:
        end = mid - 1
    # 떡볶이 양이 충분한 경우 덜 자르기 (왼쪽 부분 탐색)
    else:
        result = mid # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
        start = mid + 1

# 정답 출력
print(result)

1. 정렬된 배열에서 특정 수의 개수 구하기

1. 바이섹트 라이브러리 활용

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

n, x = map(int, input().split()) # 데이터의 개수 N, 찾고자 하는 값 x 입력 받기
array = list(map(int, input().split())) # 전체 데이터 입력 받기

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

# 값이 x인 원소가 존재하지 않는다면
if count == 0:
    print(-1)
# 값이 x인 원소가 존재한다면
else:
    print(count)        

2. 직접 찾는 함수 만들기

from typing import *


def count_by_value(array: List[int], x):
    # 데이터의 갯수
    n = len(array)
    # X가 처음 등장한 인덱스 계산
    a = first(array, x, 0, n - 1)

    # 수열에 x가 존재하지 않는 경우
    if a is None:
        return 0  # x 0개 0

    # x가 마지막으로 등장한 인덱스 계산
    b = last(array, x, 0, n - 1)

    # 개수를 반환
    return b - a + 1


# 처음 위치를 찾는 이진 탐색 메서드
# 작거나 같으면 왼쪽
def first(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    # 해당 값을 가지고 있는 원소 중에서 가장 왼쪽에 있는 경우에만 인덱스 반환
    # 맨 왼쪽이거나, mid 전 인덱스 원소가 target보다 작다 (커져서 target).
    if (mid == 0 or target > array[mid - 1]) and array[mid] == target:
        return mid
    # 중간점의 값 보다 찾는 값이 작거나 같으면 왼쪽을 찾는다.
    elif array[mid] >= target:
        return first(array, target, start, mid - 1)
    # 중간점의 값 보다 찾는 값이 크면 오른쪽을 찾는다.
    else:
        return first(array, target, mid + 1, end)


# 마지막 위치를 찾는 이진 탐색 메서드
# 크거나 같으면 오른쪽
def last(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    # 해당 값을 가지고 있는 원소 중에서 가장 오른쪽에 있는 경우에만 인덱스 반환
    # 맨 왼쪽이거나, mid 다음 인덱스 원소가 target보다 크다 (오름차순).
    if (mid == len(array) - 1 or target < array[mid + 1]) and array[mid] == target:
        return mid
    # 중간점의 값 보다 찾는 값이 작은경우 왼쪽 확인
    elif array[mid] > target:
        return last(array, target, start, mid - 1)
    # 중간점의 값 보다 찾는 값이 크거나 같으면 오른쪽을 찾는다.
    else:
        return last(array, target, mid + 1, end)


n, x = map(int, input().split())  # 데이터의 개수 N, 찾고자 하는 값 x 입력 받기
arr = list(map(int, input().split()))  # 전체 데이터 입력 받기

# 값이 x인 데이터의 개수 계산
count = count_by_value(arr, x)

# 값이 x인 원소가 존재하지 않는다면
if count == 0:
    print(-1)
# 값이 x인 원소가 존재한다면
else:
    print(count)

2.고정점 찾기

• 수열의 원소 중 그 값이 인덱스와 동일한 원소
• 이진 탐색은 찾고자 하는 값이 중앙점과 같다고 두고 수행

# 이진 탐색 소스코드 구현(재귀 함수)
def binary_search(array, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    # 고정점을 찾은 경우 인덱스 반환
    if array[mid] == mid:
        return mid
    # 중간점이 가리키는 값보다 중간점이 작은 경우 왼쪽 확인
    elif array[mid] > mid:
        return binary_search(array, start, mid - 1)
    # 중간점이 가리키는 값보다 중간점이 큰 경우 오른쪽 확인
    else:
        return binary_search(array, mid + 1, end)

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

# 이진 탐색(Binary Search) 수행
index = binary_search(array, 0, n - 1)

# 고정점이 없는 경우 -1 출력
if index == None:
    print(-1)
# 고정점이 있는 경우 해당 인덱스 출력
else:
    print(index)

3. 공유기 설치

• 파라메트릭 서치
• 첫째 집에는 반드시 공유기를 설치한다고 가정하자.

# 집의 개수(N)와 공유기의 개수(C)를 입력 받기
n, c = list(map(int, input().split(' ')))

# 전체 집의 좌표 정보를 입력 받기
array = []
for _ in range(n):
     array.append(int(input()))
array.sort() # 이진 탐색 수행을 위해 정렬 수행

start = 1 # 가능한 최소 거리(min gap)
end = array[-1] - array[0] # 가능한 최대 거리(max gap)
result = 0

while(start <= end):
    mid = (start + end) // 2 # mid는 가장 인접한 두 공유기 사이의 거리(gap)을 의미
    # 첫째 집에는 무조건 공유기를 설치한다고 가정
    value = array[0]
    count = 1
    # 현재의 mid 값을 이용해 공유기를 설치하기
    for i in range(1, n): # 앞에서부터 차근차근 설치 
        if array[i] >= value + mid:
            value = array[i]
            count += 1
    if count >= c: # C개 이상의 공유기를 설치할 수 있는 경우, 거리를 증가시키기
        start = mid + 1
        result = mid # 최적의 결과를 저장
    else: # C개 이상의 공유기를 설치할 수 없는 경우, 거리를 감소시키기
        end = mid - 1

print(result)

4. 가사 검색

• 각 단어를 길이에 따라서 나눈다.
• 모든 리스트를 정렬한 뒤 각 쿼리에 대해 이진탐색을 수행한다.
• fro??
• 5글자 리스트
  • fro로 시작하는 첫 단어
  • fro로 시작하는 마지막 단어
  • 두 위치 차이 계산
• 접두사 ??
  • 뒤집은 배열을 유지한다.

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

# 모든 단어들을 길이마다 나누어서 저장하기 위한 리스트
array = [[] for _ in range(10001)]
# 모든 단어들을 길이마다 나누어서 뒤집어 저장하기 위한 리스트
reversed_array = [[] for _ in range(10001)]

def solution(words, queries):
    answer = []
    for word in words: # 모든 단어를 접미사 와일드카드 배열, 접두사 와일드카드 배열에 각각 삽입
        array[len(word)].append(word) # 단어를 삽입
        reversed_array[len(word)].append(word[::-1]) # 단어를 뒤집어서 삽입

    for i in range(10001): # 이진 탐색을 수행하기 위해 각 단어 리스트 정렬 수행
        array[i].sort()
        reversed_array[i].sort()

    for q in queries: # 쿼리를 하나씩 확인하며 처리
        if q[0] != '?': # 접미사에 와일드 카드가 붙은 경우
            res = count_by_range(array[len(q)], q.replace('?', 'a'), q.replace('?', 'z'))
        else: # 접두사에 와일드 카드가 붙은 경우
            res = count_by_range(reversed_array[len(q)], q[::-1].replace('?', 'a'), q[::-1].replace('?', 'z'))
        # 검색된 단어의 개수를 저장
        answer.append(res)
    return answer