이분 탐색이란?
정렬된 배열에서 target의 존재 여부와 위치를 알려준다.
재귀적으로 탐색 범위를 반으로 줄여, 시간복잡도를 O(logN)까지 줄일 수 있다.
매개 변수 탐색(Parametric Search)란?
이분 탐색과 유사하다.
탐색 범위를 반으로 줄이기 때문에 시간복잡도는 O(logN)이다.
최적화 문제를 결정 문제로 바꾸어 풀 때 사용한다.
- 최적화 문제: 어떤 알고리즘의 최적 솔루션을 찾는 것
- 결정 문제: 답이 이미 결정되어 있다고 보고 문제를 푸는 것
이진 탐색과 매개변수 탐색의 차이점
이진 탐색은 배열에서 target과 일치하는 값을 찾으면 바로 함수를 종료하지만, 매개변수 탐색은 함수를 종료하지 않고 모든 배열을 살펴본다.
따라서, 매개변수 탐색은 어떤 조건을 만족하는 위치 중 가장 크거나 작은 값을 찾을 때 사용한다.
1. 어떤 시점까지 조건을 만족하지만 그 후로 만족하지 않는 경우, 조건을 만족하는 최댓값 찾기
2. 어떤 시점까지 조건을 만족하지 않지만 그 후로는 조건을 만족하는 경우, 조건을 만족하는 최소값 찾기
1. 1654: 랜선 자르기
랜선의 길이를 움직여 랜선 개수를 채우는지 보는 것이다.
1) 가장 짧은 길이 1을 start로, 랜선 중 가장 긴 길이를 end로 둔다.
2) 이분탐색이 끝날 때까지 while 문을 돌린다.
3) mid를 start와 end의 중간으로 두고, 모든 랜선 값을 mid로 나누어 총 몇개의 랜선이 나오나 살펴본다.
4-1) 랜선이 목표치 이상이면 mid+1을 start로 두고 다시 while문 반복
4-2) 랜선이 목표치 이하면 mid-1을 end로 두고 다시 while문 반복
5) start와 end가 같아지면: 조건을 만족하는 최대의 랜선길이를 찾으면 탈출한다.
6) 결과값인 end출력
# 1654: 랜선 자르기
import sys
sys.stdin = open('input.txt', 'r')
K, N = map(int, sys.stdin.readline().split())
lines = [int(sys.stdin.readline()) for i in range(K)]
def solution(target, key):
start, end = 1, max(target)
while start <= end: # 적절한 랜선의 길이를 찾는 알고리즘
mid = (start + end) // 2
lines = 0
for i in target:
lines += i // mid # 분할된 랜선 수
if lines >= key:
start = mid + 1
else:
end = mid - 1
return end
sys.stdout.write(f'{solution(lines, N)}')2. 2805: 나무자르기
벌목 높이를 움직여 필요 나무 길이를 채우는지 보는 것이다.
1. 입력: 나무 개수 N = 100만, 필요한 나무 길이 M(상근이가 집으로 가져가려고 하는 나무의 길이) = 20억
=> 값이 10억 이상으로 설정된 경우 이진탐색을 고려해보아야 한다.
2. 출력 => 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값를 출력한다.
1) 가장 짧은 길이 1을 start로, 나무 중 가장 긴 길이를 end로 둔다.
2) 이분탐색이 끝날 때까지 while 문을 돌린다.
3) mid를 start와 end의 중간으로 두고, 모든 랜선 값을 mid로 나누어 총 몇개의 랜선이 나오나 살펴본다.
4-1) 잘린 나무의 합(tree)이 목표치(M) 이상이면 mid+1을 start로 두고 다시 while문 반복
4-2) 잘린 나무의 합(tree)이 목표치(M) 이하면 mid-1을 end로 두고 다시 while문 반복
5) start와 end가 같아지면: 조건을 만족하는 최대의 나무 절단 높이를 찾으면 탈출한다.
6) 결과값인 end출력
# 2805: 나무 자르기
n, m = map(int, input().split())
trees = list(map(int, input().split()))
start, end = 1, max(trees)
# start와 end가 같아질 때까지 반복
while start <= end:
# mid: 나무 절단 높이
mid = (start + end) // 2
tree = 0 # 잘린 나무 합
# 나무 자르기
# trees => [20, 15, 10, 17]
for i in trees:
# 나무의 높이가 절단기 높이보다 크다면
if i > mid:
tree += i - mid
# 원하는 나무 높이보다 덜 잘렸으면
if tree < m:
end = mid - 1 # mid(나무 절단 높이)를 낮추고
# 원하는 나무 높이보다 더 많이 잘렸으면
else:
start = mid + 1 # mid(나무 절단 높이)를 높이고
print(end)3. 2110: 공유기 설치
- 집 좌표 담은 home 리스트를 정렬한 후, 맨 첫 번째 집부터 공유기를 설치하는데 이때 공유기 사이의 거리를 mid만큼 잡는다.
- 공유기를 설치한 횟수를 나타내는 count가 주어진 공유기 개수 C 이상이면 공유기 사이의 거리를 넓히고, C미만이면 거리를 좁힌다.
1) 공유기 사이의 최소거리 1을 minGap로, 공유기 사이의 최대거리 target[-1]-target[0]를 maxGap로 둔다.
2) 이분탐색이 끝날 때까지 while 문을 돌린다.
3) midGap를 minGap와 maxGap의 중간으로 두고, 맨 첫번째 집부터 공유기를 설치하는데 이 때 공유기 사이의 거리를 midGap으로 잡는다.
4) count는 공유기를 설치한 횟수를 나타내고, 맨 첫 번째 집(wifi = target[0])은 이미 설치했기에 count=1로 초기화한다.
5) 모든 집을
6-1) 공유기 갯수가 필요한 갯수보다 많거나 같으면 midGap+1을 minGap로 두고 다시 while문 반복
6-2) 공유기 갯수가 필요한 갯수보다 부족하면 midGap-1을 maxGap로 두고 다시 while문 반복
① minGap= 1, maxGap = 8
- 이진 탐색에서는 minGap, maxGap 를 설정하여 중간값을 찾고 이 과정을 반복한다.
- midGap= 4 ∵ (1+8)//2 = 4
- 공유기들의 거리 차가 midGap보다 크게 될 수 있도록, 위치를 설정한다.
[ 1 ] [ 2 ] [ 4 ] [ 8 ] [ 9 ]
→ 공유기 2개 가능
→ 설치 가능한 공유기의 개수(count)가 C보다 작으므로, midGap을 감소시킨다.
② minGap= 1, maxGap = 3
- midGap= 2 ∵ (3+1)//2 = 2
[ 1 ] [ 2 ] [ 4 ] [ 8 ] [ 9 ]
→ 공유기 3개 가능
→ 설치 가능한 공유기의 개수가 C 이상이므로, 현재 Gap을 저장한 후 Gap을 증가시킨다.
③ minGap = 3, maxGap = 3
- midGap= 3
[ 1 ] [ 2 ] [ 4 ] [ 8 ] [ 9 ]
→ 공유기 3개 가능
→ 더 이상 midGap을 증가시킬 수 없으므로, 최적의 경우이다.
# 2110: 공유기 설치
import sys
sys.stdin = open('input.txt', 'r')
N, C = map(int, sys.stdin.readline().split())
# 이분 탐색을 위한 정렬
house = sorted([int(sys.stdin.readline().rstrip()) for i in range(N)])
# 출력값 => 첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리
def solution(target, c):
minGap = 1 # start: 공유기 사이의 최소 거리
maxGap = target[-1] - target[0] # end: 공유기 사이의 최대 거리
while minGap <= maxGap:
# mid: 공유기 사이의 최소 거리와 최대 거리의 중앙값
midGap = (minGap + maxGap) // 2
# wifi: 가장 마지막으로 와이파이를 설치한 집의 좌표를 저장한다.
wifi = target[0]
count = 1
for i in range(len(target)): # 모든 집을 다 돈다.
if target[i] >= wifi + midGap:
wifi = target[i] # 공유기 설치된 집 갱신
count += 1
# 설치한 공유기의 갯수를 토대로, 범위를 조정한다.
if count >= c: # 공유기 갯수가 필요한 양보다 많거나 같으면 간격을 높인다.
temp = midGap
minGap = midGap + 1
# 공유기 갯수가 필요한 갯수보다 부족하면 간격을 줄인다.
else:
maxGap = midGap - 1
return temp
sys.stdout.write(f'{solution(house, C)}')왜 이렇게 헷갈릴까...................................................................... 다시 봐야겠다 :)
3. 16564: 히오스 프로게이머
문제
이 게임에는 총 N개의 캐릭터가 있다. 그리고 현재 각 캐릭터의 레벨은 Xi이다.
성권이는 앞으로 게임이 끝날 때까지, 레벨을 최대 총합 K만큼 올릴 수 있다. 팀 목표레벨 T =min(Xi) (1 ≤ i ≤ N)라고 정의하면, 게임이 끝날 때까지 성권이가 달성할 수 있는 최대 팀 목표레벨 T는 무엇인가?
예를 들어, N = 3, X1= 10, X2= 20, X3= 15이고 K = 10일 때, X1을 7만큼 올리고 X3을 2만큼 올리면 최소 레벨 Xi는 17이 된다. 따라서 팀 목표레벨 T는 17이다. 이 경우처럼 레벨을 총합 K보다 적게 올릴 수도 있다.
1. 입력 => 값이 10억 이상으로 설정된 경우 이진탐색을 고려해보아야 한다.
2. 출력 => 가능한 최대 팀 목표레벨 T를 출력한다.
기본적으로 나무자르기 문제와 같은 개념이다. (잘라야하는 나무의 양 = 레벨 업 해야하는 총량)
레벨업하는 총량이 올릴 수 있는 레벨의 총합(K)을 넘어가지 않는 선에서 최대 높이를 찾는다. 레벨의 총합(K)을 다 써도 혹은 다 쓰지 않아도 올라가고자 하는 최대 목표 레벨을 찾기 위함이기에 min(Xn)은 똑같을 것이다.
최고점은 max(level) 값에 k//n을 더해준다. 의 직관적인 이유는??????
1. 처음부터 max에게만 K를 더해주면 우리의 목표는 팀 내에서 가장 낮은 레벨이 가장 커지는 지점을 찾기 위함인데 max가 더 커지기만 할 뿐 적절하지 않다.
2. K를 적당히 나눠서 쪼렙이의 레벨들을 높여준다.
3. 쪼렙이를 버리지 않고 쪼렙이(min)부터 채우면서 모두가 최대 목표 레벨에 도달하도록 나눠준다.
# 16564: 히오스 프로게이머
import sys
sys.stdin = open('input.txt', 'r')
N, K = map(int, sys.stdin.readline().split())
level = sorted([int(sys.stdin.readline().rstrip()) for i in range(N)])
# 악 !!! sorted 안 해서 값이 안 나오는 것이었다... 이분탐색은 정렬을 하고 들어가야 한다.
def solution(targets, k, n):
# 최저점을 가장 낮은 레벨(min(level))
# 최고점은 max(level) 값에 k//n을 더해준다.
# 이 둘의 평균을 t_value로 잡아서 이분탐색 시작
lowest, highest = min(targets), max(targets) + k//n
while lowest <= highest:
t_value = (lowest + highest) // 2
total = 0
for target in targets:
if t_value > target:
total += t_value - target
else:
break
# total: 레벨업하는 총량
# k: 레벨의 총합(K)
if total > k:
highest = t_value - 1
elif total == k:
return t_value
# 레벨의 총합 K보다 적게 올릴 수도 있기에 t_value를 temp에 넣어줌
else:
temp = t_value
lowest = t_value + 1
return temp
sys.stdout.write(f'{solution(level, K, N)}')공부 참고 블로그:
From YJ 히오스 프로게이머 풀이: https://github.com/jnl1128/W02_teamB4/blob/master/B16564/B16564_OYJ.py
랜선 자르기 풀이: https://claude-u.tistory.com/443?category=260018
공유기 설치 풀이: https://leunco.tistory.com/79
'Problem Solving > Algorithm Concepts' 카테고리의 다른 글
| [알고리즘] 스택 & 백준(탑, PPAP) (0) | 2022.10.08 |
|---|---|
| [알고리즘] 이분 탐색, 투 포인터 알고리즘 & 백준(두 수의 합, 두 용액) (1) | 2022.10.06 |
| [알고리즘] 분할 정복 & 백준(곱셈, 행렬 제곱) (1) | 2022.10.05 |
| [알고리즘] 행렬 곱셈, 행렬 제곱 (0) | 2022.10.04 |
| [알고리즘] 우선순위 큐, 힙 & 백준(최대 힙, 최소 힙, 가운데를 말해요, 카드 정렬하기) (1) | 2022.10.03 |
