[Swift] 백준 12015번: 가장 긴 증가하는 수열2

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

문제

수열 A에서 가장 긴 증가하는 부분 수열의 길이를 출력

제한사항

• 수열의 크기 N은 1,000,000 이하의 자연수
• 수열 A를 이루고 있는 A𝘅는 1,000,000 이하의 자연수

풀이

수열 A로 [10, 20, 10, 30, 20, 50]이 주어진 상황에서 가장 긴 증가하는 부분 수열은 [10, 20, 30, 50]으로 길이 4를 반환하면 된다.

DP로 풀게 되면 O(n²) 시간 복잡도를 가지게 된다. 이를 개선하기 위해서는 이진 탐색을 해야한다.

 

Longest Increasing Subsequence

위키의 LIS 내용을 보게 되면 알고리즘이 아닌 다양한 분야에서 연구되어 사용된다.

시간 복잡도는 O(n𝙡𝙤𝙜n)로 풀 수 있다.

흐름

반복문으로 수열 A의 element를 확인한다. element이 LIS 배열의 마지막 원소보다 크면 LIS에 넣어주고 그렇지 않으면 binary search를 통해 찾은 위치에 넣어준다. 그리고 마지막에 LIS의 길이를 알 수 있게 된다. 이렇게만 설명해서는 이해가 너무 어려웠다. "LIS 배열이 아닌데?" 라는 의문을 가지게 될 것이다.

 

위키에서 나오는 LIS 배열을 구하는 것은 최대 길이를 구하는 것보다는 더 복잡하다. 위키에서 나오는 방법으로는 길이에 따른 배열을 가지는 2차원 배열이 존재한다. LIS의 길이가 1일 때 [0], 2일 때는 [0,2], 3일 때는 [0, 2, 6] 등 배열을 가지게 된다. binary search로 찾은 위치에 해당하는 배열을 고친다.

 

위에서 어떻게 LIS를 구하는지 알고나면 LIS를 1차원 배열로 표현해도 되는지 알게 된다. 간단하게 그림으로 표현해보자면 아래와 같다. 

더 자세한 과정은 위키에 gif 타입 그림으로 확인할 수 있다.

4를 만났을 때, [0, 4]가 되는 과정

 

최종적으로 LIS는 아래와 같은 2차원 배열을 갖게 된다.

각 길이에 따른 최종 LIS 배열

 

하지만 알고리즘 문제에서 요구하는 것은 최종 길이만 구하면 된다.

LIS 배열을 1차원으로 표현하되 내부 원소가 달라지더라도 LIS의 길이는 변함이 없게 된다.

그렇기에 아래와 같이 반복문으로 [0, 8, 4, 12, 2, 10, 6, 14] 까지 진행했을 경우에는 LIS의 최종 길이는 4가 된다.

그 과정은 아래의 그림과 같다.

 

코드

import Foundation

let N = Int(readLine()!)!
var A = readLine()!.split(separator: " ").map { Int($0)! }
var LS = [Int]()

for a in A {
    if LS.last == nil || LS.last! < a {
        LS.append(a)
    } else {
        var start = 0, end = LS.count - 1, mid = 0
        while start <= end {
            mid = (start + end) / 2
            if LS[mid] < a {
                start = mid + 1
            } else {
                end = mid - 1
            }
        }
        LS[start] = a
    }
}

print(LS.count)