[Algotithm] Longest increasing subsequence

오늘은 Longest Increasing Subsequence(LIS)에 대해 알아보도록 하겠습니다.

주어진 수열(배열)에서 가장 긴 증가하는 부분 수열을 찾는 문제입니다.

문제 예시

길이가 n이며 배열의 원소는 정수 범위의 값을 갖는 배열 A가 있다고 가정합니다.

0 ≤ i < j ≤ n - 1 인 i와 j 가 있을 때, 항상 A[i] < A[j]를 만족하는 가장 긴 부분 수열의 길이를 찾아야합니다.

[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

이와 같은 수열이 있을 때, LIS는 아래와 같습니다.

[0, 2, 6, 9, 11, 15]
[0, 4, 6, 9, 11, 15]
[0, 2, 6, 9, 13, 15]
[0, 4, 6, 9, 13, 15]

이처럼 LIS는 여러 개가 될 수 있습니다.

접근법

문제를 해결하기위해 동적계획법과 이분 탐색 두가지 방식으로 접근이 가능합니다.

동적계획법(DP, Dynamic Programming)

배열의 각 원소에 대해 그 원소를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이를 기록하고 갱신합니다.

func LISofDP(_ nums: [Int]) -> Int {
    if nums.isEmpty { return 0 }

    var dpTable = Array(repeating: 1, count: nums.count)
    for i in 1..<nums.count {
        for j in 0..<i {
            if nums[i] > nums[j] {
                dpTable[i] = max(dpTable[i], dpTable[j] + 1)
            }
        }
    }
    return dp.max()!
}

let nums = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
print(LISofDP(nums)) // 6

 

DP를 활용할 경우 O(n^2)의 시간 복잡도를 갖습니다.

이분탐색

LIS를 유지하는 배열을 사용하고, 기존 배열의 원소를 차례대로 탐색합니다.

탐색한 원소가 LIS의 끝보다 크면 추가하고, 더 작거나 같다면 이분탐색을 사용하여 위치를 찾아 교체합니다.

func LISofBS(_ nums: [Int]) -> Int {
    var lis: [Int] = []
    
    for num in nums {
        if lis.isEmpty || lis.last! < num {
            lis.append(num)
        } else {
            var left = 0
            var right = lis.count - 1
            while left < right {
                let mid = (left + right) / 2
                if lis[mid] < num {
                    left = mid + 1
                } else {
                    right = mid
                }
            }
            lis[left] = num
        }
    }
    
    return lis.count
}

let nums = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
print(LISofBS(nums)) // 6

이분탐색의 경우 O(n*logn)의 시간 복잡도를 갖기 때문에 DP를 활용하는 것보다 더 효율적입니다.

주의해야할 것은 변수로 사용된 LIS가 실제 LIS가 아니라 단순히 길이를 구하기 위한 배열일 뿐이라는 것입니다.

 

이분탐색 과정을 로그로 확인해보면 다음과 같습니다.

lis = [0]                   // 0
lis = [0, 8]                // 8
lis = [0, 4]                // 4 : 8보다 작고, 8과 교체
lis = [0, 4, 12]            // 12
lis = [0, 2, 12]            // 2 : 12보다 작고, 4와 교체
lis = [0, 2, 10]            // 10 : 12보다 작고, 12와 교체
lis = [0, 2, 6]             // 6 : 10보다 작고, 10과 교체
lis = [0, 2, 6, 14]         // 14
lis = [0, 1, 6, 14]         // 1 : 14보다 작고, 2와 교체
lis = [0, 1, 6, 9]          // 9 : 14보다 작고, 14와 교체
lis = [0, 1, 5, 9]          // 5 : 9보다 작고, 6과 교체
lis = [0, 1, 5, 9, 13]      // 13
lis = [0, 1, 3, 9, 13]      // 3 : 13보다 작고, 5와 교체
lis = [0, 1, 3, 9, 11]      // 11 : 13보다 작고, 13과 교체
lis = [0, 1, 3, 7, 11]      // 7 : 11보다 작고, 9와 교체
lis = [0, 1, 3, 7, 11, 15]  // 15

 

Reference

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

Longest Increasing Subsequence (LIS) - GeeksforGeeks

 

Longest increasing subsequence - Wikipedia