[알고리즘 이론] LIS(가장 긴 부분 수열)

 

LIS(Longest Increasing Subsequence )

개념

•  주어진 배열에서 가장 긴 증가하는 부분 수열의 길이를 구하는 코드. DP 방식이나 이분 탐색을 이용하여 풀 수 있다.  예를 들어, 배열 [10, 20, 10, 30, 20, 50]가 주어졌을 때, 가장 긴 증가하는 부분 수열은 [10, 20, 30, 50]로 길이는 4가 된다. 
• 문제 풀이 방식
  1. 동적 프로그래밍(DP) 방식 - 시간 복잡도: O(n^2)
  2. 이분 탐색을 이용한 최적화 방식 - 시간 복잡도: O(n log n)

 

풀이 방식(DP)

• 배열을 순서대로 탐색하면서 dp 배열을 갱신해나가는 방식. 각 위치에서 해당 위치까지의 가장 긴 증가하는 부분 수열의 길이를 저장한다.
  • 점화식: dp[i]는 i번째 요소까지의 가장 긴 증가하는 부분 수열의 길이
  • 갱신 방법: 현재 위치 i보다 앞에 있는 모든 위치 j에 대해 arr[i] > arr[j]이면, dp[i] = max(dp[i], dp[j] + 1)로 갱신한다.

 

풀이 방식(이분 탐색)

• dp 배열을 이용해 현재까지의 LIS를 유지하면서, 각 요소가 들어갈 위치를 이분 탐색으로 찾아 대체하는 방식. 이때 dp 배열에 포함된 요소는 LIS의 길이에만 관여하고, 실제 수열을 구성하지는 않는다.
• 풀이 과정:
  1. dp 배열을 빈 배열로 초기화한다.
  2. 배열의 각 요소에 대해, dp 배열 내에서 그 요소의 위치를 이분 탐색으로 찾는다.
  3. 이분 탐색의 결과 위치에 해당 요소를 삽입하거나 대체하여 dp 배열을 갱신한다.
  4. 최종적으로 dp 배열의 길이가 가장 긴 증가하는 부분 수열의 길이가 된다.

 

예제 코드

DP

# 파이썬
def lis_dp(arr):
    n = len(arr)
    dp = [1] * n  # 각 위치에서 최소 길이는 1로 시작

    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j]:  # 증가하는 부분 수열 조건
                dp[i] = max(dp[i], dp[j] + 1)  # 가장 긴 길이 갱신

    return max(dp)  # dp 배열에서 최댓값이 가장 긴 부분 수열 길이

// java
import java.util.Arrays;

public class LIS_DP {
    public static int lisDP(int[] arr) {
        int n = arr.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);  // 각 위치에서 최소 길이는 1로 시작

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {  // 증가하는 부분 수열 조건
                    dp[i] = Math.max(dp[i], dp[j] + 1);  // 가장 긴 길이 갱신
                }
            }
        }

        int maxLength = 0;
        for (int length : dp) {
            maxLength = Math.max(maxLength, length);
        }

        return maxLength;  // 가장 긴 부분 수열의 길이 반환
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 10, 30, 20, 50};
        System.out.println("DP 방식 LIS 길이: " + lisDP(arr));  // 출력: 4
    }
}

 

이분 탐색

# 파이썬
from bisect import bisect_left

def lis_binary_search(arr):
    dp = []  # LIS 배열을 유지하는 dp 리스트

    for num in arr:
        pos = bisect_left(dp, num)  # num이 들어갈 위치를 이분 탐색으로 찾음
        if pos == len(dp):
            dp.append(num)  # num이 가장 큰 값이면 추가
        else:
            dp[pos] = num  # num이 들어갈 위치에 대체

    return len(dp)  # dp 배열의 길이가 LIS 길이

// java
import java.util.ArrayList;
import java.util.Collections;

public class LIS_BinarySearch {
    public static int lisBinarySearch(int[] arr) {
        ArrayList<Integer> dp = new ArrayList<>();  // LIS 배열을 유지하는 dp 리스트

        for (int num : arr) {
            int pos = Collections.binarySearch(dp, num);  // num이 들어갈 위치를 이분 탐색으로 찾음
            if (pos < 0) {
                pos = -(pos + 1);  // 삽입 위치를 음수값으로 반환하기 때문에 변환
            }
            if (pos == dp.size()) {
                dp.add(num);  // num이 가장 큰 값이면 추가
            } else {
                dp.set(pos, num);  // num이 들어갈 위치에 대체
            }
        }

        return dp.size();  // dp 리스트의 크기가 LIS의 길이
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 10, 30, 20, 50};
        System.out.println("이분 탐색 방식 LIS 길이: " + lisBinarySearch(arr));  // 출력: 4
    }
}

 

관련 문제

• 실버 2 - 11053번 - 가장 긴 증가하는 부분 수열
• 골드 2 - 12015번 - 가장 긴 증가하는 부분 수열 2
• 골드 2 - 12738번 - 가장 긴 증가하는 부분 수열 3
• 실버 1 - 14002번 - 가장 긴 증가하는 부분 수열 4
• 골드 3 - 2352번 - 반도체 설계