알고리즘 이론 - 이분 탐색

☑️ To-do

• 이분 탐색 이론 정리
  • 이론 탐색 문제 접근 방식 정리
• Week02 문제 풀이
  • 11053 / 2630 / 1629 / 10830 / 6549 / 13334

 

 

---

이분 탐색(Binary Search)

• 데이터가 정렬되어있는 상태
• 타깃 데이터 탐색
• 중앙값 비교를 통한 대상 축소 방식

 

• 시간복잡도

$$O(lgN)$$

 

이진 탐색 과정

1. mid 값 특정

2. if mid > target, 왼쪽 탐색

3. if mid < target, 오른쪽 탐색

4. if mid == target, 탐색 종료

 

 

파라메트릭 서치(Parametric Search)

• 최적화 문제(문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제)를 결정 문제로 바꾸어 푸는 것

1. 결정 문제를 정의했을 때, 쉽게 풀 수 있는 경우

2. 최솟값의 구하는 경우에, 최솟값이 x라면 x 이상의 값에 대해서는 모두 조건을 만족

3. 최댓값을 구하는 경우에, 최댓값이 x라면 x 이하의 값에 대해서는 모두 조건을 만족

 

 

 

---

이분탐색 PS

 

[boj. 2805] 나무 자르기

• 이분탐색 대표 문제

 

• 🏃‍♂️ Try 1 : 시간초과

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())))

answer = 0
start, end = 0, arr[-1]
while start <= end:
    total = 0
    mid = (start + end) // 2
    for i in range(n):
        if arr[i] > mid: total += arr[i] - mid
    if total < m:
        end = mid -1
    else:
        start = mid + 1
        answer = mid

print(answer)

• 함수 모듈화를 안하고 돌리면 시간초과 가 발생한다.

 

• 🎉 Complete

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())))

def binary_search(start, end):
    answer = 0
    while start <= end:
        total = 0
        mid = (start + end) // 2
        for i in range(n):
            if arr[i] > mid: total += arr[i] - mid
        if total < m:
            end = mid -1
        else:
            start = mid + 1
            answer = mid # 적어도 m 이상이니까 answer에 mid값 저장
    return answer

print(binary_search(0, arr[-1])) # 최대로 자를 수 있는 나무 길이가 arr[-1]이므로 max값 제한

[boj. 2110] 공유기 설치

import sys

input = sys.stdin.readline
n, c = map(int, input().split())
arr = []
for _ in range(n):
    arr.append(int(input()))
arr.sort()

def binary_search():
    answer = 0
    start, end = 0, arr[-1]
    while start <= end:
        mid = (start + end) // 2
        l_house = arr[0] # 이전 집과의 간격 측정을 위한 포인터
        cnt = 1
        for i in range(1, n):
            if arr[i] - l_house >= mid:
                cnt += 1
                l_house = arr[i]
        if cnt < c:
            end = mid - 1
        else:
            start = mid + 1
            answer = mid
    return answer

print(binary_search())

• 집 사이의 인접 최대 간격 값을 이분탐색을 진행하는 타깃 값으로 설정했다.
• 해당 간격을 기준으로 공유기를 설치했을 때, 설치할 수 있는 집 개수를 카운트한다.

 

 

• 🙋 첫 번째 원소에 무조건 공유기를 설치하는 이유?
  • (https://www.acmicpc.net/board/view/99986)

[boj. 2470] 두 용액

• 🏃‍♂️ Try 1

import sys

input = sys.stdin.readline
n = int(input())
arr = sorted(list(map(int, input().split())))
val, answer = 1e9, (0, 0) ###

start, end = 0, n - 1
while start < end:
    t = abs(arr[start] + arr[end]) 
    if val > t:
        val = t
        answer = (arr[start], arr[end])
    a = abs(arr[start + 1] + arr[end])
    b = abs(arr[end - 1] + arr[start])
    if a < b: start = start + 1
    else: end = end - 1

print(answer[0], answer[1], sep=' ')

• 입력 최대, 최소 값이 -1e9, 1e9인데, 이때 비교값도 1e9로 넣어버려서 틀렸다.
• 최댓값 입력으로 999,999,999 1,000,000,000 으로 생각하고 MAX_VALUE를 1e18로 바꿔줬다!

 

• 🎉 Complete

import sys

input = sys.stdin.readline
n = int(input())
arr = sorted(list(map(int, input().split())))
val, answer = 1e18, (0, 0)

start, end = 0, n - 1
while start < end:
    t = abs(arr[start] + arr[end]) 
    if val > t:
        val = t
        answer = (arr[start], arr[end])
    if abs(arr[start + 1] + arr[end]) < abs(arr[end - 1] + arr[start]):
                start = start + 1
    else: end = end - 1

print(answer[0], answer[1], sep=' ')

• 투 포인터
• 정렬된 리스트의 좌측 원소, 우측 원소를 비교하며 둘의 차잇값을 갱신해준다.

---

💡 이분탐색 PS Tip

1. 이분 탐색을 진행할 타깃 값을 설정한다.
2. 이때, 타깃 값은 범위를 좁혀나갈 수 있는 값으로 설정한다.

⭐️ 타깃 값이 반드시 문제에서 제시된 값이 아님을 인지하자!

​ (문제 제시 값에서 찾으려고 너무 매몰되지 않기...! 😭)

---

🔗 Reference

• 이분 탐색(Binary Search)
  • (https://blog.naver.com/kks227/220777333252)
• [이분탐색] 파라메트릭 서치(개념)
  • (https://sarah950716.tistory.com/16)