[PS] 99클럽 코테 스터디 29일차 TIL (Longest Increasing Subsequence)

문제

문제 링크

설명

어떤 수열이 주어지고 수열 내에서 수를 몇개 뽑는다고 했을 때, 가장 긴 증가하는 부분수열(LIS)의 길이를 반환하는 문제

풀이 (DP)

dp[i] 는 nums[i] 를 마지막 원소로 하는 LIS 의 길이를 나타낸다. 전체 배열을 순회하면서 현재 인덱스까지 nums[j] < nums[i] 인 경우가 있다는 것은 LIS 가 될 수 있는 조건이기 때문에 dp[i] 를 다음 기준 중 더 긴 길이로 갱신해 준다.

• j 인덱스 까지 계산한 LIS 마지막에 nums[i] 를 추가한 길이 (dp[j] + 1)
• 기존의 dp[i] 값

class Solution {
  public int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);

    int maxLen = 1;
    for (int i = 1; i < nums.length; i++) {
      for (int j = 0; j < i; j++) {    // 현재 인덱스(i) 전 까지 검사
        if (nums[j] < nums[i]) {       // 구간 내에서 현재 인덱스 값(arr[i]) 보다 작으면 LIS 조건 성립
          dp[i] = Math.max(dp[i], dp[j] + 1);    // dp[i] 값 갱신
        }
      }
      maxLen = Math.max(maxLen, dp[i]);   // 기존 LIS 보다 길면 갱신
    }
    return maxLen;
  }
}

전체 배열을 순차적으로 순회하면서 직접 인덱스 비교를 하기 때문에 O(n^2) 의 시간복잡도가 된다.

풀이 (이분탐색)

LIS 문제를 이분 탐색으로 풀게되면 O(n log n) 의 시간복잡도로 해결할 수 있다. 위 DP 방식에선 dp[i] 를 LIS 의 길이로 정의했었는데, 이분 탐색 방식에선 lis 배열에 현재까지 찾은 LIS 가 저장되어 있다.

자바에서 Arrays.binarySearch() 를 통해 이분탐색을 수행 할 수 있다. 첫번째 인자로 값을 찾고자하는 배열을 넘겨주고 순서대로 fromIndex, toIndex, key 를 넘겨준다. key 값을 lis 에서 찾게되면 찾은 위치 인덱스를 반환한다. 만약 못찾게 되면 -(insertion point) -1 값을 반환하는데

예를 들어 삽입 지점이 index 2 인 경우 Arrays.binarySearch() 는 -3 을 반환한다.

int[] arr = {1, 3, 5, 7};
int pos = Arrays.binarySearch(arr, 4); // returns -3

lis 에 삽입 위치 그대로 저장하기 위해 -(pos + 1) 를 하게되면 -(-3 + 1) = 2 가 된다. 위 예시처럼 4는 2번째 인덱스에 들어가야 함을 알 수 있다.

class Solution {
  public int lengthOfLIS(int[] nums) {
    int[] lis = new int[nums.length];
    int length = 0;   // 현재 lis 배열의 유효 길이

    for (int num : nums) {
      int pos = Arrays.binarySearch(lis, 0, length, num);
      if (pos < 0) {    
        pos = -(pos + 1);  // lis 배열에 삽입할 위치 계산
      }
      lis[pos] = num;
      if (pos == length) {  
        length++;
      }
    }
    return length;
  }
}

만약 현재 lis 배열에 [0, 1, 3] 이 들어있는 상태에서 num = 2 이면 pos 는 -3 이 되고, -(pos + 1) = 2 가 된다. lis 배열은 [0, 1, 2] 가 되어 3이 2로 대체된다. 즉, lis 배열엔 계속해서 오름차순으로 값이 들어가게 된다.

length 변수는 lis 배열에 값이 하나씩 추가될때마다 늘어나게 된다. 위 dp 방식과의 차이점이라고 한다면 dp 방식은 부분 수열 자체에는 관심 없고 그 순간 순간의 LIS 길이만을 추적하고 있다면, 이분탐색 방식은 실제로 LIS 를 구성해 간다는 점이 다르다.