백준 12015번: 가장 긴 증가하는 부분 수열 (LIS)

 

가장 긴 증가하는 부분 수열 (LIS) 문제는 수열에서 오름차순으로 정렬된 가장 긴 부분 수열의 길이를 구하는 대표적인 알고리즘 문제입니다.

입력: 10 20 10 30 20 50  
출력: 4 (예: 10 → 20 → 30 → 50)

이 문제를 해결하는 방법에는 O(N²)의 DP 방식과 O(N log N)의 이분 탐색 방식이 있는데,
입력 수가 많아질수록 O(N log N) 방식이 훨씬 효율적입니다.

 

이 문제의 입력조건은

' 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. '

 

그래서 O(N²) 방식으로 풀 경우 시간초과 입니다. 그래서 O(N log N) 방식으로 LIS의 길이를 구해야 합니다.

---

전체 코드 (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

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());
        int[] arr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

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

        for (int i = 0; i < n; i++) {
            int idx = binarySearch(list, arr[i]);

            if (idx < list.size()) {
                list.set(idx, arr[i]);
            } else {
                list.add(arr[i]);
            }
        }

        System.out.println(list.size());
    }

    public static int binarySearch(List<Integer> list, int target) {
        int left = 0;
        int right = list.size();

        while (left < right) {
            int mid = (left + right) / 2;

            if (list.get(mid) >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }
}

 

 

LIS(가장 긴 증가하는 부분수열)를 리스트에 저장하지 않는다

이 코드에서 list는 실제 증가하는 부분 수열을 저장하는 목적이 아닙니다.

 그저 "길이 유지에 필요한 최소한의 값"만을 담는 리스트입니다.

⚠ 예시

arr = [10, 20, 7, 30, 20, 50]

< list 변화 >

10 → [10]
20 → [10, 20]
7 → list.set(0, 7) → [7, 20]
30 → [7, 20, 30]
20 → list.set(1, 20) → [7, 20, 30]
50 → [7, 20, 30, 50]

그런데 실제 LIS 수열은 10 → 20 → 30 → 50일 수도 있음
list는 7로 시작해서 전혀 다른 경로임

 

 

시간 복잡도

작업	시간 복잡도
전체 반복 (N번)	O(N)
이분 탐색 (각 원소마다)	O(log N)
전체	O(N log N)

입력이 100,000 이상이어도 충분히 통과 가능한 수준