최장 증가 부분 수열(LIS) 알고리즘 정리(백준 11053, 11054)

 

백준 2565 전깃줄 문제가 너무 안풀려 구글링을 하다 LIS 알고리즘을 접하게 되었다. 브루트포스든 datastructure든 dp든 계속 파고들면 새로 배워야할 알고리즘이 보이는 것 같다. (브루트포스->백트래킹, datastructure->union-find, dp->LIS...)

공부가 끝이없다! ㅎㅎ

 

 

 

최장 증가 부분 수열(LIS: Longest Increasing Subsequence) 알고리즘이란?

원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하는 최대길이의 부분수열을 구하는 문제다.

 

예를 들면 다음과 같은 수열이 있다

6 2 5 1 7 4 8 3

이 수열에서 최장증가 부분수열은 2578 이다.

 

 

 

LIS 풀이법

LIS 문제를 푸는 방법은 DP를 이용하는 것이다. 

포인트는 다음과 같다

 

"나"를 포함하는 부분증가수열 중 내 앞에 올 수 있는 애 찾기 

 

"나"는 인덱스다. 

6 2 5 1 7 4 8 3

다음과 같은 수열이 있다면 "나"는 각 인덱스의 값이 될 수 있다. 6, 2, 5...

 

그리고 내 최장부분증가수열을 찾는 방법은 다음과 같다

1. 내 앞에 있는 애들 중 나를 포함한 부분증가수열에 들어갈 수 있는 애들을 일단 찾는다
2. 나의 최장부분증가수열은 걔의 최장부분증가수열 + 1 이다. (나만 포함하면 되니까)
3. 다 돌아가면서 구한 값들 중 max를 찾아 내 값을 갱신한다

 

예시를 들어보겠다

 

"나" = 7

• 내 앞에있는 6 2 5 1 을 보면서 나보다 작은 애를 찾는다
• 나보다 크기가 작은 애 = 내 부분증가수열의 앞자리 수가 될 수 있다
• 나보다 크기가 작은 6의 최장부분증가수열값 + 1 한 값이 내 부분증가수열 중 하나가 된다
• 6 2 5 1 각각 크기비교, (최장부분증가수열값+1) 값들을 구한 후 max값을 내 최장부분증가수열로 갱신

 

코드를 보면 더 이해가 잘된다

 

DP 풀이

for (int k = 0; k < n; k++){
    LIS[k] = 1;
    for (int i = 0; i < k; i++){
        if(arr[i] < arr[k]){
            LIS[k] = max(length[k], length[i] + 1);
        }
    }
}

• LIS배열은 1로 초기화해야한다(나만 포함하는 경우가 최소이다)
• 이 경우 시간복잡도가 O(N^2)가 걸린다.
• 이분탐색을 이용하면 조금 더 시간을 줄일 수 있다고 한다

 

이분탐색 풀이

그냥 리스트가 있으면 각 인덱스 값이 들어갈 인덱스에 추가해주면 된다고 한다.

이게 왜 되는지는 모르겠지만 길이자체는 확실하게 구할 수 있다(이게 되네?)

 

신기하다 왜 되지

• 순서자체는 유지가 되기 때문에 가능한 풀이인 것 같다
• 참신해서 그냥 외우려고 한다

 

 

관련 문제 풀어보기

 

11053 가장 긴 증가하는 부분 수열 - 실버2

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

 

• 길이만 출력하면 되기 때문에 이분탐색으로도 충분히 풀릴 것 같다
• dp와 이분탐색 두 가지 방법으로 다 풀어보겠다

 

이분탐색 풀이

public class Main {
  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int n = Integer.parseInt(br.readLine());
    int arr[] = new int[n];
    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i=0; i<n; i++) {
      arr[i] = Integer.parseInt(st.nextToken());
    }

    List<Integer> list = new ArrayList<>();
    list.add(arr[0]);

    for (int i=1; i<n; i++) {
      if (list.get(list.size()-1) < arr[i]) {
        list.add(arr[i]);
      } else {
        int idx = binarySearch(arr[i], list);
        list.set(idx, arr[i]);
      }
    }

    System.out.println(list.size());
  }

  //lowerbound를 구하자
  private static int binarySearch(int value, List<Integer> list) {
    int start = 0;
    int end = list.size();

    while (start < end) {
      int mid = (start+end)/2;

      if (value > list.get(mid)) {
        start = mid+1;
      } else {
        end = mid;
      }
    }

    return start;
  }
}

