백준 11053번
https://www.acmicpc.net/problem/11053

문제

---

생각하기

---

• LIS : 가장 긴 증가하는 부분 수열을 찾는 문제이다

• DP와 이분탐색을 통해서 구현할 수 있다.

  • memoization를 사용해서 최적화를 진행하고 target값을 어디에 넣을 수 있는지 탐색하는 과정에서 이분탐색을 사용한다.

동작

결과

코드

---

Kotlin

Top-Down, BinarySearch

import java.io.*
import java.util.*

// input
private lateinit var br: BufferedReader

// variables
private var N = 0
private lateinit var arr: IntArray
private lateinit var memo: IntArray

fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    sb.append(LIS())
    return sb.toString()
} // End of solve()

private fun LIS(): Int {
    val list = ArrayList<Int>()
    list.add(arr[0])

    for (i in 0 until N) {
        topDown(list, i)
    }

    return list.size
} // End of LIS()

private fun topDown(list: ArrayList<Int>, n: Int): Int {
    if (memo[n] != -1) return memo[n]

    if (list[list.size - 1] < arr[n]) {
        list.add(arr[n])
        memo[n] = list.size
        return memo[n]
    } else {
        val idx = binarySearch(list, arr[n], 0, list.size - 1)
        list[idx] = arr[n]
        memo[n] = idx + 1
        return memo[n]
    }
} // End of topDown

private fun binarySearch(list: ArrayList<Int>, target: Int, low: Int, high: Int): Int {
    if (low > high) return low

    val mid = (low + high) / 2
    if (list[mid] < target) {
        return binarySearch(list, target, mid + 1, high)
    } else {
        return binarySearch(list, target, low, mid - 1)
    }
} // End of binarySearch

private fun input() {
    N = br.readLine().toInt()

    StringTokenizer(br.readLine()).run {
        arr = IntArray(N) {
            nextToken().toInt()
        }
    }

    memo = IntArray(N) { -1 }
} // End of input()

Bottom-Up, BinarySearch

import java.io.*
import java.util.*

// input
private lateinit var br: BufferedReader

// variables
private var N = 0
private lateinit var arr: IntArray
private lateinit var memo: IntArray

fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    sb.append(LIS())
    return sb.toString()
} // End of solve()

private fun LIS(): Int {
    val list = ArrayList<Int>()
    list.add(arr[0])

    for (i in 0 until N) {
        if (list[list.size - 1] < arr[i]) {
            list.add(arr[i])
        } else {
            val idx = binarySearch(list, arr[i], 0, list.size - 1)
            list[idx] = arr[i]
        }
    }

    return list.size
} // End of LIS()

private fun binarySearch(list: MutableList<Int>, target: Int, low: Int, high: Int): Int {
    if (low > high) return low

    val mid = (low + high) / 2
    if (list[mid] < target) {
        return binarySearch(list, target, mid + 1, high)
    } else {
        return binarySearch(list, target, low, mid - 1)
    }
} // End of binarySearch

private fun input() {
    N = br.readLine().toInt()

    StringTokenizer(br.readLine()).run {
        arr = IntArray(N) {
            nextToken().toInt()
        }
    }

    memo = IntArray(N)
} // End of input()