[코딩테스트] 9. LIS

LIS(Longest Increasing Subsequence)는 수열에서 값이 오름차순을 유지하는 가장 긴 부분 수열의 길이를 구하는 문제다. DP 문제에서 자주 출제되고, 응용 범위도 넓다.

문제 이해

수열 [3, 1, 4, 1, 5, 9, 2, 6]에서 LIS를 찾아보자.

오름차순을 유지하는 부분 수열 중 가장 긴 것을 찾으면 된다. 연속일 필요는 없다. 순서만 지키면 된다.

[3, 1, 4, 1, 5, 9, 2, 6]
         ↑     ↑  ↑  ↑
         4     5  9  6  → 길이 4이지만 9 다음에 6은 감소 → 안 됨

         4     5     6  → [1, 4, 5, 6] 길이 4 ✓

LIS는 여러 개일 수 있다. [1, 4, 5, 9]도 길이 4인 LIS다.

상태 정의

dp[i] = arr[i]를 마지막 원소로 하는 LIS의 길이.

핵심은 "i번 원소를 반드시 포함"하는 가장 긴 증가 수열이라는 점이다.

수열: [3, 1, 4, 1, 5]
       ↑  ↑  ↑  ↑  ↑
dp:   [1, 1, 2, 1, 3]

dp[0]=1: [3]
dp[1]=1: [1]
dp[2]=2: [1,4] 또는 [3,4]
dp[3]=1: [1] (앞의 1과 같지만 인덱스가 다름, 앞에 4>1이라 [1,4,1]은 불가)
dp[4]=3: [1,4,5] 또는 [3,4,5]

최종 답은 dp 배열의 최댓값이다.

점화식

dp[i]를 구하려면 arr[i]보다 앞에 있고 값이 작은 원소들을 전부 확인한다.

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

arr[j] < arr[i]인 j들 중 dp[j]가 가장 큰 것을 선택해서 +1 한다.

int[] dp = new int[n];
Arrays.fill(dp, 1);

for (int i = 1; i < n; i++) {
    for (int j = 0; j < i; j++) {
        if (arr[j] < arr[i]) {
            dp[i] = Math.max(dp[i], dp[j] + 1);
        }
    }
}

int answer = 0;
for (int val : dp) answer = Math.max(answer, val);

• Arrays.fill(dp, 1) : 모든 원소는 자기 혼자만으로 길이 1의 LIS를 이룬다
• 내부 루프에서 j < i이고 값이 작은 경우를 전부 확인

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

O(N log N) 풀이

N이 10만 이상이면 O(N²)은 시간 초과가 난다. 이분 탐색을 활용하면 O(N log N)으로 줄일 수 있다.

배열 tail을 유지한다. tail[k]는 길이 k+1인 증가 수열의 가장 작은 마지막 원소다.

List<Integer> tail = new ArrayList<>();

for (int x : arr) {
    int pos = Collections.binarySearch(tail, x);
    if (pos < 0) pos = -(pos + 1);

    if (pos == tail.size()) tail.add(x);
    else tail.set(pos, x);
}

int answer = tail.size();

tail의 길이가 LIS의 길이가 된다.

→ 다음 : 배낭 문제

---