77. Longest Increasing Subsequence

최장 증가 부분수열(Longest Increasing Subsequence, LIS)은 수열의 부분 수열 중 값이 오름차순으로 나오면서 가장 긴 것을 말한다. 부분 수열은 원래의 수열에서 몇 개의 원소를 제거한 뒤 남는 수열을 의미하며, 연속되지 않는 원소들이 남을 수도 있다.

 

예를 들어 다음과 같은 수열 $a$가 있을 때 이 수열의 LIS는 $\{2, 4, 6, 7\}$이다.

$$a = \{5, {\color{Red}2}, 6, {\color{Red}4}, 8, 3, {\color{Red}6}, {\color{Red}7}\}$$

LIS의 원소들은 단조증가하므로 LIS에는 같은 원소가 두 번 이상 나타날 수 없다. 또한 한 수열에 두 개 이상의 LIS가 존재할 수도 있다. 예를 들어 수열 $a$가 다음과 같을 경우 LIS는 $\{3, 4, 6, 7\}, \{3, 4, 5, 7\}, \{2, 4, 6, 7\}, \{2, 4, 5, 7\}$로 총 $4$개 존재한다.

$$a = \{4, 7, 3, 2, 4, 6, 5, 7\}$$

---

길이가 $n$인 수열 $a$가 주어졌을 때 LIS의 길이는 다음과 같이 구할 수 있다. 기본적으로 각각의 원소에 대해 '그 원소를 마지막 원소로 하는 증가 부분수열의 최대 길이'를 구한 다음 그중 최댓값을 구하면 그 값이 LIS의 길이가 된다. 즉, 다음 식에서 $b_i$의 최댓값이 수열 $a$의 LIS의 길이와 같다.

$$b_1 = 1, b_i = \max \begin{cases} b_j, & a_j \ge a_i \\ b_j+1, & a_j < a_i \end{cases} (1 \le j < i \le n)$$

각각의 $b_i$를 구하는 가장 간단한 방법은 앞쪽의 $b_j$를 하나씩 확인하는 방법이다. 다음과 같이 구현할 수 있다.

int lis(int n)
{
    int m = 1;
    b[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        for(int j = 1; j < i; j++)
        {
            if(a[i] > a[j])b[i] = max(b[i], b[j] + 1);
            else b[i] = max(b[i], b[j]);
        }
        m = max(m, b[i]);
    }
    return m;
}

이 방법의 시간복잡도는 $\Theta(n^2)$이다. 만약 $n$이 크다면 이분 탐색을 이용하여 LIS의 길이를 더 빠르게 구할 수 있다. $b_i$를 구할 때 $b_i = k$가 되는 인덱스 $i$에 대해 $a_i$의 최솟값 $c_k$를 저장해 놓으면 다음 $b_i$를 구할 때 이 정보를 이용할 수 있다. $b_i$는 $c_k \ge a_i$인 최소의 $k$와 같고, $c_k$가 항상 오름차순으로 유지되므로 이분 탐색으로 원하는 $k$를 찾아낼 수 있다. 구현은 다음과 같으며 이 방법의 시간복잡도는 $\Theta(n \text{ lg } n)$이다.

#define INF (1<<30)
int lis(int n)
{
    c[0] = -INF;
    fill(c + 1, c + n + 1, INF);
    for(int i = 1; i <= n; i++)
    {
        int k = lower_bound(c, c + n + 1, a[i]) - c;
        b[i] = k;
        c[k] = min(a[i], c[k]);
    }
    return lower_bound(c, c + n + 1, INF) - c - 1;
}

INF의 값은 모든 $a_i$보다 크기만 하면 되고, -INF의 값은 모든 $a_i$보다 작기만 하면 된다. 문제의 입력 제한을 보고 적당히 크게 잡으면 어떤 값으로 해도 상관없다. 사실 이렇게 되면 $b_i$는 별로 의미가 없으므로 $8$행의 $b[i] = k;$ 문장을 빼도 된다.

---

