[문제 풀이] 가장 긴 증가하는 부분 수열 (LIS)

 

안녕하세요. 오늘의 문제는 LIS라고 불리는 가장 긴 증가하는 부분 수열 문제들의 해결 방식들에 대해 이야기해보겠습니다.

 

백준 번호 11722번

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

 

(아 이 문제에서는 감소하는 수열이긴 한데 풀이법은 동일합니다.)

 

일단 모든 경우를 브루트 포스를 구한다면 얼마나 걸릴지 먼저 생각을 해보겠습니다. 수열 A의 크기 N에서 1개부터 N개까지 뽑는 경우의 수로 표현해야 할지 2^1000으로 표현해야 할지 고민이네요. 아무튼 둘 다 굉장히 오래 걸립니다. 

 

그럼 어떤 규칙을 찾아야 합니다. 시간을 줄이기 위해서는 이미 한번 수행한 적이 있는 계산을 다시 수행하지 않아야 합니다. 다. 그 예를 들어보면 

 

arrA = {1,2,3,4,6} / arrB={1,2,3,4,6,8} 

 

A 배열의 가장 긴 감소하는 부분 수열의 길이는 5입니다.  B 배열의 가장 긴 감소하는 부분 수열의 길이는 물론 직접 셀 수 있지만 배열 A의 마지막 자리보다 더 작은 수가 추가되었으므로 5+1 = 6으로 구할 수 있습니다. 

 

즉 어떤 배열 arr에서, LIS [n] = LIS [n-1] +1 (arr [n] > arr [n-1] ) 으로 생각할 수 있죠. 하지만 세상일이 이렇게 간단하지 않습니다. 

arrA = {1,2,3,2} / arrB={1,2,3,2,3}

 

위와 같은 상황에서는 LIS[n] = LIS[n-1] +1 (arr[n] > arr[n-1] )이 적용되지 않습니다. 그 이유는 2가 LIS의 끝 나는 부분이 아니기 때문입니다.

 

따라서LIS [n]은 arr[n] > arr[n-1] 이면, arr[n-1]이 가장 긴 수열의 마지막 부분인 경우  LIS [n] = LIS[n-1] +1 가 성립합니다.  즉 새로 들어온 수와 각 요소들 간의 개별적인 비교가 필요합니다. 

 

LIS[n] = Math.max(LIS [1] +1 (arr [1] < arr [n] ) , LIS[2] +1 (arr[2] < arr[n] )... )

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int n,answer;
    static int[] arr,memo;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        arr = new int[n+1];
        memo = new int[n+1];
        for(int i=1;i<=n;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        memo[1] = 1;
        for(int i=2; i<=n;i++){
            memo[i] = 1;
            for(int j = 0; j<i;j++){
                if(arr[j] > arr[i]){
                    memo[i] = Math.max(memo[i],memo[j]+1);
                }
            }
        }
        Arrays.sort(memo);
        System.out.println(memo[n]);
    }
}

 

 

이 문제에서는 sort를 하거나 혹은 memo [i]에 memo [i-1] 값을 초기에 넣어주면 될 것 같습니다.

 

 

백준 번호 11722번 가장 긴 증가하는 부분 수열 4

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

 

 

이제는 길이 + 증가하는 부분 수열을 출력해야 합니다. 

 

그럼 위 문제에서 구현한 memo에 어떤 값이 담기는지 확인을 해보겠습니다. 

 

arr = {10 20 10 30 20 50}인 경우 memo = {1,2,1,3,2,4} 

아 혹시 이번문제에서도 memo [i]에 memo [i-1] 값을 초기에 넣으면 안 됩니다.

 

이제 memo를 역 방향으로 순회하며 최대 값 (증가하는 부분 수열의 최대 길이)와 같다면 LIS에 사용되는 요소로 체크하고 최댓값을 -1 해주면 됩니다. 

 

문제에서 원하는 건 증가하는 방향이니까 stack 자료구조에 딱 넣어주면 이쁩니다. 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        int[] dp = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        int maxLen = 1;
        int maxIndex = 0;
        for(int i=0;i<n;i++){
            arr[i] = Integer.parseInt(st.nextToken());
            dp[i] = 1;
            for(int j = 0; j<i;j++){
                if(arr[i] > arr[j]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                    if(maxLen < dp[i]){
                        maxIndex = i;
                        maxLen = dp[i];
                    }
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        sb.append(maxLen).append("\n");
        Stack<Integer> stack = new Stack<>();
        for(int i=maxIndex;i>=0;i--){
            if(dp[i] == maxLen){
                stack.add(arr[i]);
                maxLen --;
            }
        }
        while (!stack.isEmpty()){
            sb.append(stack.pop()+" ");
        }
        System.out.println(sb);
    }
}

 

 

백준 번호 14003번 가장 긴 증가하는 부분 수열 5

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

 

 

마지막입니다. 으휴 지겨워 이제 쉽다 쉬워라고 생각 금지

 

이번에는 수열 N의 크기가 굉장히 커졌습니다. 위 두 문제에서 적용한 DP는 O(N ^2 )으로 위 문제에서는 안 통합니다. 

 

시간을 줄이는 방법이 또 있다고...?

 

이 부분에서는 아래 블로그 분을 참고하여 문제를 풀었습니다.

https://jason9319.tistory.com/113

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

 

이렇게 끝내면 안 되겠죠?

 

그럼 이 문제를 풀지 못한 이유를 적어보자면

 

- LIS의 길이를 구하는 방법으로 Lower bound을 사용하는 것을 이해하기가 어려움ㅜ.

 

1) 현재 최대 값 보다 큰 값이 들어옴. 

    가장 끝에 넣어줌. => 가장 늦게 들온 값이 가장 큰 값이라면 당연히 LIS의 길이가 늘어남.

 

2) 현재 최대 값 보다 작은 값이 들어옴. 

 a. 그 값이 가장 작은 값일 때

    가장 작은 값을 들어온 값으로 경신. => LIS의 길이의 변화는 없지만, 그 다음에 들어올 값에 대해 판단이 가능.

 

 b. 그 값이 중간 값일 때

    들어온 값 이상의 값을 중간 값으로 갱신 => 

arr = 1, 4, 5 , 3, 4, 5

memo = {1}

memo = {1, 4}

memo = {1, 4, 5}

memo = {1, 3, 5}

memo = {1,3, 4}

memo = {1, 3, 4, 5}

 

 

+ 세그먼트 트리로 LIS 구하기

https://blog.naver.com/bagzaru/223004433092?trackingCode=rss

Segment Tree로 LIS(최장 증가하는 부분 수열) 길이 구하기 (feat. 백준 12738번)