최장 증가 부분 수열 (LIS, Longest Increasing Subsequence) feat.kotlin

정의

어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 뽑아서 부분수열을 만들 수 있다. 이때, 만들어진 부분수열 중 오름차순으로 정렬된 길이가 가장 긴 수열을 최장 증가 부분 수열이라 한다.

예를 들어 다음 수열이 주어졌다고 하자.

 

---> 탐색을 한다 가정할때,

5 1 6 2 7 3 8

 

1 2 3 8
5 6 7 8

모두 길이가 4인 최장 증가 부분 수열이다.

 

문제로 익혀보기.

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

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

boj_no_11053

 

예시)

Arr = {10, 20, 10, 30, 20, 50}

LIS는 {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

필수적으로 필요한 부분.

 

일단, 기본적으로 배열을 --> 선형 탐색을 한다.

이때, i 일때, 수열을 다시 0 --> i 까지 재탐색을 한다. (2중 반복)

 

LISArr ( 원본 Arr을 i 만큼 탐색 했을 때, 해당 i에 LIS의 length를 저장하는 배열)

 

만약 원본 Arr이 예시일때, 

LISArr[0]이면  LIS의 원소는 {10}, 길이는 1이 된다.

LISArr[1]이면  LIS의 원소는 {10, 20}, 길이는 2이 된다.

LISArr[2]이면  LIS의 원소는 {10},  길이 1이 된다.

--> 10 20 10 이면 LIS가 증가하지 않기 때문에 쓰레기 값 1이 들어간다. 

LISArr[3]이면  LIS의 원소는 {10, 20, 30}, 길이 3이 된다.

 

i = 3일때,

LISArr {1, 2, 1, 3, X, X} 

 

*tempMaxLength  

 j가 (0 --> i) 까지 재탐색 하는 중 현재까지 구한 LIS의 길이의 최대값을 임시로 담음.

 

var n = 0
lateinit var arr: IntArray
lateinit var LISLengthArr: IntArray

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

    n = readLine().toInt()
    arr = readLine().split(" ").map { it.toInt() }.toIntArray()
    LISLengthArr = IntArray(n) { 0 }

    for (i in 0 until n) {
        var tempMaxLength = 0
        for (j in 0 until i) {
            // (arr[i] > arr[j]) 오름 차순 증가 이기 때문에 현재 숫자 보다 작아야 된며,
            // LIS 길이 값은 가장 크다면 갱신.
            if (arr[i] > arr[j] && tempMaxLength < LISLengthArr[j]) {
                tempMaxLength = LISLengthArr[j]
            }
        }
        // 위에서 선택된 arr[j]을 포함 하는 LISLengthArr[i] 값을 갱신.
        LISLengthArr[i] = tempMaxLength + 1
    }
//    println(LISLengthArr.joinToString(" "))
    println(LISLengthArr.maxOrNull())
    Unit
}