Binary Search
정렬되어 있는 배열에서 특정 데이터를 찾기 위해 탐색 범위를 절반으로 줄여나가며 찾는 탐색 방법
탐색을 진행할 수록 범위는 절반으로 줄어들기 때문에 시간복잡도는 O(logN)이다
Parametric Search
최적화 문제를 결정 문제로 바꾸어 해결하는 것
최적화 문제 : 조건을 만족하는 특정 수의 최소 / 최댓값을 구하는 문제
문제 예시 : 어떤 수열에서 30보다 큰 수를 찾는다 할 때 그 중 제일 작은 수는 무엇인가?
결정 문제로 바꾸기 (yes or no로 답을 내릴 수 있는 문제): 어떤 수 x는 30보다 큰가?
결정 문제로 바꾸면 이분 탐색을 활용하여 탐색 범위를 좁혀가며 답을 효율적으로 찾을 수 있다.
이분 탐색 활용 문제 풀기
BOJ 1920. 수 찾기
직접 구현한 코드
import java.io.*
import java.util.*
private var n = 0
private lateinit var numbers: List<Int>
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val bw = BufferedWriter(OutputStreamWriter(System.out))
n = readLine().toInt()
numbers = readLine().split(" ").map { it.toInt() }.sorted()
// 탐색
var m = readLine().toInt()
val st = StringTokenizer(readLine())
while (m-- != 0) {
val target = st.nextToken().toInt()
bw.write("${binarySearch(target)}\n")
}
bw.close()
}
private fun binarySearch(target: Int): Int {
var start = 0
var end = n-1
while (start <= end) {
val mid = (start + end) / 2
if (numbers[mid] < target)
start = mid + 1
else if (numbers[mid] > target)
end = mid - 1
else return 1
}
return 0
}내장함수 binarySearch() 사용
import java.io.*
import java.util.*
private var n = 0
private lateinit var numbers: List<Int>
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val bw = BufferedWriter(OutputStreamWriter(System.out))
n = readLine().toInt()
numbers = readLine().split(" ").map { it.toInt() }.sorted()
// 탐색
var m = readLine().toInt()
val st = StringTokenizer(readLine())
while (m-- != 0) {
val target = st.nextToken().toInt()
if (numbers.binarySearch(target) >= 0)
bw.write("1\n")
else bw.write("0\n")
}
bw.close()
}값을 찾을 경우 : 찾은 위치 인덱스 반환
찾지 못할 경우 : -(타겟보다 큰 근삿값의 인덱스) - 1 반환
찾지 못한 경우 예를 들자면
arr = [1, 3, 5, 7], target = 2 일 때 출력은 -2가 나온다
-(2보다 큰 근삿값 3의 인덱스) - 1 = -2다.
상근이가 가진 N개의 숫자 카드 중 M이 적힌 카드가 몇개인지 출력하는 문제
중복되는 값의 범위를 특정하는 방법
1. M이 최초로 등장하는 위치를 구한다
2. M보다 큰수가 최초로 등장하는 위치를 구한다
3. 2 결과값 - 1 결과값 = 중복되는 값의 수
1 과정 구현 : M 이상의 값이 처음 등장하는 위치
수열에 있는 모든 값이 M보다 작을 수도 있기 때문에 end 값을 수열의 크기보다 하나 더 크게 설정해준다.
범위 : start = 0 ~ end: n
target < mid 일 경우 : tartget은 mid보다 큰 범위 안에 있을 가능성이 있다 -> start = mid + 1
target >= mid 일 경우 : target은 mid 이하의 범위 안에 있을 가능성이 있다 -> end = mid
private fun lowerIdx(target: Int): Int {
var start = 0
var end = n
while (start < end) {
val mid = (start + end) / 2
if (list[mid] >= target)
end = mid
else start = mid + 1
}
return start
}
2 과정 구현 : M보다 큰 수가 최초로 등장하는 위치 구하기
범위 : 1과 같음
target < mid 일 경우 : start = mid + 1
target > mid 일 경우 : end = mid
private fun upperIdx(target: Int): Int {
var start = 0
var end = n
while (start < end) {
val mid = (start + end) / 2
if (list[mid] > target) end = mid
else start = mid + 1
}
return start
}
필요한 랜선의 개수 N : 1 ~ 10^5
가진 랜선의 수 K : 1 ~ 10^3
랜선의 길이 : 1 ~ 2^31 -1
가진 랜선을 잘라 N개의 랜선을 만든다고 할 때, 만들 수 있는 최대 랜선의 길이를 구하라
랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다.
최적화 문제를 결정 문제로 바꾸어 답의 분포 확인하기
"가진 랜선을 잘라 N개의 랜선을 만든다고 할 때, 만들 수 있는 최대 랜선의 길이를 구하라"
이 문제를 좀 더 쉽게 해결하기 위해 결정문제로 바꾼다."가진 랜선들을 길이 x만큼씩 잘랐을 때 N개 이상의 랜선을 만들 수 있는가?"
랜선은 짧게 자를 수록 더 많이 만들 수 있기 때문에 일정 범위를 넘어서면 N개만큼 랜선을 만들 수 없을 것이다.
그렇기 때문에 위 결정 문제에 대한 답은 TTTTTFFFFF 이런식으로 분포하게 된다.
while (lo + 1 < hi) 조건으로 이분 탐색을 진행한다면
lo+1 = hi 일때 탐색이 종료될 것이고,
최종적으로 오름차순 되어 있기 때문에 lo는 T 중 제일 큰 T값, hi는 F값 중 제일 작은 F값을 가지게 될 것이다.
문제에서는 최대 랜선의 길이를 구하라고 했기 때문에 lo 값을 반환하면 된다.
TTTTTFFFFF 분포에서 T쪽은 1 ~ 2^31-1 범위를 포함해야 하고 F쪽은 그보다 커야 lo 값을 반환했을 때 정답이 나올 수 있기 때문에
hi는 lo보다 1 더 커야 한다. 따라서 초기값은 lo = 1, hi = 2^31이 된다.
import java.io.*
import java.util.*
import kotlin.math.pow
// n개를 만들 수 있는 최대 랜선의 길이
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val st = StringTokenizer(readLine())
val k = st.nextToken().toInt() // 가진 랜선의 수
val n = st.nextToken().toInt() // 필요한 랜선의 수
val arr = LongArray(k)
repeat(k) {
arr[it] = readLine().toLong()
}
arr.sort()
var lo: Long = 1
var hi: Long = 2.0.pow(31).toLong()
while (lo + 1 < hi) {
val mid: Long = (lo + hi) / 2
var sum: Long = 0
for (l in arr) {
sum += (l / mid)
}
if (sum < n) hi = mid
else lo = mid
}
println("$lo")
}
import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val bw = BufferedWriter(OutputStreamWriter(System.out))
val n = readLine().toInt()
val list = readLine().split(" ").map { it.toInt() }.sorted()
var m = readLine().toInt()
val st = StringTokenizer(readLine())
while (m-- != 0) {
val target = st.nextToken().toInt()
if (list.binarySearch(target) >= 0)
bw.write("1 ")
else bw.write("0 ")
}
bw.close()
}
import java.io.*
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
var st = StringTokenizer(readLine())
var nA = st.nextToken().toInt()
var nB = st.nextToken().toInt()
val listA = mutableListOf<Int>()
st = StringTokenizer(readLine())
while (nA-- != 0) {
listA.add(st.nextToken().toInt())
}
st = StringTokenizer(readLine())
val listB = mutableListOf<Int>()
// mlogm
while (nB-- != 0) {
listB.add(st.nextToken().toInt())
}
// mlogm
listB.sort()
val result = mutableListOf<Int>()
repeat(listA.size) { i ->
if (listB.binarySearch(listA[i]) < 0)
result.add(listA[i])
}
// mlogm
result.sort()
val bw = BufferedWriter(OutputStreamWriter(System.out))
bw.write("${result.size}\n")
repeat(result.size) { i->
bw.write("${result[i]} ")
}
bw.close()
}
시간과 심사 받을 수 있는 사람 수는 비례하는 관계이며, 범위는 아래와 같이 잡았다.
start : times에서 가장 작은 값
end : times에서 가장 큰 값 * n(사람수)
1. 이분 탐색 전 정렬을 수행한다.
2. 시간이 mid일 때 몇 사람을 심사할 수 있는지 확인한다.
3-1. 심사할 수 있는 사람 수보다 N이 더 작은 경우 mid 전 범위는 볼 필요가 없어지니 탐색 대상에서 제거한다
-> if(cnt < N) start = mid + 1
3-2. 심사할 수 있는 사람 수가 N보다 더 큰 경우 mid보다 큰 범위는 탐색 대상에서 제거한다.
N이 mid와 같은 경우에도 최솟값을 찾아야 하기 때문에 mid보다 작은 쪽을 탐색하도록 설정한다.
-> if(cnt >= N) end = mid - 1
탐색을 마친 후 최솟값은 end + 1에서 얻을 수 있다.
계산하면서 오버플로우가 일어날 수 있기 때문에 int가 아니라 Long 타입을 쓰도록 한다
class Solution {
fun solution(n: Int, times: IntArray): Long {
times.sort()
var start: Long = times[0].toLong()
var end: Long = times[times.lastIndex] * n.toLong()
while (start <= end) {
var cnt: Long = 0L
val mid: Long = (start + end) / 2
for (t in times) {
cnt += mid / t
}
if (cnt >= n) {
end = mid - 1
}
else start = mid + 1
}
return end + 1
}
}
True 의 범위는 과자를 나누줄 수 없는 경우도 포함해서 0 ~ 1,000,000,000이다.
import java.util.*
import java.io.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val max = 1000000000L
var st = StringTokenizer(readLine())
val m = st.nextToken().toInt() // 조카의 수
val n = st.nextToken().toInt() // 과자의 수
st = StringTokenizer(readLine())
val snacks = IntArray(n)
repeat(n) {
snacks[it] = st.nextToken().toInt()
}
var lo: Long = 0
var hi: Long = max + 1
while (lo + 1 < hi) {
val mid = (lo + hi) / 2
var sum: Long = 0
for (snack in snacks) {
sum += (snack / mid)
}
if (sum < m) hi = mid
else lo = mid
}
println("$lo")
}참고
[실전 알고리즘] 0x13강 - 이분탐색
안녕하세요, 이번 시간에는 이분탐색을 배워보도록 하겠습니다. 사실 이분탐색의 개념 자체는 그렇게 어렵지는 않습니다. 초등학생 정도만 되어도 업다운게임같은걸 아주 재밌게 즐길 수 있고,
blog.encrypted.gg
https://blog.naver.com/jinhan814/222607789392
Theme 09. 이분 탐색(Binary Search)
[개념] (목차 : https://blog.naver.com/jinhan814/222439906974) 이번 글에서는 이분 탐색의 원리와 구현,...
blog.naver.com