상한선(upper_bound) & 하한선(lower_bound) feat.kotlin

이진탐색의 응용으로 자주 나오지는 않지만, 알아두면 유용하고 반대로 모르면 구현자체가 쉽지 않을 수도 있다.

 

*이진탐색의 응용으로 반드시 오름차순 정렬은 기본적으로 되어있는 배열 및 리스트를 이용한다.

 

상한선 (upper_bound)

 - key 보다 "큰 값"이 가장 처음 나오는 index

val arr = arrayOf(1, 2, 2, 3, 3, 3, 4, 5, 5, 6, 7, 7)

 

위 와같은 배열이 있다면 key = 6이라면 상한선은 무엇일까?

첫번째 7인 index 10일 것이다.

 

key = 7 또는 그 이상의 값이라면 상한선은 배열의 마지막 Index + 1, 반대로 배열의 최소값이 들어온다면 무조건 index 0이다.

 

여기 핵심적으로 봐야할것 

 

1.  조건을 만족하는 key값을 찾기 위해 left는 right를 넘을 수 없습니다.

key 보다 큰 값을 가르키는 right index보다 작은 값을 가르키는 left index가 같아 진다라는 것은 곧 key를 찾은 것이기 때문이다.

그래서 우리가 찾는건 "key보다 큰 값이 처음 나오는 index"이다. 

while (left < right) {
...
}

 

2. 이진탐색하고 다른 부분은 현재 검사하고 있는 index (mid)가, key보다 크다면, 

 right = mid - 1이 아니라 1칸 덜 줄어든 (일단 커야되니까) mid로 할당된다.

그리고 (arr[mid] == key)처리하는 분기는 없어야 한다.

if (arr[mid] > key) {
    right = mid
} else {
    left = mid + 1
}

 

code

fun upperBound(arr: Array<Int>, start: Int = 0, end: Int = arr.size, key: Int): Int {
    var left = start
    var right = end

    while (left < right) {
        val mid = (left + right) / 2

        if (arr[mid] > key) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return right
}

fun main() {
    val arr = arrayOf(1, 2, 2, 3, 3, 3, 4, 5, 5, 6, 7, 7)
    println(upperBound(arr, key= 6))
    println(upperBound(arr, key= 10))
    println(upperBound(arr, key= 0))

}

 

하한선 (lower_bound)

 - key 보다 "크거나 같은 값" 중 가장 처음 나오는 index

 

중요하게 봐야될 점은 상한선과 유사한데, while 반복문 안쪽의

if (arr[mid] >= key) {
            right = mid
        }

이 부분이다.

정의에 따라서 "크거나 같은 값" 중 

같은이 추가되었다 보면된다.

 

code

fun lowerBound(arr: Array<Int>, start: Int = 0, end: Int = arr.size, key: Int): Int {
    var left = start
    var right = end

    while (left < right) {
        val mid = (left + right) / 2

        if (arr[mid] >= key) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return right
}

fun main() {
    val arr = arrayOf(1, 2, 2, 3, 3, 3, 4, 5, 5, 6, 7, 7)
    println(lowerBound(arr, key = 3))
    println(lowerBound(arr, key = 0))
    println(lowerBound(arr, key = 8))
}

 

예시문제

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

7795번: 먹을 것인가 먹힐 것인가

 A의 크기가 B보다 큰 쌍이 몇 개나 있는지

 (1 ≤ N, M ≤ 20,000) 

단순히 A의 모든 원소를 각각 반복하면서 B의 모든 원소와 각각 비교하면 모든 쌍을 구할 수 있다.

하지만 이렇게되면 20_000 * 20_000 = 400_000_000 최악의 경우 4억번의 반복 횟수가 생기기 때문에 시간초과가 생긴다.

즉, 단순 2중 반복문을 사용하면 안된다는 것.

 

일단 "크기"의 순서쌍 이기 때문에 먹이가 되는 B집단을 정렬한다.

자신과 "같거나 큰것"은 못 먹는다 그럼 lowerBound를 쓴 결과의 Index는 이전은 "무조건 작음"

 

code

var n = 0
var m = 0

lateinit var arrA: Array<Int>
lateinit var arrB: Array<Int>

fun lowerBound(key: Int): Int {

    var left = 0
    var right = arrB.size

    while (left < right) {
        val mid = (left + right) / 2

        if (arrB[mid] >= key) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return right
}

fun main() = with(System.`in`.bufferedReader()) {

    val tc = readLine().toInt()
    repeat(tc) { _ ->
        val info = readLine().split(" ").map { it.toInt() }
        n = info[0]
        m = info[1]

        arrA = readLine().split(" ").map { it.toInt() }.toTypedArray()
        arrB = readLine().split(" ").map { it.toInt() }.toTypedArray()
        arrB.sort()

        var cnt = 0
        for (i in 0 until arrA.size) {
            val idx = lowerBound(arrA[i])
            cnt += idx
        }
        println(cnt)
    }
    Unit
}

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

 

12015번: 가장 긴 증가하는 부분 수열 2

 

 

문제분석

LIS 를 사용할때 DP로 풀면 시간복잡도가 O(N^2)이지만,  lowerBound를 사용하면 그 시간을  O(N logN)으로 줄일 수 있다.

단, 아래와같이 그 길이를 알수는 있지만, 어떤 요소로 LIS가 구성되어 있는지는 알 수 없다. 

var n = 0
lateinit var arr: IntArray
val lis = mutableListOf<Int>()

fun lowerBound(key: Int): Int {
    var left = 0
    var right = lis.size

    while (left < right) {
        val mid = (left + right) / 2

        if (lis[mid] >= key) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return right
}

fun main() = with(System.`in`.bufferedReader()) {
    n = readLine().toInt()
    arr = readLine().split(" ").map { it.toInt() }.toIntArray()

    lis.add(arr[0])
    for (i in 1 until arr.size) {
        if (arr[i] == 0) continue
        if (arr[i] > lis.last()) {
            lis.add(arr[i])
        } else {
            val idx = lowerBound(arr[i])
            lis[idx] = arr[i]
        }
    }
    println(lis.size)
}