이분탐색
1. 정렬된 배열 또는 정렬 가능한 값이 주어진다
- 이분 탐색은 기본적으로 오름차순 또는 내림차순으로 정렬된 배열에 대해서만 사용할 수 있습니다.
- 정렬된 배열에서 특정 값을 찾거나, 특정 범위 안에서 값을 찾아야 할 때 이분 탐색을 떠올리면 좋습니다.
2. 탐색의 대상이 숫자, 길이, 무게 등의 ‘범위’일 때
- 결과값이 특정 범위 내에 있는지를 판별해야 하거나, 특정 값 이상이거나 이하인 값을 찾는 경우 이분 탐색을 활용할 수 있습니다.
- 예를 들어 "최소 길이" 또는 "최대 무게" 등의 제한이 있다면, 이분 탐색으로 조건에 맞는 최적의 값을 찾을 수 있습니다.
3. ‘최대값’ 또는 ‘최소값’을 찾아야 하는 경우
- 예를 들어 특정 작업을 수행하는 데 필요한 최소 시간이나 최대 크기를 찾는 문제는 이분 탐색의 후보가 될 수 있습니다.
- 특정 조건을 만족하는 값의 최대/최소 경계를 찾는 문제라면, 상한선과 하한선을 정해 탐색하는 방식을 적용할 수 있습니다.
4. 결과가 ‘참/거짓’으로 나뉠 수 있는 경우
- 어떤 값이 조건을 만족하는지 여부가 이분 탐색으로 확인 가능해야 합니다.
- 예를 들어 "X 값에서 가능한가?"라는 질문에 대해 "가능하다/불가능하다"의 형태로 답할 수 있다면 이분 탐색을 고려해볼 수 있습니다.
5. 반복적인 계산을 통해 특정 값을 탐색하는 경우
- 각 단계에서 중간 값을 선택해 조건을 만족하는지 계산하고, 그 결과에 따라 탐색 범위를 줄여 나갈 수 있다면 이분 탐색이 적합합니다.
- 예시: 특정 작업을 완료하는 데 걸리는 최소 시간, 주어진 예산 내에서 구매 가능한 최대 물건 수 등.
예시 문제 유형
- 숫자 찾기: 정렬된 배열에서 특정 숫자 또는 특정 숫자의 위치를 찾는 문제.
- 최적화 문제: "가장 작은", "가장 큰" 값을 구하는 문제(예: 특정 조건에서 가장 작은 크기, 최소 비용).
- 조건을 만족하는 최대/최소값: 특정 조건을 만족하는 값 중에서 최소 또는 최대값을 찾는 문제 (예: 특정 물건을 사기 위해 필요한 최소 예산).
이분 탐색 문제는 탐색 대상이 정렬되어 있거나 특정 조건을 만족하는 값의 범위가 명확할 때 주로 등장합니다.
이분탐색에서 자주 쓰이는 정렬 개념 - 힙을 통한 정렬
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)