최장 증가 부분 수열 (Longest Increasing Subsequence)

정의

최장 증가 부분 수열 (Longest Increasing Subsequence, LIS) 은 주어진 수열에서 순서를 유지하며 선택한 부분 수열 중 엄격히 증가하는 가장 긴 수열을 찾는 문제.

예: [10, 20, 10, 30, 20, 50] → LIS = [10, 20, 30, 50], 길이 4.

문제 상황과 동기

수열 길이 N개에서 증가 부분 수열의 최대 길이를 구한다.

• naive: 모든 부분집합 2^N 탐색. N=20 이상 불가.
• DP: O(N^2) - 각 위치까지의 최장 길이 저장.
• DP + binary search: O(N log N) - 길이별 최소 끝값 배열 유지.

핵심 통찰: 길이 k인 증가 부분 수열 중 끝값이 최소인 것만 유지하면 다음 원소를 더 쉽게 붙일 수 있다. 이 배열은 항상 증가 → 이분 탐색 가능.

실무 / PS: 버전 관리 (longest common increasing subsequence), 스케줄링 (activity selection 변형), 타일링, patience sorting.

시각화

핵심 아이디어

DP O(N^2)

dp[i] = i번 원소를 반드시 포함하는 최장 증가 부분 수열 길이.

dp[i] = max(dp[j] + 1) for all j < i where a[j] < a[i]

DP + Binary Search O(N log N)

tail[len] = 길이 len 인 증가 부분 수열 중 끝값이 최소인 값.

invariant: tail 배열은 증가 수열.

for each a[i]:
  k = lower_bound(tail, a[i])  // tail[k-1] < a[i] <= tail[k]
  tail[k] = a[i]
  if k == tail.size(): tail.push_back(a[i])

최종 답 = tail.size().

알고리즘

O(N^2) DP

lis_dp(a):
    n = len(a)
    dp[0..n-1] = 1
    for i = 0..n-1:
        for j = 0..i-1:
            if a[j] < a[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

O(N log N) DP + Binary Search

lis_binary(a):
    tail = []
    for x in a:
        pos = lower_bound(tail, x)
        if pos == len(tail):
            tail.append(x)
        else:
            tail[pos] = x
    return len(tail)

구현

// LIS O(N log N), tail 배열 유지
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n; cin >> n;
  vector<int> a(n);
  for (auto& v : a) cin >> v;
  vector<int> tail;
  for (int x : a) {
      auto it = lower_bound(tail.begin(), tail.end(), x);
      if (it == tail.end()) tail.push_back(x);
      else *it = x;
  }
  cout << tail.size() << "\n";
}

# bisect.bisect_left 로 O(N log N)
import bisect
import sys
input = sys.stdin.readline
​
n = int(input())
a = list(map(int, input().split()))
tail = []
for x in a:
  pos = bisect.bisect_left(tail, x)
  if pos == len(tail):
      tail.append(x)
  else:
      tail[pos] = x
print(len(tail))

// Collections.binarySearch 로 O(N log N)
import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int n = Integer.parseInt(br.readLine());
      StringTokenizer st = new StringTokenizer(br.readLine());
      ArrayList<Integer> tail = new ArrayList<>();
      for (int i = 0; i < n; i++) {
          int x = Integer.parseInt(st.nextToken());
          int pos = Collections.binarySearch(tail, x);
          if (pos < 0) pos = -(pos + 1);
          if (pos == tail.size()) tail.add(x);
          else tail.set(pos, x);
      }
      System.out.println(tail.size());
  }
}

6
10 20 10 30 20 50

4

5
5 4 3 2 1

1

4
1 2 3 4

4

복잡도

변형 / 활용

LIS 수열 복원

O(N log N) 에서도 수열 복원 가능. parent[i] = i번 원소 이전에 선택된 인덱스.

vector<int> parent(n, -1);
vector<int> tail, idx;
for (int i = 0; i < n; i++) {
    auto it = lower_bound(tail.begin(), tail.end(), a[i]);
    int pos = it - tail.begin();
    if (it == tail.end()) {
        tail.push_back(a[i]);
        idx.push_back(i);
    } else {
        *it = a[i];
        idx[pos] = i;
    }
    if (pos > 0) parent[i] = idx[pos - 1];
}
// traceback from idx.back()

Longest Non-Decreasing Subsequence

lower_bound → upper_bound 로 변경. a[j] <= a[i] 허용.

LCS (Longest Common Subsequence) → LIS 환원

두 수열 A, B 의 LCS 는, B의 각 원소를 A 인덱스로 치환 후 LIS. 단, A의 원소가 unique 할 때만.

Patience Sorting

카드 게임 전략. LIS 알고리즘과 동일.

함정

1. lower_bound vs upper_bound

엄격히 증가 (<) 는 lower_bound, 비감소 (<=) 는 upper_bound.

2. tail 은 답이 아니다

tail 배열은 길이만 의미. 실제 LIS 수열은 아니다 (끝값만 최소로 유지).

3. 수열 복원 필요시 parent 배열

O(N log N) 에서도 parent 추적 필수. tail 만으로는 복원 불가.

4. 중복 원소 처리

같은 값이 여러 개면 lower_bound / upper_bound 선택 주의.

BOJ 연습 문제

참고

• 동적 계획법
• 이분 탐색