이분탐색

1. 정렬된 배열 또는 정렬 가능한 값이 주어진다

• 이분 탐색은 기본적으로 오름차순 또는 내림차순으로 정렬된 배열에 대해서만 사용할 수 있습니다.
• 정렬된 배열에서 특정 값을 찾거나, 특정 범위 안에서 값을 찾아야 할 때 이분 탐색을 떠올리면 좋습니다.

2. 탐색의 대상이 숫자, 길이, 무게 등의 ‘범위’일 때

• 결과값이 특정 범위 내에 있는지를 판별해야 하거나, 특정 값 이상이거나 이하인 값을 찾는 경우 이분 탐색을 활용할 수 있습니다.
• 예를 들어 "최소 길이" 또는 "최대 무게" 등의 제한이 있다면, 이분 탐색으로 조건에 맞는 최적의 값을 찾을 수 있습니다.

3. ‘최대값’ 또는 ‘최소값’을 찾아야 하는 경우

• 예를 들어 특정 작업을 수행하는 데 필요한 최소 시간이나 최대 크기를 찾는 문제는 이분 탐색의 후보가 될 수 있습니다.
• 특정 조건을 만족하는 값의 최대/최소 경계를 찾는 문제라면, 상한선과 하한선을 정해 탐색하는 방식을 적용할 수 있습니다.

4. 결과가 ‘참/거짓’으로 나뉠 수 있는 경우

• 어떤 값이 조건을 만족하는지 여부가 이분 탐색으로 확인 가능해야 합니다.
• 예를 들어 "X 값에서 가능한가?"라는 질문에 대해 "가능하다/불가능하다"의 형태로 답할 수 있다면 이분 탐색을 고려해볼 수 있습니다.

5. 반복적인 계산을 통해 특정 값을 탐색하는 경우

• 각 단계에서 중간 값을 선택해 조건을 만족하는지 계산하고, 그 결과에 따라 탐색 범위를 줄여 나갈 수 있다면 이분 탐색이 적합합니다.
• 예시: 특정 작업을 완료하는 데 걸리는 최소 시간, 주어진 예산 내에서 구매 가능한 최대 물건 수 등.

예시 문제 유형

1. 숫자 찾기: 정렬된 배열에서 특정 숫자 또는 특정 숫자의 위치를 찾는 문제.
2. 최적화 문제: "가장 작은", "가장 큰" 값을 구하는 문제(예: 특정 조건에서 가장 작은 크기, 최소 비용).
3. 조건을 만족하는 최대/최소값: 특정 조건을 만족하는 값 중에서 최소 또는 최대값을 찾는 문제 (예: 특정 물건을 사기 위해 필요한 최소 예산).

이분 탐색 문제는 탐색 대상이 정렬되어 있거나 특정 조건을 만족하는 값의 범위가 명확할 때 주로 등장합니다.

 

---

 

이분탐색에서 자주 쓰이는 정렬 개념 - 힙을 통한 정렬

 

1. 백준 "카드 정렬하기"

- 가장 작은 두 카드 묶음을 먼저 합치는 것이 최적의 선택

- 작은 카드 묶음을 먼저 합치면 이후에 큰 카드 묶음을 합치는 방식

- 가장 작은 두 묶음을 빠르게 찾기 위해 **우선순위 큐(힙)**를 사용

import heapq

def solution(card_packs):
    # 우선순위 큐에 모든 카드 묶음 넣기
    heapq.heapify(card_packs)
    
    total_cost = 0

    # 카드 묶음이 하나가 될 때까지 반복
    while len(card_packs) > 1:
        # 가장 작은 두 카드 묶음을 꺼냄
        first = heapq.heappop(card_packs)
        second = heapq.heappop(card_packs)

        # 두 카드 묶음을 합친 비용을 더함
        current_cost = first + second
        total_cost += current_cost

        # 합친 카드 묶음을 다시 큐에 넣음
        heapq.heappush(card_packs, current_cost)

    return total_cost

# 입력 예시
n = int(input())  # 카드 묶음의 개수
card_packs = [int(input()) for _ in range(n)]

 

 

2. 프로그래머스 입국심사

def solution(N, times):
    # 최소 시간과 최대 시간을 설정
    left, right = 1, max(times) * N
    answer = right  # 최소 시간을 최대 시간으로 초기화

    while left <= right:
        mid = (left + right) // 2  # 중간 시간 설정
        people = 0  # mid 시간 동안 처리할 수 있는 사람 수

        # 모든 심사대에서 처리 가능한 사람 수 계산
        for time in times:
            people += mid // time  # 각 심사대가 처리할 수 있는 사람 수

        # N명 이상 처리할 수 있으면 시간을 줄여본다
        if people >= N:
            answer = mid  # 가능한 최소 시간을 업데이트
            right = mid - 1
        else:
            left = mid + 1  # N명보다 적게 처리하면 시간을 늘림

    return answer

# 예시 실행
N = 6
times = [7, 10]
print(solution(N, times))  # 출력: 28

 

3. 백준 나무 자르기

2번 문제와 유사함

문제를 이해하는게 중요하다

 