어떤 문제에서는 LIS의 길이뿐 아니라 LIS 자체를 구해야 할 때도 있는데(때때로 이 과정을 역추적이라고도 한다), 이때 하기 쉬운 실수가 위의 코드의 실행이 끝난 다음의 $c$ 배열에서 INF가 아닌 부분을 차례로 출력하는 것이다. 예를 들어 수열 $a = \{5, 2, 3, 7, 6, 8, 4\}$일 경우 위의 코드를 실행한 다음 $c$ 배열은 $[2, 3, 4, 8, \infty, \infty, \infty]$이 되는데, 수열 $\{2, 3, 4, 8\}$은 $a$의 부분 수열이 아니다. 이렇게 되는 이유는 뒤쪽 원소들에 의해서 $c$ 배열의 앞쪽 원소들의 값이 계속 변하기 때문이다. 따라서 변하기 전의 값을 알고 있어야 하며, 각각의 원소에 대해서 그 원소를 포함하는 최장 증가 부분수열에서 그 원소의 바로 앞에 나온 원소를 알고 있으면 된다. 설명이 간단하지만은 않은데, 더 자세히 이해하려면 구현을 참고하는 것을 추천한다.

#define INF (1<<30)
stack<int>S;
int lis(int n)
{
    c[0] = -INF;
    fill(c + 1, c + n + 1, INF);
    fill(d + 1, d + n + 1, 0);
    for(int i = 1; i <= n; i++)
    {
        int k = lower_bound(c, c + n + 1, a[i]) - c;
        if(a[i] < c[k])
        {
            c[k] = a[i];
            d[k] = i;
            p[i] = d[k - 1];
        }
    }
    int k = lower_bound(c, c + n + 1, INF) - c - 1;
    for(int x = d[k]; x; x = p[x])S.push(a[x]);
    return k;
}

이 코드를 실행하면 스택 $S$에 $a$ 배열의 LIS가 역순으로 들어간다. 따라서 원소를 하나씩 뽑으면서 늘어놓으면 $a$의 LIS가 된다.

 

[연습문제]

 

BOJ 11053. 가장 긴 증가하는 부분 수열 (Silver II)

시간복잡도 $\Theta(n^2)$으로 LIS를 구해도 된다.

 

BOJ 11722. 가장 긴 감소하는 부분 수열 (Silver II)

LIS를 구할 때의 과정을 조금만 변형하면 LIS와 별로 다르지 않게 최장 감소 부분수열도 구할 수 있다.

 

BOJ 14002. 가장 긴 증가하는 부분 수열 4 (Gold IV)

위에서 설명한 방법대로 LIS를 찾는다.

 

BOJ 11054. 가장 긴 바이토닉 부분 수열 (Gold III)

각각의 인덱스 $i$에 대해 $a_i$를 마지막 원소로 하는 최장 증가 부분수열의 길이와 $a_i$를 첫 번째 원소로 하는 최장 감소 부분수열의 길이를 구하면 이를 바탕으로 가장 긴 바이토닉 부분 수열의 길이를 구할 수 있다.

 

BOJ 12015. 가장 긴 증가하는 부분 수열 2 (Gold II)

$n$의 제한이 커져서 $\Theta(n \text{ lg } n)$ 시간에 LIS를 구해야 한다. 위에서 설명한 대로 하면 된다.

 

BOJ 14003. 가장 긴 증가하는 부분 수열 5 (Platinum V)

$\Theta(n \text{ lg } n)$ 시간에 LIS를 구하고 위에서 설명한 방법대로 LIS를 찾으면 된다.

 

BOJ 2568. 전깃줄 - 2 (Platinum V)

전깃줄을 A 전봇대에 연결된 위치 순서대로 정렬하고 전깃줄이 B 전봇대에 연결된 순서를 수열로 간주하면 이 수열의 LIS를 구하면 된다. LIS를 구한 다음 그 전깃줄이 A 전봇대에 연결되는 위치까지 구해야 하므로 위 문제들에 비해 구현이 조금 복잡하다.

 

→ solved.ac tag: lis