[알고리즘] 증가하는 최장 부분 수열(LIS)

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

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

 

LIS라는 명칭으로 잘 알려진 문제다.

결론부터 얘기하면 DP로 접근하여 풀 수 있다.

아래는 나의 답안 코드다.

n = int(input())
nums = list(map(int, input().split()))

lst = [0 for _ in range(n)]

for i in range(n):
    max_val = 0
    for j in range(i):
        if nums[j] < nums[i]:
            max_val = max(max_val, lst[j])

    lst[i] = max_val + 1

print(max(lst))

차근차근 살펴보면 일단 lst는 무엇을 의미할 지 알아야 한다.

lst[i]는 nums[i] 값을 마지막으로 갖는 부분 수열의 최대 길이 값이다.

 

코드를 보면 반복문을 돌면서 max_val을 업데이트 하는 식인데 여기서 max_val은 

nums[i]가 마지막 값으로 들어갈 수 있는 부분 수열 중 가장 긴 값이다.

 

반복문을 자세히 살펴보자.

반복문 안에 반복문이 하나 더 있다. 

여기서 nums[j] < nums[i] 조건을 만족한다면 nums[j]로 끝나는 수열에 nums[i]을 추가할 수 있다는 뜻이 될 것이다.

그렇게 들어갈 수 있는 경우가 여러가지 있을텐데 그때 lst[j]값을 살펴보면서 가장 큰 lst[j]을 찾는다.

최장 증가 부분 수열을 만드는 것이 목적이기 때문에 가장 큰 lst[j]을 찾고 lst[i]에는 lst[j]+1을 대입해주면 되는 것이다.

시간복잡도는 O(n2)이다.

 

예시가 없어 위의 설명만으론 이해하기 어려울 수 있으니 이해가 안되면 다른 문서를 참고하자.

 

 

 

++ nlog(n) 풀이

LIS는 워낙 well-known 문제이기도 하고 아이디어만으로 풀어내기는 쉽지가 않아 서치를 통해 방법을 참고하여 답을 구했다. 아래의 방법으로 nlog(n)에 문제를 풀 수 있을 뿐아니라 그 부분수열도 구해낼 수 있다. 

 

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

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

n = int(input())
nums = list(map(int, input().split()))
k = []

idx_table = [0 for _ in range(n)]

def binary_search(x):
    lo, hi = 0, len(k)-1
    while lo < hi:
        mid = (lo + hi) // 2
        if k[mid] < x: lo = mid + 1
        else: hi = mid
    return lo

for i in range(n):
    if not k:
        k.append(nums[i])
        idx_table[i] = len(k) -1
        continue

    if k[-1] < nums[i]:
        k.append(nums[i])
        idx_table[i] = len(k) -1
        
    elif k[0] > nums[i]:
        k[0] = nums[i]
    else:
        p = binary_search(nums[i])
        k[p] = nums[i]
        idx_table[i] = p

length = len(k)
lis = []
j = n-1
while j >= 0:
    if idx_table[j] == length-1:
        lis.append(nums[j])
        length -= 1
        if length == 0:
            break
    j -= 1

print(len(k))
lis.reverse()
print(*lis)