[백준] LIS DP, 이분탐색

 

LIS (Longest Increasing Subsequnce, 최장 증가 부분 수열)

LIS는 주어진 수열에서 원소들의 순서를 유지 하며, 가능한 가장 긴 증가하는 부분 수열을 찾는 문제이다.

예시로
nums = [10,20,10,30,20,50] 이 주어졌으면, LIS는 [10,20,30,50] 이고 길이는 4이다.

LIS를 구하는 대표적인 방법은 DP(동적 계획법) 과 이분 탐색을 활용한 방법이 있다.

1.DP (O(N²))를 이용한 LIS 구현

동적 계획법을 사용하면 각 원소 nums[i] 를 마지막 원소로 하는 LIS 길이를 저장하는 dp 배열을 유지한다.
완전 탐색법이고, 이중 반복문을 사용하므로 O(N^2) 가 걸린다.

DP 정의

dp[i] = nums[i]를 마지막 원소로 하는 LIS의 최대 길이

1. nums[i] 보다 작은 nums[j] (j<i)를 찾고, dp[i] = Math.max(dp[j]+1)로 갱신한다.
2. dp 배열을 업데이트 하면서 최대 길이도 갱신해준다.
3. dp 배열 중 최댓값이 LIS의 길이가 된다.

DP 코드

for (int i = 0; i < N; i++) {
    dp[i] = 1; //인덱스 i를 가지고 만들 수 있는 가장 큰 수열의 길이
    for (int j = 0; j < i; j++) { //i보다 작은 인덱스들
        if (map[j] < map[i]) {//만약 앞 인덱스보다 값이 크면
            dp[i] = Math.max(dp[j] + 1, dp[i]); //이전 수열의 길이에 1을 더하는 것 vs 현재 dp값
            maxLen = Math.max(maxLen, dp[i]);
        }
    }
}
sb.append(maxLen).append("\n");
for (int i = N - 1; i >= 0; i--) {
    if (maxLen == dp[i]) {
        dq.offerLast(map[i]);
        maxLen--;
    }
}

while (!dq.isEmpty()) {
    sb.append(dq.pollLast()).append(" ");
}

2. 이분 탐색(O(NlogN))을 이용한 LIS 구현

DP는 식은 간단하지만 O(N^2)가 걸리므로 느리다.
이분 탐색을 사용하면 O(NlogN)에 끝낼 수 있다.

이분탐색 공식

1. 가변적인 List로 LIS 배열을 선언한다. List lis = new ArrayList<>();
2. 처음에 비어있으므로 nums[0] 첫번째 요소를 lis.add(nums[0])한다.
3. nums 배열을 탐색하면서 lis의 마지막 요소보다 크면 list.add(nums[i]) 한다.
4. 만약 lis의 마지막 요소보다 작은 요소가 나왔다면 이분탐색을 진행한다.

이분 탐색:

1. int left = 0, int right = lis.size() -1, int mid = (left+right)/2 로 지정해준다.
2. lis.get(mid) 값이 nums[i]보다 크다면 nums[i]의 lis에서의 자리가 mid값보다 뒤라는 뜻이다. 따라서 right 위치를 mid - 1로 옮겨준다.
3. 반대로 nums[i]가 더 크다면 left위치를 mid+1로 옮겨주면 된다.
4. 이분탐색의 조건은 left가 right보다 작거나 클 때이다. left가 right보다 커지면 종료한다.
5. 이때 종료했을 때의 left값이 nums[i]보다 가장 작은데 최대인 수의 idx + 1(바로 옆)이므로 바로 그 위치에 삽입해주면 된다.
6. 따라서 while문(이분탐색) 종료 후에는 lis.set(left,nums[i]) 해주면된다.

5. 이분탐색 종료 후에는 lis.size()를 리턴하면 최장 증가 부분 수열의 길이가 나온다.

이분 탐색 코드

 for (int num : arr) {
      if (lis.isEmpty() || lis.get(lis.size() - 1) < num) {
          lis.add(num);
      } else {
          int left = 0;
          int right = lis.size() - 1;
          while (left <= right) {
              int mid = (left + right) / 2;
              if (lis.get(mid) < num) {
                  left = mid + 1;
              } else {
                  right = mid - 1;
              }
          }
          lis.set(left, num);
      }
  }
  if (lis.size() >= K) {
      answer = 1;
  } else {
      answer = 0;
 }