• list의 맨 끝값과 나를 비교하여 내가 크다면 그냥 add
• 내가 크지 않다면 list에서 내가 들어갈 수 있는 곳을 이진탐색하여 idx를 구하고 거기다 삽입
  • 이진탐색은 어차피 나와 중복되는 값이 없을 것이기 때문에 indexoutofbound에러가 출력되지 않도록 lowerbound를 구해줬다
• list의 최종 길이를 출력하면 된다

 

dp풀이

public class Main {
  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int n = Integer.parseInt(br.readLine());
    int arr[] = new int[n];
    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i=0; i<n; i++) {
      arr[i] = Integer.parseInt(st.nextToken());
    }

    int lis[] = new int[n];
    for (int i =0; i<lis.length; i++) {
      lis[i] = 1;
    }
    int max = 1;

    //"나" 선택
    for (int i =1; i<arr.length; i++) {
      //"나" 밑에 모든 값 비교, 최장부분증가수열 갱신
      for (int j=0; j<i; j++) {
        if (arr[j] < arr[i]) {
          //내 부분증가수열의 앞자리가 될 수 있다 = 내 부분증가수열 길이는 얘를 앞자리로 해서 +1
          lis[i] = Math.max(lis[i], lis[j]+1);
          if (max < lis[i])
            max = lis[i];
        }
      }
    }

    System.out.println(max);
  }
}

• 이중 for문으로 쉽게 구할 수 있다
• 위에 설명한 내용을 그대로 구현했다
• 최장부분수열이 갱신될 때마다 if 문으로 max값을 갱신해주고, 이를 최종 출력했다

 

 

11054 가장 긴 바이토닉 부분 수열 - 골드4

https://www.acmicpc.net/problem/11054

11054번: 가장 긴 바이토닉 부분 수열

(급 골드4가 나와서 당황)

 

• 이 문제도 LIS 알고리즘을 사용할 수 있다고 한다
• 올라가는 수와 내려가는 수를 둘 다 비교하면 될 것 같다 / queue로 되는지는 잘 모르겠다

 

처음 풀이법 생각 - 틀림

• 내 앞에 있는 애들 중
• 나보다 크기가 작으면서 && 올라가고 있는 애들의 최장바이토닉부분수열+1
• 나보다 크기가 크면서 && 내려가고 있는 최장바이토닉부분수열 + 1
• 얘네들을 모으고, 이 중 가장 큰 수가 내 가장 긴 바이토닉 부분수열임

=> 이렇게 하면 답이 제대로 나오지 않음

 

두 번째 풀이법 생각

• 최장부분증가수열을 구하고
• 최장부분감소수열을 구한 후
• 둘의 합이 가장 큰 수를 구함 -> max-1이 정답
• 합을 구하면 내가 2번 포함되게 되므로 1을 빼주는 게 포인트다

 

풀이

public class Main {
  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int n = Integer.parseInt(br.readLine());
    int arr[] = new int[n];
    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i=0; i<n; i++) {
      arr[i] = Integer.parseInt(st.nextToken());
    }

    int lis[] = new int[n];
    int lisReverse[] = new int[n];
    for (int i =0; i<lis.length; i++) {
      lis[i] = 1;
      lisReverse[i] = 1;
    }

    //"나" 선택
    for (int i =1; i<arr.length; i++) {
      //"나" 밑에 모든 값 비교, 최장부분증가수열 갱신
      for (int j=0; j<i; j++) {
        if (arr[j] < arr[i]) {
          //내 부분증가수열의 앞자리가 될 수 있다
          lis[i] = Math.max(lis[i], lis[j]+1);
        }
      }
    }
    
    //최장부분증가수열을 그냥 반대로함
    for (int i =arr.length-2; i>=0; i--) {
      //"나" 밑에 모든 값 비교, 최장부분증가수열 갱신
      for (int j=arr.length-1; j>i; j--) {
        if (arr[j] < arr[i]) {
          //내 부분증가수열의 앞자리가 될 수 있다
          lisReverse[i] = Math.max(lisReverse[i], lisReverse[j]+1);
        }
      }
    }

    int max = -1;
    for (int i =0; i<arr.length; i++) {
      if (lis[i]+ lisReverse[i] > max) {
        max = lis[i] + lisReverse[i];
      }
    }

    System.out.println(max-1); //내가 2번 포함되므로, -1
  }
}

 

 

 

 

 

 

 

 

참고한 블로그

https://chanhuiseok.github.io/posts/algo-49/

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

https://4legs-study.tistory.com/106

최장 증가 수열 (LIS, Longest Increasing Subsequence)