[알고리즘] 이분 탐색, 매개 변수 탐색 & 백준(랜선 자르기, 나무 자르기, 공유기 설치, 히오스 프로게이머)

이분 탐색이란?

정렬된 배열에서 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)부터 채우면서 모두가 최대 목표 레벨에 도달하도록 나눠준다. 

YJ가 이거 보단 예쁘게 쓸 수 있다고 했다. ..💕 설명을 위함~

YJ언니가 설명해준 이 그림을 설명하자면 초록색인 각각의 레벨이 있으며 lowest과 highest의 평균인 t_value를 기준으로 잡는다. for문을 통해 각각의 level이 레벨업할 수 있는 값(핑크색)들을 더해서 총량 total을 구한다. 올릴 수 있는 레벨 총합 K보다 total이 크면 t_value를 하나 내리고, 같으면 t_value를 반환하고, 작으면 t_value를 하나 올린다. 이 과정을 반복하여 레벨 업하는 총량(total)이 올릴 수 있는 레벨 총합 K을 넘어가지 않는 선에서 최대 높이 t_value를 구한다.

# 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