[이코테] 이진 탐색

본 포스팅은 유투브에 온라인 배포되어 있는 나동빈 님의 이코테 강의를 수강하며 정리한 내용을 기록한 것입니다. 자세한 내용이 궁금하다면, 링크를 참고하시길 바랍니다.

 

포스팅 내 코드 블록은 깃허브에서 찾을 수 있음.

 

목차

 

1. 이진 탐색

• 순서대로 정렬된 배열이 있을 때, 가능성을 반씩 줄여가며 목표 값을 탐색하는 알고리즘
• 선형 탐색은 최대 O(N)의 시간복잡도를 가지나, 이진 탐색은 O(logN)의 시간복잡도를 가짐

 

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

• bisect_left: 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스 반환
• bisect_right: 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스 반환

이진 탐색 코드

from bisect import bisect_left, bisect_right

a = [1, 2, 4, 4, 8]
x = 4

print(bisect_left(a, x))
print(bisect_right(a, x))

4
2

 

 

두 값의 차이를 이용하면 배열 내 x의 개수를 구할 수 있다.

# a 배열에서 x의 개수
print(bisect_right(a,x) - bisect_left(a,x))

2

 

 

이 개념을 확장하면 [i, j] 범위 내에 데이터가 몇 개 있는지 셀 수도 있다

# a 배열에서 [i, j] 범위에 포함되는 데이터의 개수
i = 2
j = 4
print(bisect_right(a,j) - bisect_left(a,i))

3

파라메트릭 서치 (Parametric Search)

• 최적화 문제를 결정 문제로 바꾸어 해결하는 기법 -> 예시를 보면 알겠지만, 잘은 이해가 안감.
• ex) 특정 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 문제
• 일반적으로 코테에서 파라메트릭 서치는 이직 탐색을 이용해 해결할 수 있음

 

문제1: 떡볶이 떡 만들기

파라메트릭 서치의 예

문제 정의

• 오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했습니다. 오늘은 떡볶이 떡을 만드는 날입니다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않습니다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰줍니다.
• 절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단합니다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않습니다.
• 예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것입니다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm입니다. 손님은 6cm 만큼의 길이를 가져갑니다.
• 손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하세요.

입출력 조건

• 입력 조건: 첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어집니다. (1 <= N <= 1,000,000. 1 <= M <= 2,000,000,000)
• 출력 조건: 적어도 M만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력합니다.

 

입력 예시

4 6
19 15 10 17

출력 예시

15

 

문제 해결 전략

• 제일 긴 떡의 길이보다 작을 때, 남는 떡이 생긴다. -> H의 범위는 0에서 (긴 떡의 길이-1) 사이
• 떡의 개수가 10만 개까지 가능하므로, N2 연산, 즉 선형 탐색으로 H를 찾으려고 하면 시간이 초과될 것이다
  -> 이진 탐색으로 풀자

동작 아이디어

1. 가장 긴 떡을 구한다
2. 이진 탐색으로 H를 구하고, H일 때 M을 구한다.
3. 목표 M보다 떡 길이가 작으면, H보다 작은 범위에서 이진 탐색
4. 목표 M보다 떡 길이가 크면, H보다 큰 범위에서 이진 탐색

DB's 아이디어

• 적절한 높이를 찾을 때까지 이진 탐색을 수행하여 높이 H를 반복해서 조정하면 됩니다.
• 현재 이 높이로 자르면 조건을 만족할 수 있는가?'를 확인한 뒤에 조건의 만족 여부(예 혹은 아니오)에 따라서 탐색 범위를 좁혀서 해결할 수 있습니다.
• 절단기의 높이는 0부터 10억까지의 정수 중 하나입니다.
• 이렇게 큰 탐색 범위를 보면 가장 먼저 이진 탐색을 떠올려야 합니다.

문제 풀이 코드

# 이코테 - 이진 탐색: 떡볶이 떡 만들기
n,m = list(map(int, input().split(' ')))
tteoks = list(map(int, input().split(' ')))

sp = 0 
ep = max(tteoks)-1

while sp<=ep:
    center = (sp+ep)//2
    sum_ = 0 
    
    for t in tteoks:
        sum_ += max(t-center, 0)

    print(center, sum_, m) # 이진 탐색을 잘 수행하고 있는지 로깅.
    
    if sum_ == m:          # 합이 목표 값과 같으면 그 때의 절단기 높이를 출력 후 반복문 중단
        print(center)
        break
    elif sum_ > m:         # 합이 목표 값보다 크면, 지금 절단기 높이보다 크게 설정
        sp = center+1
    elif sum_ < m:         # 합이 목표 값보다 작으면, 지금 절단기 높이보다 작게 설정
        ep = center-1
else:
    print(-1)

 

 

문제2: 정렬된 배열에서 특정 수의 개수 구하기

문제 정의

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 예를 들어 수열 (1, 1, 2, 2, 2, 2, 3}이 있을 때 x = 2라면, 현재 수열에서 값이 2인 원 소가 4개이므로 4를 출력합니다.

단, 이 문제는 시간 복잡도 0(LogN)으로 알고리즘을 설계하지 않으면 시간 초과 판정을 받습니다.

 

입출력 조건

• 입력 조건
  • 첫째 줄에 N과 x가 정수 형태로 공백으로 구분되어 입력됩니다. (1≤N≤ 1,000,000), (-109 ≤ x ≤ 109)
  • 둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력됩니다. (-10 s 각 원소의 값 S 109)
• 출력 조건: 수열의 원소 중에서 값이 x인 원소의 개수를 출력합니다. 단, 값이 x인 원소가 하나도 없다면 1을 출력합니다.

 

입력 예시

7 2
1122223

 

출력 예시

4

 

문제 풀이 전략

• 원래는 숫자를 세어가며 풀면 되지만, 시간복잡도 O(logN)으로 설계해야 하므로, 이진 탐색을 통해 수를 세면 된다.
• 파이썬 언어 이므로 내장함수를 사용하여 간단하게 해결하자

 

풀이 코드

# 이코테 - 이진탐색: 정렬된 배열에서 특정 수의 개수 구하기
from bisect import bisect_right, bisect_left

n,x = list(map(int, input().split(' ')))
nums = list(map(int, list(input())))

print(bisect_right(nums,x)-bisect_left(nums,x))