직접 풀어보자! 이분 탐색 5문제
안녕, 나 코딩냥이다냥! 오늘 다섯 문제는 차례대로 한 걸음씩 올라간다냥.
1번은 기본, 23번은 경계, 45번은 답 자체를 탐색한다냥. 순서를 지켜서 푸는 게
중요하다냥.
막히면 표를 그리자냥
예시 입력으로 서너 줄만 채워보면 lo 와 hi 가 어떻게 움직여야 하는지
보인다냥. 머리로만 굴리면 오래 걸린다냥.
target 이 배열에 있으면 YES, 없으면 NO 를 출력하는 문제다냥.
숨겨진 테스트에 target 이 배열의 최댓값보다 큰 경우가 있다냥.
경계를 찾아 arr[i] == target 으로 확인할 때, i 가 배열 끝을 넘을 수
있다냥. 그대로 읽으면 프로그램이 터진다냥.
i < n 인지 먼저 확인하고 읽어야 한다냥.
n, target = map(int, input().split())
arr = list(map(int, input().split()))
# 직접 while 로 짜봐도 되고, bisect 를 써도 된다냥
# 어느 쪽이든 범위 검사를 잊지 말자냥target 이상인 값이 처음 나오는 위치를 출력한다냥. 없으면 n 을
출력한다냥.
개념 페이지의 경계 찾기 골격을 그대로 쓰는 문제라냥. 세 가지를 기억하자냥.
hi시작값은n이라냥 (n - 1이 아니라냥)- 반복 조건은
lo < hi라냥 - 줄일 때
hi = mid라냥 (mid - 1이 아니라냥)
숨겨진 테스트에 같은 값이 여러 개 있는 경우가 있다냥. bisect_right 를
쓰면 위치가 뒤로 밀려서 틀린다냥.
n, target = map(int, input().split())
arr = list(map(int, input().split()))
lo, hi = 0, n
while lo < hi:
mid = (lo + hi) // 2
# arr[mid] 를 보고 lo 또는 hi 를 옮긴다냥
pass
print(lo)a 이상 b 이하인 값이 몇 개인지 출력한다냥.
2번에서 만든 경계를 두 번 쓰면 된다냥.
(b 초과인 첫 위치) - (a 이상인 첫 위치)
b 초과라는 게 핵심이라냥. b 이상으로 잡으면 b 와 같은 값들이
통째로 빠진다냥. 숨겨진 테스트가 이걸 확인한다냥.
[1, 3, 3, 3, 7, 9] 에서 a=3, b=3 이면 답은 3이라냥.
- 3 이상인 첫 위치 = 1
- 3 초과인 첫 위치 = 4
- 4 - 1 = 3 이라냥
n, a, b = map(int, input().split())
arr = list(map(int, input().split()))
# 경계 두 개의 차이를 출력한다냥k * k <= n 을 만족하는 가장 큰 k 를 출력한다냥.
여기서부터 답을 탐색한다냥. 배열이 없는데도 이분 탐색을 쓴다냥.
k 를 하나 정해두고 k * k <= n 인지 물어보면, 작은 k 는 전부 참이고
어느 지점부터 거짓이라냥. 그 경계를 찾는 거라냥.
lo = mid 형태를 쓰니 mid = (lo + hi + 1) // 2 라냥. +1 을 빼먹으면
무한 반복이라냥.
n 이 0일 수도 있다냥. 답은 0이라냥. lo 를 1부터 시작하면 틀린다냥.
n = int(input())
lo, hi = 0, 10**6
while lo < hi:
mid = (lo + hi + 1) // 2
# mid * mid 와 n 을 비교한다냥
pass
print(lo)오늘의 마지막이라냥. 랜선을 잘라 같은 길이 k개 이상을 만들 때, 한 개의 최대 길이를 구한다냥.
"k개 이상" 이라는 조건이 함정이라냥.
답이 되는 길이에서 정확히 k개가 나온다는 보장이 없다냥. 예를 들어 길이 10짜리 랜선 3개로 2개를 만들 때, 답은 10이지만 그 길이에서는 3개가 나온다냥.
개수가 == k 인지 확인하면 답을 못 찾는다냥. 반드시 >= k 로 판단하자냥.
숨겨진 테스트가 정확히 이걸 확인한다냥.
"최대 길이가 얼마냐"는 어렵지만, "길이 200이면 k개를 만들 수 있냐" 는 쉽다냥. 각 랜선을 200으로 나눈 몫을 다 더하면 되니까라냥.
made = sum(x // mid for x in arr)그리고 짧으면 되고 길면 안 되니, 되는 쪽의 끝을 찾으면 그게 답이라냥.
만들 수 없는 경우도 있다냥. 길이 1짜리 랜선 2개로 5개는 못 만든다냥.
그럴 땐 0 을 출력한다냥. lo 를 0부터 시작하면 자연히 처리된다냥.
n, k = map(int, input().split())
arr = list(map(int, input().split()))
lo, hi = 0, max(arr)
while lo < hi:
mid = (lo + hi + 1) // 2
# mid 길이로 k개 이상 만들 수 있냥?
pass
print(lo)다 풀었냥?
4번과 5번에서 배열이 없는데도 이분 탐색을 썼다는 게 느껴졌냥? 이분 탐색은 "정렬된 배열에서 찾는 기술"이 아니라 "되는 구간과 안 되는 구간의 경계를 찾는 기술" 이라냥. 이걸 알면 쓸 곳이 훨씬 넓어진다냥.
스스로 점검해보자냥
- 다섯 문제를 전부 채점기에서 통과했냥?
- 값 찾기와 경계 찾기의 세 가지 차이를 말할 수 있냥?
lo = mid를 쓸 때mid에+1을 붙이는 이유를 설명할 수 있냥?- 5번에서
== k가 아니라>= k여야 하는 이유를 설명할 수 있냥?
여기까지 오면 알고리즘의 기본기는 갖춘 거라냥. 훑기, 문자열, 누적, 정렬, 세기, 그리고 이분 탐색까지 여섯 개의 무기가 생겼다냥. 이제 문제를 봤을 때 "어떤 무기를 쓸까" 하고 고민할 수 있게 됐다냥. 정말 수고했다냥~