LIS(Longest Increasing Subsequence) Algorithm

목차

1. LIS란?
2. DP → $O(n^2)$
   1. 아이디어
   2. 점화식
   3. 코드
3. 이진 탐색 → $O(nlogn)$
   1. 아이디어
   2. 동작 방식
   3. 코드
4. 참고

1. LIS란?

LIS, Longest Increasing Subsequence(최장 증가 수열, 최대 증가 부분 수열): 어떤 수열에서 특정 부분을 지워서 만들어낼 수 있는 가장 긴 증가하는 부분 수열

• 부분 수열: 원래 순서를 유지하면서 몇 개를 골라 만든 수열

10, 20, 40, 25, 20, 50, 30, 70, 85 라는 수열이 있을 때,
LIS는 10, 20, 40, 50, 70, 85가 된다.

2. DP → $O(n^2)$

2.1. 아이디어

dp[i]: i번째 원소를 마지막으로 하는 LIS의 길이

즉, arr[i]에서 끝나는 가장 긴 LIS 길이

2.2. 점화식

arr[j] < arr[i]인 이전 원소들 중에서 이어붙일 수 있으므로:

dp[i] = max(dp[j] + 1) (단, j < i 이고 arr[j] < arr[i])

초기값은 자기 자신만 선택하는 경우이므로:

dp[i] = 1

2.3. 동작흐름

flowchart TD
    A[시작] --> B[arr와 dp 준비]
    B --> C[i = 0부터 n-1까지 반복]
    C --> D[dp[i] = 1로 초기화]
    D --> E[j = 0부터 i-1까지 비교]
    E --> F{arr[j] < arr[i]?}
    F -- 예 --> G{dp[j] + 1 > dp[i]?}
    G -- 예 --> H[dp[i] = dp[j] + 1]
    G -- 아니오 --> I[다음 j]
    F -- 아니오 --> I
    H --> I
    I --> J{j 반복 끝?}
    J -- 아니오 --> E
    J -- 예 --> K[maxLength 갱신]
    K --> L{i 반복 끝?}
    L -- 아니오 --> C
    L -- 예 --> M[정답 = maxLength]
    M --> N[종료]

2.4. 코드

def lis_dp(arr):
    n = len(arr)
    dp = [1] * n

    for i in range(n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp) if arr else 0

int lisDP (int[] arr) {
	if (arr == null || arr.length == 0) return 0;

	int n = arr.length;
	int[] dp = new int[n];
	int maxLength = 0;
	
	for (int i = 0; i < n; i++) {
		dp[i] = 1;
		
		for (int j = 0; j < i; j++) {
			if (arr[j] < arr[i] && dp[j]+1 > dp[i]) dp[i] = dp[j]+1;
		}
		
		if (maxLength < dp[i]) maxLength = dp[i];
	}
	
	return maxLength;
}

3. 이진 탐색 → $O(nlogn)$

3.1. 아이디어

lis 배열을 유지

lis[k] = 길이가 k+1인 LIS의 마지막 값들 중 가능한 최소값

실제 LIS 자체를 저장하는 게 아니라 각 길이에 대해 마지막 값을 최대한 작게 유지한다

3.2. 동작 방식

수열을 왼쪽부터 보면서:

1. 현재 값이 lis의 마지막 값보다 크면 뒤에 붙인다
2. 작다면 이분 탐색으로 들어갈 위치를 찾아서 교체한다

3.3. 동작 흐름

flowchart TD
    A[시작] --> B[cache 비움]
    B --> C[arr를 왼쪽부터 하나씩 확인]
    C --> D{현재 값 > cache의 마지막 값?}
    D -- 예 --> E[cache 뒤에 추가]
    D -- 아니오 --> F[이진 탐색으로 lower bound 위치 찾기]
    F --> G[그 위치 값을 현재 값으로 교체]
    E --> H{모든 원소 처리 완료?}
    G --> H
    H -- 아니오 --> C
    H -- 예 --> I[정답 = cache 길이]
    I --> J[종료]

3.4. 코드

def lower_bound(arr, target):
    left = 0
    right = len(arr)

    while left < right:
        mid = (left + right) // 2

        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid

    return left

def lis_binary(arr):
    lis = []

    for x in arr:
        pos = lower_bound(lis, x)

        if pos == len(lis):
            lis.append(x)
        else:
            lis[pos] = x

    return len(lis)

int binarySearch(ArrayList<Integer> arr, int l, int r, int trg) {
    while (l < r) {
        int c = (l + r) / 2;

        if (trg > arr.get(c)) {
            l = c + 1;
        } else {
            r = c;
        }
    }

    return r;
}

int lisBS(int[] arr) {
    if (arr == null || arr.length == 0) return 0;

    ArrayList<Integer> lis = new ArrayList<>();
    lis.add(arr[0]);

    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > lis.get(lis.size() - 1)) {
            lis.add(arr[i]);
        } else {
            int pos = binarySearch(lis, 0, lis.size() - 1, arr[i]);
            lis.set(pos, arr[i]);
        }
    }

    return lis.size();
}

참고

• Github Pages: LIS의 길이를 구하는 3가지 알고리즘
• Tistory: [최장 증가 수열] LIS(Longest Increasing Subsequence)
• Tistory: [1][LIS : 최장 증가 수열 알고리즘] - DP를 이용한 알고리즘 (Longest Increasing Subsequence Algorithm)
• Tistory: [2][LIS : 최장 증가 수열 알고리즘] - Lower Bound를 이용한 알고리즘 (Longest Increasing Subsequence Algorithm)
• Tistory: 최장 증가 수열 (LIS, Longest Increasing Subsequence) 2