[코테 직전 유형별 정리] - 이분탐색

알고리즘 문제 중에서 그나마 쉬운 유형에 속하는 것 같다. 탐색 알고리즘 자체는 정형화되어 있으니... 

다만 다른 문제 유형이랑 섞이기 시작하면 이제 골치아파지는거다.

 

---

 

유형 1. 단순 탐색 문제

이분탐색이 쉽게 나오면 그냥 목표 값을 찾기만 하면 되는 문제가 나온다.

목표 값만 잘 설정해두면 low, high 나눠서 찾기만 하면 되니까, 가장 쉬운 난이도의 유형이라 볼 수 있다.

• 용액

https://www.acmicpc.net/problem/2467

산성 +, 알칼리성 - 용액을 더해서 0에 최대한 가깝게 하는 문제.

당연하게도 ph 농도 자체를 탐색 대상으로 잡으면 된다.

"""
어떤 것을 이분탐색 대상으로 놓을지 잘 선택해보자

산성 양수 / 알칼리성 음수
0에 가장 가까워야 함

1. sort를 해요
2. min max 값 더하기 -> 현재 값이 작으면? min값 옮기기 / 현재값이 크면? max 값 옮기기
"""

N = int(input())
liqs = list(map(int, input().split()))

liqs.sort()

l, h = 0, len(liqs) - 1
avg_liq = liqs[l] + liqs[h]

min_liq = liqs[l]
max_liq = liqs[h]


while True:
    if l >= h:
        break

    liq_sum = liqs[l] + liqs[h]

    # print(liq_sum)
    # print('## current liq', liqs[l], liqs[h])
    if liq_sum < 0:
        if abs(liq_sum) < abs(avg_liq):
            avg_liq = liq_sum
            min_liq = liqs[l]
            max_liq = liqs[h]
        l += 1

    elif liq_sum > 0:
        if abs(liq_sum) < abs(avg_liq):
            avg_liq = liq_sum
            min_liq = liqs[l]
            max_liq = liqs[h]
        h -= 1
    else:
        avg_liq = liq_sum
        min_liq = liqs[l]
        max_liq = liqs[h]
        break
    
    # print('## min-max liq', min_liq, max_liq)
print(min_liq, max_liq)

 

 

• 퍼즐 게임 챌린지

https://school.programmers.co.kr/learn/courses/30/lessons/340212?language=python3

모든 게임을 풀이하는데 필요한 숙련도의 최소값을 이분탐색으로 구하면 된다.

"""
제한 시간 내 퍼즐을 모두 해결하기 위한 숙련도 최소값
diffs	times
[1, 99999, 100000, 99995]	[9999, 9001, 9999, 9001]

숙련도의 최소값 -> 이분탐색으로 구하기

diff <= level인지 체크
    - 소요시간 time_cur

diff > level
    - 한번 틀릴때마다 걸리는 시간 = time_cur + time_prev
    - 소요시간 (diff - level - 1) * (time_cur + time_prev) + time_cur

"""
def calculate(diffs, times, limit, level):
    
    if diffs[0] <= level:
        total = times[0]
    else:
        # 풀어야 할 이전 문제 없음
        total = (diffs[0] - level) * times[0]
    
    for i in range(1, len(diffs)):
        if diffs[i] <= level:
            total += times[i]
        else:
            # 이전 퍼즐은 무조건 틀리지 않음
            total += (diffs[i] - level) * (times[i] + times[i-1]) + times[i]
    
    if total > limit:
        return False
    
    else:
        return True
    


def solution(diffs, times, limit):
    l = 0; h = max(diffs)
    answer = max(diffs)
    
    while l + 1 < h:
        mid = (l + h) // 2
        # print("## l", l, "h", h)
        # print("## 초기 레벨 값 ", mid)
        
        # 계산하기
        if calculate(diffs, times, limit, mid):
            answer = min(mid, answer)
            h = mid
        
        else:
            l = mid
    
    return answer

 

---

 

유형 1-1. 징검다리 문제

이분탐색 문제 중 가장 헷갈렸던 유형이라서 따로 분리했다.

• 징검다리 건너기

https://school.programmers.co.kr/learn/courses/30/lessons/64062

앞사람이 밟을 때마다 디딤돌 숫자가 줄어들기 때문에, 현재 남아있는 숫자로 징검다리를 건널 수 있는지 확인해주는 함수를 추가해주었다.

def can_check(bridge, people, k):
    # 0 이하 구간이 연속되는 최대 횟수
    cnt = 0
    
    for stone in bridge:
        # 뛰어 넘을 수 없는 칸 : 남은 칸수 - 사람 수 음수면 못뛰어넘는 칸 +1
        if stone < people:
            cnt += 1
            if cnt >= k:
                return False
        else:
            cnt = 0
    
    return True       

def solution(stones, k):
    start, end = 0, max(stones)
    max_people = 0
    
    while start <= end:
        mid = (start + end) // 2
        # print('## people : ', mid)
        
        # 건널 수 있다는 뜻
        if can_check(stones.copy(), mid, k):
            max_people = max(max_people, mid) # 최대값 갱신
            start = mid + 1
            
        # 건널 수 없으면
        else:
            end = mid - 1
    
    return max_people

 

 

• 징검다리

https://school.programmers.co.kr/learn/courses/30/lessons/43236

프로그래머스

 

문제 조건을 꼼꼼히 읽어야 할 뿐만 아니라, 생각이 좀 필요한 문제였다.

"바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값" 을 구해야 하므로,

