📚 <이것이 코딩 테스트다> - 이진탐색

참고자료 : 이것이 코딩 테스트다 (나동빈 저)

1. 범위를 반씩 좁혀가는 탐색

순차탐색

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

def seq_search(n, target, array):
    for i in range(n):
        if array[i] == target:
            return i+1

input_data = input().split()
n = int(input_data[0])
target = input_data[1]
array = input().split()

print(seq_search(n, target, array))

데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 순차 탐색의 시간복잡도는 O(N)이다.

이진탐색

이진 탐색은 배열 내부의 데이터가 정렬되어 있을 때 범위를 절반씩 좁혀가며 데이터를 탐색하는 알고리즘
이미 정렬되어 있는 경우 매우 빠르게 데이터를 찾을 수 있다.
위치를 나타내는 변수 3개 시작점 끝점 중간점 을 사용한다.
시간복잡도 O(logN)

재귀를 사용한 코드

def bin_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 bin_search(array, target, start, mid-1)
    else :
        return bin_search(array, target, mid+1, end)

반복문을 사용한 코드

def bin_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2

        if array[mid] == target: return mid
        elif array[mid] > target : 
            end = mid - 1
        else :
            start = mid + 1

    return None

코테에서의 이진탐색

여러 차례 코드를 입력하며 자연스럽게 외우자! 중요중요~
탐색 범위가 클 때는 이진탐색으로 접근하자.

트리 자료구조

트리 자료구조는 노드와 노드의 연결로 표현하며 많은 양의 데이터를 관리하기 위한 목적으로 사용된다.
트리는 일부를 떼어내도 트리 구조이며 이를 서브 트리라 한다.

이진 탐색트리

트리 자료구조 중에서 가장 간단한 형태가 이진 탐색 트리이다.
이진 탐색 트리 : 이진 탐색이 동작할 수 있도록 고안된, 효율적 탐색이 가능한 자료구조

부모 노드보다 왼쪽 자식 노드가 작다.
부모 노드보다 오른쪽 자식 노드가 크다

빠르게 입력받기

Python input() 함수는 동작 속도가 느리다.
한 줄 입력받고 rstrip() 함수를 꼭 호출해야 한다.

import sys

input_data = sys.stdin.readline().rstrip()
print(input_data)

2. 부품찾기

난이도 중하

문제

전자 매장에는 부품이 N개 있고 각 부품에는 정수 형태의 고유번호가 있다. 어는 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자.

해설

먼저 매장 내 N개의 부품을 번호를 기준으로 정렬하고 M개의 부품을 각각 이진탐색을 수행한다.

코드

def bin_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None

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

    for i in x :
        result = bin_search(array, i, 0, n-1)
        if result != None : print('yes', end=' ')
        else : print('no', end=' ')

계수 정렬을 사용할 수 있다

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

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

3. 떡볶이 떡 만들기

난이도 중

문제

동빈이네 떡볶이 떡은 떡의 길이가 일정하지 않고 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다. 절다기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이 H보다 긴 떡은 잘리고, 낮은 떡은 잘리지 않는다. 손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

해설

전형적인 이진 탐색 문제이자, 파라메트릭 서치유형이다. 파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다. 이 문제의 풀이 아이디어는 의외로 간단한데 적절한 높이를 찾을 때까지 절단기의 높이 H를 반복해서 조정하는 것이다.

코드

n, m = 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
        start = mid + 1

print(result)