알고리즘 - 최장 증가 부분 수열 (LIS)

최장 증가 부분 수열

 

최장 증가 부분 수열(Longest Increasing Subsequence)이란 어떤 수열이 주어졌을 때, 해당 수열의 부분 수열 중 오름차순으로 정렬된 가장 긴 수열을 의미합니다.

 

예를 들어 다음과 같은 수열이 주어졌다고 가정해봅시다.

3, 1, 4, 5, 9, 2, 6, 5, 3, 5

 

그럼 해당 수열에서 수많은 부분 수열이 나올 수 있습니다.

(3) (1) (4) ....
(3,1) (3, 4) ...
(3,1,4) (3,1,5) ... 

 

이러한 부분 수열 중에 오름차순으로 정렬된 가장 긴 수열(LIS)은 다음과 같습니다.

(1, 4, 5, 9)
(1, 4, 5, 6)
(1, 2, 3, 5)
(3, 4, 5, 9)
(3, 4, 5, 6)

 

최장 증가 부분 수열 길이 구하기

 

보통 알고리즘 문제로 최장 증가 부분 수열의 길이를 구하는 문제가 나오는데, 이러한 문제는 두가지 방식으로 풀 수 있습니다.

 

동적 계획법(DP) 이용

 

동적 계획법을 이용해서 LIS의 길이를 구할 수 있습니다.

 

해당 방법은 다음과 같은 과정을 거칩니다.

 

1. 수열의 각 자리들의 최장 길이를 기록할 배열을 선언한 후, 1로 초기화

여기서 1로 초기화하는 이유는 최소로 보장되는 LIS의 길이는 1이기 때문입니다.

 

1. 최장길이를 기록할 배열 추가 및 1로 초기화

 

2. 수열의 각 자리를 순차적으로 돌면서 현재 위치보다 이전 위치들의 수가 작은지 확인

 

2-1. 현재(here) 값 이전의 값이 없으므로 pass

 

2-2. 현재 값보다 작은 값이 없으므로 유지

 

3. 만약 이전 값이 현재 값보다 작다면 Max(이전 값의 LIS + 1, 현재 LIS)를 현재 LIS로 기록

 

3-1. 현재 값보다 작은 값이 존재하므로 작은 값의 최장길이 + 1을 현재 값의 최장길이로 업데이트

3-2. 현재 값보다 작은 값이 존재하지만, 이전 값의 LIS + 1 과 현재의 LIS가 같으므로 그대로 유지

 

4. 3번 과정을 수열이 끝날 때까지 반복

 

DP를 이용한 방법은 N * N 번 반복되므로 O(N^2)의 시간복잡도를 가지고 있습니다. 

 

이진 탐색 이용

 

이진 탐색의 순차적으로 정렬되는 특징을 이용한 방식입니다.

 

다음과 같은 과정을 통해 이루어집니다.

 

1. 이진 탐색을 할 배열 선언

1. 최장 길이를 이진 탐색 배열을 선언합니다.

 

2. 수열을 돌면서 해당 값이 이진 탐색 배열의 위치 상 어디에 위치해야하는지 파악 후 교체

2-1. 현재 값 3은 처음 값이므로 이진 탐색 배열의 처음에 위치시킵니다.

2-2. 1은 3보다 작으므로 이진 탐색 배열에서 1은 1번째 위치, 3은 2번째 위치로 가야겠지만, LIS를 구하는 것이기 때문에 밀려난 값은 삭제해줍니다.(교체)

2-3. 4는 이진탐색 배열에서 1 다음 위치에 위치할 수 있으므로 2번째 자리에 위치시킵니다.

3. 2번 과정을 수열이 끝날 때 까지 반복

 

이진 탐색을 이용한 방법은 해당 수열을 돌면서 (N) 이진 탐색으로(logN) 자리를 찾기 때문에 O(NlogN)의 시간복잡도를 가집니다.

 

프로그래밍 언어로 구현

Java

// DP
public static int dpLis(int[] arr) {

   // 최장 길이를 저장할 배열 선언
   int[] dp = new int[arr.length];

   // 기본값 채워 넣기, LIS는 최소 길이가 1이기 때문
   Arrays.fill(dp, 1);

   // 주어진 배열을 돌면서
   for (int i = 0; i < arr.length; i++) {
      // 이전 값들이 현재 값보다 작은지 체크
      for (int j = 0; j < i; j++) {
         // 이전 값들이 나보다 값이 작다는 것은 오름차순이라는 의미
         if (arr[j] < arr[i]) {
            // 작다면 내 최장 길이와 작은 수가 가진 최장 길이 + 1 를 비교해서 큰 값으로 업데이트
            dp[i] = Math.max(dp[i], dp[j] + 1);
         }
      }
   }

   // dp의 최대값이 최장 길이
   int result = Arrays.stream(dp).max().getAsInt();

   return result;
}


// 이진 탐색
public static int binaryLis(int[] arr) {

   // 부분 수열을 체크할 배열
   int[] result = new int[arr.length];

   // lis 길이 체크
   int len = 0;


   for (int num : arr) {
      // 이진 탐색은 직접 반복문으로 구현하셔도 됩니다.
      int idx = Arrays.binarySearch(result, 0, len, num);

      // Arrays.binarySearch는 해당 값이 배열에 없으면 -(해당 값이 들어가야할 자리) -1 을 반환하므로
      // 그거를 보완해주는 식
      if (idx < 0) {
         idx = -(idx + 1);
      }

      // 해당 위치에 삽입
      result[idx] = num;

      if (len == idx) {
         len++;
      }
   }

   return len;

}