[백준 12015] 가장 긴 증가하는 부분 수열 2

문제 출처 : https://www.acmicpc.net/problem/12015

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

LIS(Longest Inceasing Sequence)란?

LIS는 Longest Increasing Subsequence의 약자로 최장 증가 수열 또는 최장 증가 부분수열이라고 합니다. LIS를 이해하기 위해서는 먼저 Increasing Subsequence 한글로 증가 부분수열을 알아야 합니다. 증가 부분수열을 말 그대로 증가하고 있는 부분 수열을 나타냅니다. 가령 [5, 1, 9, 2, 7, 3, 8, 4, 6] 이라는 리스트가 존재할때 여기서 증가하는 부분 수열을 찾아 보겠습니다.

[5, 9], [5, 7, 8], [1, 2, 7, 8] 등등 다양한 증가하는 부분수열이 존재합니다. 이중 가장 길이가 큰 최장 증가 부분 수열은 [1, 2, 3, 4, 6]이 됩니다. 이 최장 증가 부분 수열을 찾는 것이 이 알고리즘의 목표 입니다.

 

알고리즘 이해하기

LIS를 구하는 세그먼트 트리 방법 입니다. 세그먼트 트리의 다양한 활용을 위해 이 문제를 선택하였습니다. 세그먼트 트리로 푸는 방법도 이분 탐색과 크게 다르지 않습니다. 자신보다 1 작은 숫자의 LIS의 길이를 찾아 1씩 늘려주는 방식 입니다. [5, 1, 9, 2, 7, 3, 8, 4, 6] 리스트를 예로 확인해 보겠습니다.

첫 번째 숫자인 5보다 1 작은 4까지 LIS를 확인합니다.

가장 큰 숫자가 0이기 때문에 5의 인덱스에 1을 업데이트 합니다.

다음으로 1보다 1작은 숫자까지의 LIS를 확인합니다. 아무것도 없기 때문에 LIS는 0이고 1의 인덱스의 값도 1로 업데이트 합니다.

9가 들어오면 8까지의 LIS를 확인합니다. 8까지의 LIS 최대값은 1입니다. 따라서 9의 인덱스에 1을 더해 2가 됩니다.

다음으로 2가 들어옵니다. 1까지의 LIS 최대값은 1이기 때문에 2의 인덱스는 2가 됩니다.

다음으로 7이 들어 옵니다. 6까지의 최대값은 2 입니다. 따라서 7의 최대값은 3이 됩니다.

다음으로 3이 들어 옵니다. 2까지의 최대값은 2이기 때문에 3의 인덱스의 최대값은 3이 됩니다.

다음으로 8이 들어옵니다. 7까지의 최대값은 3이기 때문에 8의 인덱스는 4가 됩니다.

다음으로 4가 들어 옵니다. 3까지의 최대값은 3이기 때문에 4의 인덱스는 4가 됩니다.

마지막으로 6이 들어옵니다. 5까지의 최대값은 4이기 때문에 6의 인덱스는 5가 됩니다.

최종적으로 5가 가장 긴 증가하는 부분 수열이 됩니다. 

코드 작성하기

방금 알아본 내용을 코드로 작성해 보겠습니다.

입력 받기

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))

입력 숫자가 많기 때문에 readline으로 속도를 높여주었습니다. 다음으로 수열의 크기 N과 리스트 arr을 입력 받았습니다.

세그먼트 트리의 활용

ans = 0
for a in arr:
    max_len = query(0, a - 1)
    update(a, max_len + 1)
    ans = max(ans, max_len + 1)

print(ans)

lis를 구하는 방법은 위의 로직을 이용할 것입니다. 먼저 입력된 숫자 a보다 1 작은 숫자까지의 lis를 구해줍니다. query 함수를 사용하여 구해 줍니다. 구해준 lis 길이에 1을 더해 a 위치에 업데이트 합니다. query, update 함수가 빈번하게 사용되기 때문에 바텀업 세그먼트 트리를 이용할 것입니다. 그럼 세그먼트 트리 부분을 작성해 보겠습니다.

트리 만들기

N = 10 ** 6
size = 1
while size <= N:
    size <<= 1

tree = [0] * (2 * size)

이 문제에는 N의 크기의 최대값은 10 ** 6 입니다. N의 갯수는 5개인데 숫자는 1, 10, 100, 1,000, 10,000 이런식으로 들어올 수 있습니다. 따라서 N의 크기를 10 ** 6인 백만으로 늘려주었습니다. N의 크기를 늘려주기 싫다면 좌표 압축을 사용하여 최대값을 N이 되도록 해주어야 합니다. 여기서는 좌표압축을 사용하지 않기 위해 N을 백만으로 늘려주었습니다.

query 함수

def query(left, right):
    left += size
    right += size

    ans = 0
    while left <= right:
        if left % 2 == 1:
            ans = max(ans, tree[left])
            left += 1
        if right % 2 == 0:
            ans = max(ans, tree[right])
            right -= 1
        left //= 2
        right //= 2
    return ans

주어진 범위의 최대값을 구하는 단순한 형태의 query문 입니다. 바텀업 세그먼트 트리에 익숙하다면 어렵지 않게 이해가 가능합니다.

update 함수

def update(idx, num):
    idx += size
    tree[idx] = num 

    idx //= 2
    while idx:
        tree[idx] = max(tree[2 * idx], tree[2 * idx + 1])
        idx //= 2

인덱스에 숫자를 업데이트하는 단순한 업데이트문 입니다. 숫자에 해당하는 LIS의 길이를 업데이트 하는 것입니다.

전체 코드

전체 코드를 확인해 보겠습니다.

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))

N = 10 ** 6
size = 1
while size <= N:
    size <<= 1

tree = [0] * (2 * size)

def update(idx, num):
    idx += size
    tree[idx] = num 

    idx //= 2
    while idx:
        tree[idx] = max(tree[2 * idx], tree[2 * idx + 1])
        idx //= 2

def query(left, right):
    left += size
    right += size

    ans = 0
    while left <= right:
        if left % 2 == 1:
            ans = max(ans, tree[left])
            left += 1
        if right % 2 == 0:
            ans = max(ans, tree[right])
            right -= 1
        left //= 2
        right //= 2
    return ans        

ans = 0
for a in arr:
    max_len = query(0, a - 1)
    update(a, max_len + 1)
    ans = max(ans, max_len + 1)

print(ans)