이것이 취업을 위한 코딩 테스트다 CHAPTER 07 이진 탐색

순차 탐색

• 데이터 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인하는 방법
• 데이터 개수가 N개일 때 최대 N번의 비교 연산이 필요
• 최악의 경우 시간 복잡도 O(N)
• count() 메서드를 이용할 때 내부에서 순차 탐색이 수행

 

이진 탐색

• 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 방법
• 배열 내부의 데이터가 정렬되어 있어야 함
• 시간 복잡도 O(logN)
• 탐색 범위가 큰 상황에서 탐색을 가정하는 문제
  • N이 1000만 단위 이상 or 탐색 범위가 1000억 이상

# 반복문
def binary_search(array,target,s,e):
    while s <= e:
        mid = (s+e)//2
        # 찾았다?
        if array[mid] == target:
            return mid
        # 중간점의 값이 찾고자 하는 값보다 큰 경우
        elif array[mid] > target:
            # 절반 중 왼쪽 부분 확인
            e = mid - 1
        # 중간점의 값이 찾고자 하는 값보다 작은 경우
        elif array[mid] < target:
            # 절반 중 오른쪽 부분 확인
            s = mid + 1

# 재귀
def binary_search(array,target,s,e):
    if s > e:
        return 
    mid = (s+e)//2
    # 찾았다?
    if array[mid] == target:
        return mid
    # 중간점의 값이 찾고자 하는 값보다 큰 경우
    elif array[mid] > target:
        # 절반 중 왼쪽 부분 확인
        return binary_search(array,target,s,mid-1)
    # 중간점의 값이 찾고자 하는 값보다 작은 경우
    elif array[mid] < target:
        # 절반 중 오른쪽 부분 확인
        return binary_search(array,target,mid+1,e)

 

이진 탐색 트리

• 이진 탐색이 동작 할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조
• 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

 

문제1

부품 찾기

• 풀이1
  • 순차탐색으로 하나하나 비교하면 N*M이 최대 1000억이므로 이진 탐색 
  • flag가 True로 바뀌면 부품이 존재 / False이면 부품이 존재X
• 코드1

import sys
input = sys.stdin.readline

# 전체 부품 수
N = int(input())
# 전체 부품
all_num = list(map(int,input().split()))
# 이진 탐색을 위해 정렬
all_num.sort()

# 손님이 원하는 부품 수
M = int(input())
# 손님이 원하는 부품 번호
want_num = list(map(int,input().split()))

# 손님이 원하는 부품 있는지 하나씩 확인
for n in want_num:
    flag = False
    s = 0
    e = N-1
    while s <= e:
        mid = (s+e)//2
        # 찾았다?
        if all_num[mid] == n:
            flag = True
            break
        # 작아? -> 왼쪽확인
        elif all_num[mid] > n:
            e = mid -1
        # 커? -> 오른쪽 확인
        elif all_num[mid] < n:
            s = mid  + 1
    # 찾았다?
    if flag:
        print('yes',end=' ')
    else:
        print('no',end=' ')

• 풀이2
  • 부품이 있는지 없는지 유무만 물었으므로 in 연산자를 사용
• 코드2

import sys
input = sys.stdin.readline

# 전체 부품 수
N = int(input())
# 전체 부품 - 중복 제거
all_num = set(list(map(int,input().split())))

# 손님이 원하는 부품 수
M = int(input())
# 손님이 원하는 부품 번호
want_num = list(map(int,input().split()))

for n in want_num:
    # 부품이 있는가?
    if n in all_num:
        print('yes',end=' ')
    # 부품이 없는가?
    else:
        print('no',end=' ')

 

문제2

떡볶이 떡 만들기

• 풀이
  • 떡의 최대 길이가 10억이므로 순차탐색 시 시간 초과
  • 가장 긴 떡 길이의 절반으로 잘라보고 부족하면 더 짧게, 남으면 더 길게 잘라 보면 된다
    • 이진 탐색!
• 코드

import sys
input = sys.stdin.readline

# 떡의 개수, 요청한 떡의 길이
N, M = map(int,input().split())
# 떡의 개별 높이
arr = list(map(int,input().split()))

s = 0
# 가장 긴 떡을 기준으로 
e = max(arr)-1

answer = 0
while s <= e:
    mid = (s+e)//2
    # 잘린 떡의 총 합
    x = sum([i-mid for i in arr if i-mid > 0])

    # 떡의 양이 부족한가? -> 더 자르자 -> 높이를 낮추자
    if x < M:
        e = mid - 1
    # 떡의 양이 충분한가? -> 덜 잘라보자 -> 높이를 높인다.
    elif x > M:
        answer = mid
        s = mid + 1
        
print(answer)