[Algorithm] LIS : 가장 긴 증가하는 부분 수열 알고리즘 알아보기

 

LIS이란 ❓

LIS(Longest Increasing Subsequence, 가장 긴 증가하는 부분 수열)는 주어진 수열에서 가장 긴 증가하는 부분 수열을 찾는 문제입니다.

 

여기서 부분 수열이란, 원래의 수열에서 원소들의 순서를 유지하면서 일부 원소들을 선택한 새로운 수열을 말합니다. 증가하는 수열이란, 선택된 원소들이 항상 오름차순으로 배치되는 수열을 의미합니다.

LIS 예시

주어진 수열이 [10, 20, 10, 30, 20, 50]일 때, LIS는 [10, 20, 30, 50]입니다. 이 부분 수열은 주어진 수열의 원소들 중에서 가장 긴 증가하는 부분 수열로, 원래 수열의 순서를 유지하면서 오름차순으로 나열된 부분 수열입니다.

 

LIS의 특징

1. 부분 수열

• 원래 수열에서 일부 원소들을 선택하여 만든 새로운 수열.

2. 증가하는 수열

• 선택된 원소들이 반드시 오름차순으로 배치되어야 함.

3. 최대 길이

• LIS는 가장 긴 부분 수열을 의미하며, 이는 수열에서 가능한 모든 증가하는 부분 수열 중 가장 긴 수열을 찾는 문제입니다.

 

LIS의 접근 방법 (DP)

 

먼저 처음 모든 원소의 초기 LIS 길이는 1입니다.

 

현재 값은 20이고, 이전 값은 10이므로, 이전값이 더 작기 때문에 증가하는 부분 수열이 가능합니다.

 

따라서 현재 값인 20을 부분 수열에 추가할 수 있으므로, 이전 위치의 dp값에 1을 더한 값과 현재 위치의 dp값을 비교하여 더 큰 값으로 업데이트 해줍니다.

 

 

다음 위치에서는 현재 값이 10이고 이전 값이 20이므로, 이전 값이 더 크기 때문에 증가하는 부분 수열을 만들 수 없습니다. 따라서 dp값을 업데이트하지 않고 그대로 유지합니다.

 

이런 방식으로 각 위치에서 현재 값과 이전 값들을 비교하면서, 현재 값이 이전 값보다 클 경우에만 증가하는 부분 수열을 만들 수 있으며, 이를 통해 최종적인 dp 배열이 완성됩니다.

 

 

LIS의 접근 방법 (이진 탐색)

먼저 tails 배열의 모든 원소를 초기화하고 시작합니다. 첫 번째 원소를 tails[0]에 저장하고 길이를 1로 설정합니다.

---

 

• A[1] = 20을 처리할 때
  • 현재 값 20이 tails의 마지막 값인 10보다 크므로, tails 배열에 추가합니다.

---

• A[2] = 10을 처리할 때
  • 현재 값 10은 tails[0] = 10과 같거나 작으므로, 이진 탐색으로 들어갈 위치를 찾아 10을 해당 위치에 넣습니다.

---

• A[3] = 30을 처리할 때
  • 현재 값 30이 tails의 마지막 값인 20보다 크므로, tails 배열에 추가합니다.

---

이런 방식으로 각 위치에서 현재 값이 tails 배열의 마지막 값보다 크면 추가하고, 그렇지 않으면 이진 탐색으로 적절한 위치를 찾아 해당 값을 대체합니다.

 

최종적으로 tails 배열의 길이가 가장 긴 증가하는 부분 수열의 길이가 됩니다. 이 방법은 O(N log N)의 시간 복잡도를 가지므로 DP 방식보다 더 효율적입니다.

 

LIS 풀이 방법 : Java

1. 동적 계획법 (DP) - O(N²)

class Solution {
    public static int getLISLength_DP(int[] arr) {
        int n = arr.length;
        int[] dp = new int[n]; // 각 위치에서 끝나는 LIS의 길이
        
        // 모든 원소의 초기 LIS 길이는 1
        Arrays.fill(dp, 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);
                }
            }
        }
        
        // 가장 긴 LIS 길이 반환
        return Arrays.stream(dp).max().getAsInt();
    }
}

 

동적 계획법의 특징

• 모든 부분 수열을 고려하여 정확한 LIS를 찾을 수 있음
• 각 위치마다 이전 모든 위치를 검사하므로 시간복잡도가 O(N²)
• 실제 LIS를 추적할 수 있음
• 구현이 직관적이고 이해하기 쉬움

 

2. 이진탐색 - O(N log N)

class Solution {
    public static int getLISLength_BinarySearch(int[] arr) {
        int n = arr.length;
        int[] tails = new int[n]; // LIS 후보 배열
        int len = 0; // 현재 LIS의 길이
        
        tails[0] = arr[0];
        len = 1;
        
        for (int i = 1; i < n; i++) {
            if (arr[i] > tails[len-1]) {
                // 현재 숫자가 tails의 마지막 숫자보다 크면 추가
                tails[len++] = arr[i];
            } else {
                // 그렇지 않으면 들어갈 위치를 이진 탐색으로 찾아 교체
                int pos = Arrays.binarySearch(tails, 0, len, arr[i]);
                if (pos < 0) {
                    pos = -(pos + 1);
                }
                tails[pos] = arr[i];
            }
        }
        
        return len;
    }
}

 

이진 탐색 방법의 특징

• 시간복잡도 O(N log N)으로 더 효율적
• 실제 LIS 수열이 아닌 길이만 구할 수 있음
• 구현이 상대적으로 복잡함
• 대용량 데이터 처리에 적합

---

대부분의 실제 문제에서는 이진 탐색 방법이 선호되지만, 실제 수열을 구해야 하는 경우에는 동적 계획법을 사용해야 할 수 있습니다.