[알고리즘] 가장 긴 증가하는 부분 수열 구하기

수열 A = { 10, 20, 40, 30, 1, 3, 90 } 이 주어졌을 때 가장 긴 증가하는 부분 수열(LIS)을 구하는 알고리즘을 알아본다.

LIS 를 구하는 방법은 총 세 가지 정도가 있다.

1. 완전 탐색을 이용하여 LIS 구한다. (시간 복잡도 : O(N^2))

2. DP 를 이용하여 LIS 구한다. (시간 복잡도 : O(N^2))

3. 이분탐색을 이용하여 LIS 를 구한다. (시간 복잡도 : O(NlogN))

 

문제에서 N 의 개수가 10,000 개까지 일 경우 1번 혹은 2번의 방법으로 구할 경우 1초 내에 결과를 얻을 수 있다.

2번 DP 방법은 아직 완전히 익숙하지 않아 완전 탐색에 대한 알고리즘을 우선 기술 한다.

완전 탐색을 이용한 LIS 구하기

1. 입력으로 주어지는 수열을 A 배열에 저장한다.

2. seq(LIS 개수) 를 저장하는 배열을 A 와 같은 크기의 배열로 선언한다.

3. 2번의 seq 배열의 seq[0] = 1 로 저장한다.

4. A 배열을 1 부터 N - 1 까지 탐색한다.

5. 현재 index(i) 의 값인 A[i] 에 대해서 (i - 1) 부터 0까지 탐색하여 A[i] > A[j] 일 경우 seq[j] 값에 1을 더해서 저장하는데

LIS 의 경우 가장 긴 수열의 개수이므로 result 를 선언하여 Max 값을 저장한다.

for (j in (i - 1) downTo 0 step 1) {
    if (current > arr[j]) {
        result = Math.max(result, seq[j] + 1)
    }
}

6. 5번에서 찾은 Max result 값을 seq[i] 에 저장한다.

7. 4 ~ 6 과정을 반복하여 모두 탐색한 뒤 seq 의 최대 값을 구한다.

코드

import java.io.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val N = br.readLine().toInt()
    val arr = br.readLine().split(" ").map { it.toInt() }.toIntArray()
    val seq = IntArray(N) { 0 }
    seq[0] = 1

    for (i in 1 until N) {
        val current = arr[i]
        var result = 1

        for (j in (i - 1) downTo 0 step 1) {
            if (current > arr[j]) {
                result = Math.max(result, seq[j] + 1)
            }
        }

        seq[i] = result
    }

    for (s in seq) {
        print("$s ")
    }
    println()
}

문제에서 N 의 개수가 10,000 개를 넘을 경우 시간 초과가 발생할 수 있기 때문에 3번의 이분탐색을 이용하여 LIS 를 구한다.

이분 탐색을 이용한 LIS 구하기

1. 결과를 저장한 list 배열을 선언하고 Int.MAX_VALUE 로 초기화 한다.

2. list[0] = A[0] 값을 저장한다.

3. 1부터 (N-1)까지 아래의 과정으로 탐색한다.

4. list[index] < A[i] 일 경우 list[++index] 에 A[i] 값을 저장하고 다음 index 를 탐색한다.

5. list[index >= A[i] 일 경우 A[i] 값을 list 의 어디에 넣을 지를 이분 탐색을 이용하여 target index 를 찾아서 값을 넣는다.

6. list 를 출력시 Int.MAX_VALUE 가 아닌 값의 개수를 출력한다.

import java.io.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val N = br.readLine().toInt()
    val arr = br.readLine().split(" ").map { it.toInt() }.toIntArray()
    val list = IntArray(N) { Int.MAX_VALUE }
    list[0] = arr[0]
    var index = 0

    for (i in 1 until N) {
        if (list[index] < arr[i]) {
            list[++index] = arr[i]
        } else {
            // 이분탐색을 이용해서 넣을 위치를 찾는다.
            val target = binarySearch(list, arr[i])
            list[target] = arr[i]
        }
    }

    for (l in list) {
        print("$l ")
    }
    println()
}

private fun binarySearch(arr: IntArray, target: Int): Int {
    var start = 0
    var end = arr.size - 1

    while (start <= end) {
        val mid = (start + end) / 2

        if (arr[mid] < target) start = mid + 1
        else if (arr[mid] > target) end = mid - 1
        else return mid
    }

    return start
}