# 가능한 절단기 높이 중 최대값 >> 절단기높이를 1~max 범위로 잡고 이분탐색

# 조건: M미터의 나무를 가져갈 수 있어야 한다 (조건 충족)

N, M = 4, 7
trees = [20, 15, 10, 17]
left, right = 1, max(trees) # 절단기 높이를 1~최대 까지 설정해 두고, M을 충족할때 까지 이분탐색
answer = 0

while left <= right:
    mid = (left + right) // 2 # 절단기 높이
    remain = 0 # 자르고 남은 트리의 높이 (가져갈 높이)

    for tree in trees:
        if tree > mid:
            remain += (tree - mid)

    if remain >= M: # 자르고 남은 나무높이가 최소로 가져가야 하는 높이보다 크면
        answer = mid
        left = mid + 1 # 더 높은 절단기에서 확인 (자르고 남은걸 remain 최소화 하는게 목표임)
    else:
        right = mid - 1 # 절단기 높이를 감소해서 더 자를수 있게 (remain 증가) 해야함

print(answer)

 

 

4. 프로그래머스 징검다리

바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 

- 문제 분석: 최대 가능한 최소 거리를 찾아야 함 > 이분탐색으로 징검다리 사이 최소 거리를 탐색

1) 징검다리 최소 거리를 설정

2) 최소 거리를 만족하기 위해 제거해야 하는 돌의 개수가 주어진 제한(n)을 넘는지 체크

3) 최소 거리가 더 커질 수 있으면 탐색 범위를 넓히고, 최소거리 유지가 불가하면 탐색 범위를 줄인다

 

* 동작원리 

돌 위치: [2, 11, 14, 17, 21, 25]  > 주어진 제거 가능한 돌의 개수 내에서, 최소 거리를 최대화 하는게 목표

mid: 탐색할 돌 사이 최소 거리

ex. mid=12 : 돌 사이 거리가 최소 12가 되도록 돌을 제거 -> n을 만족하는지 체크

 

left=1, right = 25

1) mid=12:  2, 11, 14 .. 다 제거해야 함. n=2 보다 크므로 최소거리를 줄인다

2) left = 1, right = 11 (12-1)  => mid = 6

3) mid=6
     - 0(현재위치) 와 2 사이 거리: 2  > 돌2 제거
     - 0(현재위치) 와 11 사이 거리: 11  > 돌11 유지

     - 11(현재위치) 와 14 사이 거리: 3  > 14 제거
     - 11(현재위치) 와 17 사이 거리: 6  > 돌17 유지

     - 17(현재위치) 와 21 사이 거리: 4  > 돌21 제거

이미 3개를 제거해야하므로 최소거리를 줄인다

 

4) left = 1, right = 10 (11-1)  => mid = 5

     3) 과정이랑 마찬가지임

     - 0(현재위치) 와 2 사이 거리: 2  > 돌2 제거
     - 0(현재위치) 와 11 사이 거리: 11  > 돌11 유지

     - 11(현재위치) 와 14 사이 거리: 3  > 14 제거
     - 11(현재위치) 와 17 사이 거리: 6  > 돌17 유지

     - 17(현재위치) 와 21 사이 거리: 4  > 돌21 제거

이미 3개를 제거해야하므로 최소거리를 줄인다

 

3)  left = 1, right = 8  => mid = 4

     - 0(현재위치) 와 2 사이 거리: 2  > 돌2 제거
     - 0(현재위치) 와 11 사이 거리: 11  > 돌11 유지

     - 11(현재위치) 와 14 사이 거리: 3  > 14 제거
     - 11(현재위치) 와 17 사이 거리: 6  > 돌17 유지

     - 17(현재위치) 와 21 사이 거리: 4  > 돌21 유지

     - 21(현재위치) 와 25 사이 거리: 4  > 돌21 유지

두개만 제거해도 되므로 n=2 조건 충족. 최종 답은4

 

def solution(distance, rocks, n):
    rocks.sort()
    rocks.append(distance) # 마지막 지점까지 거리에 포함

    left, right = 1, distance
    answer = 0

    while left <= right:
        mid = (left+right) // 2
        current = 0 # 현재위치
        remove_count = 0 # 제거한 돌의 수

        for rock in rocks:
            if rock - current < mid: # 돌 제거
                remove_count += 1
            else:
                current = rock # 현재 위치를 갱신
            
        if remove_count <= n:
            answer = mid
            left = mid + 1 # 더 큰 최소거리 시도
        else:
            right = mid - 1 # 너무많은 돌을 제거한 경우, 최소 거리를 줄임

    return answer

 

 

5. 백준 랜선자르기

lines = [802, 743, 457, 539]
N = 11 # 11개를 만들어야함
# 동일하게 자를 랜선 길이 (쵀대길이 구하는게 목표)
left, right = 1, max(lines)
answer = 0

while left <= right:
    mid = (left+right) // 2
    count = 0 # 자른 랜선 갯수

    for line in lines:
        count += (line//mid)
    
    if count >= N: # 더 많이 자른경우, 자를 랜선 길이를 늘려야함
        left = mid + 1
        answer = mid
    else:
        right = mid - 1

print(answer)