[2022 하계 모각코] 7주차 1회 계획 및 결과

7주차 1회 계획 : 최장증가부분수열(LIS) 탐구

---

이번주는 최장증가부분수열알고리즘에 대해 탐구할 계획이다. 평소에는 기존에 알고 있는 알고리즘에서 확장적으로 알아나가려 했다. 이번 기회에 전혀 모르던 알고리즘을 집중적으로 파고들어 보았는데, 정말 신선한 경험이었다.

---

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

주어진 수열에서 순서대로 증가하는 가장 긴 부분수열이다.

예로 알아보자.

'1, 2, 7, 4, 3, 9' 의 수열이 있다.

증가하는 부분수열을 뽑아보면 '1, 7, 9', '2, 7, 9', '4, 9', '2, 4', ... 가 있다.

이 부분수열들 중 길이가 가장 긴 수열이 바로 최장증가부분수열이다.

위에서 주어진 수열에서의 LIS는 '1, 2, 7, 9', '1, 2, 4, 9,', '1, 2, 3, 9'가 있겠고, 그 길이는 4이다.

이때,  LIS는 보통 길이를 맞추는 문제를 내고, 그 길이를 가지는 수열을 알아내라는 문제는 많지 않다고 한다.

---

LIS를 구하는 방법

---

• 시간복잡도 : O(n^2)

sequence = [1, 2, 7, 4, 3, 9]
leng = len(sequence)
D = [0] * leng
for i in range(leng):
    D[i] = 1 #sequence[i] 로 끝나는 최장증가부분수열의 초기 길이
    for j in range(i):
        if sequence[i] > sequence[j]:
            D[i] = max(D[i], D[j]+1)
print(D)
>>> [1, 2, 3, 3, 3, 4]

 

arr 에서 각 원소들이 부분수열의 가장 끝 수가 되었을 때, 가질 수 있는 증가수열의 길이를 D에 담도록 했다.

수열에서 1을 끝으로 하는 부분수열을 따지면, 주어진 수열에서 1보다 앞에 있는 수는 없기 때문에 D[0] = 1이다.

수열에서 2를 끝으로 하는 부분수열을 따지면, 주어진 수열에서 2보다 앞에 있는 수, 1을 집어들고 D[1]과 D[0]+1을 비교해 더 큰 값을 D[1]로 설정한다. 반복문 처음부터 D[1] = 1로 초기화를 시켰으니 D[0]+1 = 1+1 = 2 를 D[1]로 설정할 것이다.

수열에서 7을 끝으로 하는 부분수열을 따지면, 주어진 수열에서 7보다 앞에 있는 수, 1을 집어들고 2에서와 마찬가지의 과정을 거친 뒤, D[2] = 2 로 설정될 것이다. 하지만 바로 다음, 2를 집어들고 max(D[2], D[1]+1) 에서 D[1]+1 = 2+1 = 3 이기 때문에 D[2] = 3 으로 설정된다.

이런 방식으로 주어진 수열(sequence)을 모두 살펴보며 D[i]값을 설정한다. 그 다음 D를 가지고 문제에서 원하는 답을 내놓을 수 있다.

하지만 N(수열의 길이)번 만큼 반복하는 반복문 안에서 주어진 수열을 1번, 2번, 3번, ..., N번 만큼 계속 돌아보기 때문에 N^2 만큼의 시간이 걸린다.

---

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

위 개념을 이용해 이 문제를 풀었다.

이 문제는 수열 A의 크기 N이 최대 1,000 이었기 때문에 N^2으로도 풀 수 있었다.

---

• 시간복잡도 : O(nlogn)

lower bound를 이용한 풀이 방법이다. LIS 수열을 제대로 알아내진 못하고, 그 길이만 정확히 구하는 알고리즘이다.

이전에 ANA 동아리에서 lower bound에 대해 특강을 들은 적이 있다. 그래서 다른 이의 블로그 글을 통해 복습하여 금방 코드를 짤 수 있었다.

def LowerBound(n, arr):
    l = -1
    r = len(arr)
    m = (l+r)//2
    while l+1 < r:
        m = (l+r)//2
        if arr[m] > n:
            r = m
        elif arr[m] < n:
            l = m
        else:
            break
    return m

sequence = [1,2,0,3,5,7,9,11,15,2]
leng = len(sequence)

D = [sequence[0]]
for i in range(1, leng):
    elem = sequence[i]
    idx = LowerBound(elem, D)

    if D[idx] < elem:
        if idx < len(D)-1:
            D[idx+1] = elem
        else:
            D.append(elem)
    else:
        D[idx] = min(D[idx], elem)
print(D)
>>> [0, 2, 3, 5, 7, 9, 11, 15]
print(len(D))
>>> 8

D는 arr에 대해서 최장증가부분수열을 적어놓는 변수이다. 이후에 D의 길이를 출력함으로써 LIS의 길이를 구할 수 있다.

하지만 위 코드로는 LIS를 정확히 알아낼 수 없다. 단지 그 길이만 빠르게 알아낼 뿐이다.

마지막에 출력한 D를 확인해보면 분명 '부분수열' 에는 어긋나는 결과를 출력하고 있다. 즉, 순서가 어긋났다는 것이다.

(0 다음에는 2가 15 뒤에 있다. 따라서 0 다음엔 2가 절대 나올 수 없다.)

하지만 lower bound(nlogn)를 이용해, sequence[i]가 D의 정확히 어디로 들어가야 할 지 빠르게 파악할 수 있다.

이 알고리즘의 핵심 아이디어는 이 글에 쓰지 않았다. 여기를 통해 더 잘 알 수 있을 것이다.

---

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

위 코드로 문제풀이에 성공했다.

---

오늘 참고한 사이트

LIS동영상강의(N^2), NlogN 아이디어

lower bound 사이트1, 사이트2