[알고리즘] (Swift) 최강 증가 부분 수열 (LIS) 알고리즘 (DP, 동적계획법을 활용한 LIS)

최장 증가 부분 수열 (LIS,Longest Increasing Subsequence) 이란?

어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분 수열을 만들 수 있다. 이때 만들어진 부분 수열 중 오름차순으로 정렬된 가장 긴 수열을 "최장 증가 부분 수열"이라고 한다. - 나무위키 🌳

▷ 예시를 들어보자.

[ 3, 5, 7, 9, 2, 1, 4, 8]

다음과 같은 수열이 있다고 하자. 이 수열에서 몇 개의 수를 제거해서 부분수열을 만들 수 있다. 몇 개의 수를 제거해서 오름차순으로 이루어진 수열을 최장 증가 부분 수열이라고 하였는데, 즉, '공차'가 존재하지 않아도 부분수열이라고 본다는 것이다. (규칙적이지 않고 오름차순이면 된다는 뜻) 따라서 위 수열에서 도출될 수 있는 부분수열은 한 가지가 아니라, 몇 가지가 존재한다.

[3, 7, 9, 1, 4, 8] -- (5, 2 제거)
[7, 9, 1, 8] -------- (3, 5, 2, 4 제거)
[3, 5, 7, 8] -------- (9, 2, 1, 4 제거)
[1, 4, 8] ----------- (3, 5, 7, 9, 2 제거)

이렇게 도출될 수 있는 부분수열 중, 오름차순이면서, 가장 긴 길이를 갖고 있는 부분수열이 LIS 라고 한다. 

 

💁🏻‍♀️ LIS를 구하는 방법

LIS를 구하는 대표적인 방법은, DP(동적 계획법)과 이분탐색을 활용하는 두 가지의 방법이 있다. 아직은 이분탐색에 대한 완전한 개념을 공부하지 않았기 떄문에, 오늘은 DP를 활용한 LIS 구하는 방법에 대해서만 알아보겠다. (추후 이분탐색을 활용한 LIS 구하는 방법은 따로 다룰 예정이다.)

👉🏻 DP(동적 계획법) 이용해서 LIS 구하기 : O(N^2)

배열 D[i] 는 i번째 인덱스에서 끝나는 최장 증가 부분 수열의 길이를 의미한다. 부분수열 A의 i번째 요소가 어떤 증가 부분 수열의 마지막 값이 되기 위해서는 A[i]가 추가되기 전 증가 부분수얼의 마지막 값이 A[i]보다 작은 값이어야 한다. 따라서 A[i]를 마지막 값으로 가지는 가장 긴 증가 부분 수열의 길이는 A[i]가 추가될 수 있는 증가 부분 수열 중 가장 긴 수열의 길이에 1을 더한 값이 된다.

▷ 빠른 이해를 위해 예시를 보자.

[3, 5, 7, 9, 2, 1, 4, 8]

이 수열을 활용하여 알고리즘을 살펴보자. (알고리즘 규칙의 형성을 위해 i=0을 추가했고, i=0일때 D[0] = 0 이다.)

i=1 일 때를 살펴보자. A[1] = 3 이다. 3은 A[0] = 0 뒤에 붙을 수 있다. 따라서 D[1] = D[0] + 1 = 1 이다.

i=2일 때를 보자. A[2] = 5 이다. 5는 A[0] = 0, A[1] = 3 뒤에 붙을 수 있다. 이때 D[0] = 0, D[1] = 1 에서 D[1]이 가장 크다. 이 말은 A[1]=3 을 마지막 값으로 가지는 증가 부분 수열의 길이가 가장 길다는 뜻이다. A[2]가 가장 긴 부분 수열 뒤에 붙는게 가장 긴 증가부분수열이 될 수 있다. 따라서 D[2]=D[1]+1 = 2 이다.

i=3, i=4 일 때도, 위와 동일한 규칙성에 의해 모두 최장 증가 부분수열을 만들 수 있다. 따라서 D[3] = D[2] +1 = 3 이 되고, D[4] = D[3]+1 =4 가 될 것이다.

자 그럼 이제 i=5 일 때를 살펴보자. A[5] = 2 이므로, A[0] 뒤에 붙을 수 있다. 따라서 D[5] = D[0] + 1 = 1이 된다.

i = 6일때는 D[6] = 1 이므로, 마찬가지로 A[0] 뒤에 붙을 수 있다. 따라서 D[6] = D[0] +1 = 1 이 된다. i=7은 A[7] = 4 이므로, A[1] = 3 뒤에 붙을 수 있다. 따라서 D[7] = D[1] + 1 = 2 가 된다. 

마지막으로 i = 8 일때는, A[3] = 7 뒤에 붙을 수 있기 때문에, D[8] = D[3] +1 = 4 가 된다.

이렇게 해서 배열 D 를 모두 완성시켰다. D의 값들 중, 가장 큰 4가 해당 수열의 LIS 길이가 된다. 이렇게 DP 방식으로 문제를 풀다보면, i 개의 수열이 있을 때, i 번의 연산이 필요하므로, O(N^2)의 시간복잡도를 갖는다.

이 알고리즘을 코딩테스트에서 활용하기 위해서 코드 예제를 작성해보자. 스위프트 코드로 구현해보면 아래와 같다.

let A = [3, 5, 7, 9, 2, 1, 4, 8]
var D: [Int] = []

for k in 0..<A.count {
    D.append(1)
    for i in 0..<k+1 {
        if A[i] < A[k] {
            D[k] = max(D[k], D[i] + 1)
        }
    }
}

print(D)

위에서 D[i] 는 i 번째 인덱스에서 끝나는 최장 증가 수열의 길이를 의미한다. 값을 max 메서드를 활용하여 업데이트 해주었는데, 업데이트 해주는 기준은 다음과 같다.

1.  i 번째 인덱스에서 끝나는 최장 증가 부분 수열의 마지막에 A[k]를 추가했을 때의 LIS 길이와, 
2. 추가하지 않고 기존의 D[k] 값
3. 둘 중 더 큰 값으로 D[k] 를 업데이트 한다.

 

 

✍🏻 참고자료

https://velog.io/@seho100/%EC%B5%9C%EA%B0%95-%EC%A6%9D%EA%B0%80-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4LIS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4