가장 짧은 거리를 만들 때 바위를 하나씩 제거해보고 그 사이의 모든 거리를 하나씩 살펴보기

 

즉 핵심 로직은,

처음부터 가장 짧게 만들 바위 간 거리를 하나 정하고, 나머지 바위를 제거할 때 무조건 이 값보다 큰 값이 나오도록 함

→ 제거해야 할 바위가 목표한 것보다 많다면 거리를 줄이고, 목표한 것보다 적다면 거리를 늘리는 방식

 

"""
거리의 최소값 - 이분탐색 대상
각 지점 거리의 최소값 중 가장 큰 값

"""

def solution(distance, rocks, n):
    rocks.append(distance) # 끝점도 고려해야 함!!
    
    rocks.sort() # [2, 11, 14, 17, 21]
    
    s, e = 0, distance
    answer = 0
    
    while s <= e:
        mid = (s+e) // 2
        
        removed_rock = 0
        prev_rock = 0
        
        # 순회하기
        """
        앞에서부터 하나씩 제거해서 두 바위 사이 간격이 중간값 미만이면 바위를 계속 제거
        초과하면 기준을 현재 위치로 바꾸기
        
        - 제거된 바위 개수가 n개 이하이면 더 제거 가능
        - 제거된 바위 개수가 n개 초과면 다시 줄이기
        """
        for rock in rocks:
            if rock - prev_rock < mid:
                removed_rock += 1
            else:
                prev_rock = rock
        
        # 제거된 바위가 n개 이하일 경우
        if removed_rock <= n:
            s = mid + 1
            answer = mid
        else:
            e = mid - 1
            
    
    return answer

 

 

 

---

 

 

유형 2. 검색 유형

약간의 응용력이 들어간 문제 유형.

반복문 내에서 직접 탐색하는 게 아니라, bisect를 활용하여 문자열을 탐색하는 방식으로 많이 푼다.

물론 완전 탐색으로도 풀 수 있는 문제이지만, 정확도 / 효율성을 빡빡하게 체크한다면 이분탐색이 강제된다.

 

• 순위 검색

https://school.programmers.co.kr/learn/courses/30/lessons/72412  

프로그래머스

 

조건이 되는 문자열을 key (defaultdict) 로 두고, 

해당 조건에 부합하는 점수 리스트 중에서 score 이상인 개수 카운트하면 된다.

 

from itertools import combinations
from collections import defaultdict
from bisect import bisect_left

def solution(info, query):
    answer = []

    # key: 조건 문자열 조합, value: 해당 조건을 만족하는 지원자들의 점수 리스트
    applicants = defaultdict(list)

    for i in info:
        applicant = i.split()
        score = int(applicant.pop())  # 마지막 점수 분리
        conditions = applicant        # ['java', 'backend', 'junior', 'pizza']

        # 0~4개의 조건 조합을 key로 사용
        for j in range(5):
            for comb in combinations(conditions, j):
                key = ''.join(comb)
                applicants[key].append(score)

    # 모든 점수 리스트 정렬 → 이진 탐색을 위해
    for key in applicants:
        applicants[key].sort()

    for i in query:
        # 'and'와 '-' 제거하여 key 추출
        key = i.replace("and", "").replace("-", "").replace("  ", " ").split()
        score = int(key.pop())  # 마지막은 점수
        key = ''.join(key)

        # 해당 조건에 부합하는 점수 리스트 중에서 score 이상인 개수 카운트
        if key in applicants:
            scores = applicants[key]
            idx = bisect_left(scores, score)  # score 이상 첫 index
            answer.append(len(scores) - idx)
        else:
            answer.append(0)

    return answer

 

 

• 가사 검색

https://school.programmers.co.kr/learn/courses/30/lessons/60060

프로그래머스

 

와일드카드(?)가 포함된 문자열 검색에서 매치된 단어가 몇 개인지를 반환하는 문제이다.

 

• 쿼리와 단어의 길이가 일치해야만 매칭 가능
• ?는 무조건 앞이나 뒤에만 나옴
  • 접두사 ???ix → 뒤에서부터 정렬된 문자열에서 매칭
  • 접미사 fro?? → 앞에서부터 정렬된 문자열에서 매칭
• 매칭은 정렬된 리스트에서 이진 탐색으로 수행 (bisect_left, bisect_right)

 

from bisect import bisect_left, bisect_right

def solution(words, queries):
    answer = []

    # 단어 길이별로 정방향/역방향 정렬된 리스트 저장
    arr = [[] for _ in range(10001)]            # 정방향
    reversed_arr = [[] for _ in range(10001)]   # 역방향

    for word in words:
        arr[len(word)].append(word)
        reversed_arr[len(word)].append(word[::-1])  # 단어를 뒤집어서 저장

    # 이진 탐색을 위해 미리 정렬
    for i in range(10001):
        arr[i].sort()
        reversed_arr[i].sort()

    for q in queries:
        if q[0] == '?':
            # 접두사가 와일드카드인 경우 → 뒤집은 배열 사용
            query = q[::-1]
            left = query.replace('?', 'a')
            right = query.replace('?', 'z')
            res = bisect_right(reversed_arr[len(q)], right) - bisect_left(reversed_arr[len(q)], left)
        else:
            # 접미사가 와일드카드인 경우 → 정방향 배열 사용
            left = q.replace('?', 'a')
            right = q.replace('?', 'z')
            res = bisect_right(arr[len(q)], right) - bisect_left(arr[len(q)], left)

        answer.append(res)

    return answer