[BOJ/백준] 가장 긴 증가하는 부분 수열(LIS) 시리즈 (Java)

문제 정리

문제 링크	티어	시간복잡도	알고리즘
가장 긴 증가하는 부분 수열	실버 2	O(n^2)	DP
가장 긴 증가하는 부분 수열 2	골드 2	O(nlogn)	이분탐색
가장 긴 증가하는 부분 수열 3	골드 2	O(nlogn)	이분탐색
가장 긴 증가하는 부분 수열 4	골드 4	O(n^2)	DP + 부분 수열 구하기
가장 긴 증가하는 부분 수열 5	플래 5	O(nlogn)	이분탐 + 부분 수열 구하기

 

가장 긴 증가하는 부분 수열 : DP / O(n^2)

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

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

n이 1000까지 이기 때문에 O(n2) 의 시간복잡도로 풀어도 괜찮은 문제이다.

1. dp 배열의  모든 값을 1로 초기화
2. 현재 위치 i 보다 이전에 있는 원소 j가 작은지 확인 ( j < i )
3. 원소 j 가 원소 i 보다 작다면, dp[i] 값과 dp[j]에서 1 더한값을 비교해 더 큰값으로 변경
4. dp 배열의 최댓값 출력

 

수열 A가 주어졌을 때,

10

20

10

30

20

50

i = 2 까지의 dp 배열은 다음과 같다.

1

2

1 (여기까지 구함)

1

1

1

이제 30 (i = 3)과 그 전 원소들을 비교할것이다.

j = 0, 10 < 30 이고, 1 < 1 + 1 이므로 dp[3]은 2가 된다.

j = 1, 20 < 30 이고, 2 < 2 + 1 이므로 dp[3]은 3이 된다.

j = 2, 10 < 30 이고, 3 > 1 + 1 이므로 dp[3]은 바뀌지 않는다.

 

이 과정을 반복하면 주어진 예제에서 완성된 dp 배열은 다음과 같다.

1

2

1

3

2

4

따라서 답은 4이다.

 

소스코드

  

    
    
    
    
  
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[] nums = new int[n];
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int res = 0;

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

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }

        System.out.println(res);
    }
}

 

 

가장 긴 증가하는 부분 수열 2, 3 : 이분탐색 / O(nlogn)

12015 가장 긴 증가하는 부분 수열 2

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

12738 가장 긴 증가하는 부분 수열 3

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

 

n이 1 ≤ N ≤ 1,000,000 / 1 ≤ N ≤ 1,000,000 으로, 두 문제 다 DP로 O(n2) 풀이로 푼다면 시간초과가 날 것이다.

DP 풀이에선 i보다 앞에있는 모든 j에 대해 검토했었다. 하지만 굳이 모든 수를 볼 필요가 있을까?

 

가장 긴 LIS를 구하기 위해선, 원소들 간의 차이가 작을수록 긴 LIS를 구할수 있다.

 

다음과 같이 배열 A가 주어진다.

i	0	1	2	3	4	5	6	7	8
A[i]	10	20	40	25	20	50	30	70	85

LIS는 10, 20, 40, 50, 70, 85로 길이 6인 배열이 될 것이다.

 

Binarysearch를 이용해 O(nlogn)의 시간복잡도로 LIS의 길이를 구하는 방법은 다음과 같다:

• 임의의 배열 L을 생성한다. size는 0이다.
• i=0 부터 순회하며 L의 가장 마지막 원소보다 A[i]가 더 클 경우 L의 맨 뒤에 A[i]를 추가하고 size를 1 증가시킨다.
• L의 가장 마지막 원소보다 A[i]가 더 작을 경우 Binarysearch로 A[i]가 오름차순을 유지하면서, 들어갈 자리를 찾고 그 자리의 값을 A[i]의 값으로 대체한다. size는 그대로 유지한다.
• L 배열의 길이이자 size의 값이 답이 된다.

 

LIS를 구하기 위해, 임의의 배열 L을 만든다. 초기 L은 비어있으므로, 10을 넣어준다. (size = 1)

i = 1일때, 20은 10보다 크므로 20을 끝에 추가한다. (size = 2)

i = 2일때, 40은 20보다 크므로 끝에 40을 추가한다. (size = 3)

i	0	1	2	3	4	5	6	7	8
L[i]	10	20	40

 

i = 3일때, 25는 20보단 크고 40보다는 작다. 40을 25로 대체한다.

만약 바로 뒤에 30이 오고, 40을 25로 대체하지 않았다면 LIS배열에 30을 추가하지 못해 LIS를 구하지 못했을 것이다.

i	0	1	2	3	4	5	6	7	8
L[i]	10	20	25

 

이 과정을 반복해 나가면 결과는 이렇게 된다.

i	0	1	2	3	4	5	6	7	8
L[i]	10	20	25	30	70	85

LIS의 길이는 6으로, 답은 6이다.

 

하지만 여기서 주목해야 할 것이, L배열이 실제 LIS와 다를 수 있다는 것이다.

수열상에 뒤에 있던 원소가 먼저 들어온 원소보다 이분 탐색으로 된 최적의 위치가 앞에 있을 수 있기 때문이다.

실제 LIS배열을 구하는 것은 뒤의 다른 문제에서 한다.

 

Binarysearch 알고리즘을 직접 구할 순 있지만 자바에서는 Arrays.binarySearch() 로 구할 수 있다.

찾고자 하는 원소가 배열에 있을 경우엔 해당 원소의 위치 인덱스를 반환하고,

찾고자 하는 원소가 배열에 없을 경우엔 key보다 greater한 최초의 위치 * (-1) -1 값을 리턴한다.

 

우리가 찾고자 하는것은 key보다 greater한 최초의 위치이기 때문에

Arrays.binarySearch로 찾은 인덱스가 0보다 작을 경우 -1을 곱하고,  -1을 빼주어 인덱스를 구한다.

만약 그게 가장 끝 위치일 경우 size를 늘려준다.

 

소스코드

  

    
    
    
    
  
public class Main {

    public static int n;

    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());
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        int[] list = new int[n];

        int size = 0;
        for (int i = 0; i < n; i++) {
            int idx = Arrays.binarySearch(list, 0, size, nums[i]);
            if (idx < 0) idx = idx * (-1) - 1;
            list[idx] = nums[i];
            if (idx == size) size++; // 끝에 들어갔을 경우
        }

        System.out.println(size);
    }
}

 

 

가장 긴 증가하는 부분 수열 4 : DP + 추적 / O(n^2)

가장 긴 증가하는 부분 수열 4

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

11053 문제에서 실제 부분 수열까지 출력하는 문제이다.

dp 배열 말고도, memo라는 배열을 하나 더 만든다.

 

dp[i]가 초기화 될 때, dp[i]가 어디로부터 온 원소인지 메모를 한다.

그렇게 하면 이런 결과가 나온다.

 

i	0	1	2	3	4	5
A[i]	10	20	10	30	20	50
dp[i]	1	2	1	3	2	4
memo[i]	0	0	0	1	0	3

 

LIS는 4이고, dp[i]가 4일때 인덱스는 5이다. max_idx = 5, max_int는 4이다.

i = 3일때,  결과 배열에 A[max_idx] = A[5]인 50을 추가한다. memo[5]가 3이므로, max_idx가 3이 된다.

i = 2일때,  결과 배열에 A[max_idx] = A[3]인 30을 추가한다. memo[3]이 1이므로, max_idx가 1이 된다.

i = 1일때,  결과 배열에 A[max_idx] = A[1]인 20을 추가한다. memo[1]이 0이므로, max_idx가 0이 된다.

i = 0일때,  결과 배열에 A[max_idx] = A[0]인 10을 추가한다.

 

그럼 결과 배열이 50, 30, 20, 10이 되고 이를 거꾸로 출력하면 그게 답이다.

 

 

소스코드

  

    
    
    
    
  
public class Main {

    public static int n;

    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());
        int[] nums = new int[n];
        int[] dp = new int[n];
        int[] memo = new int[n];

        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
            dp[i] = 1;
        }

        int max_idx = 0;
        int max_val = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    memo[i] = j; // i는 j로부터 옴
                }
            }

            if (dp[i] > max_val) {
                max_val = dp[i];
                max_idx = i;
            }
        }

        int[] res = new int[max_val];

        for (int i = max_val - 1; i >= 0; i--) {
            res[i] = nums[max_idx];
            max_idx = memo[max_idx];
        }

        System.out.println(max_val);
        for (int i = 0; i < max_val; i++) {
            System.out.print(res[i] + " ");
        }

    }
}

 

 

가장 긴 증가하는 부분 수열 5 : 이분탐색 + 추적 / O(nlogn)

14003 가장 긴 증가하는 부분 수열 5

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

무려 플레문제다. 2,3번에 실제 LIS를 구하는 로직을 추가하면 된다.

 

4번 문제와 똑같이 memo라는 배열을 추가하고, 어디로부터 온 원소인지 메모를 한다. 그럼 결과가 이렇게 된다.

아래 표에서 L이 이분탐색으로 구한 임시 lis 배열이다.

i	0	1	2	3	4	5
A[i]	10	20	10	30	20	50
L[i]	10	20	30	50	0	0
memo[i]	0	1	0	2	1	3

idx = 3으로 출발해, 하나씩 줄여가면서 어느 원소로부터 L[i]가 만들어졌는지 구하면 된다.

 

 

소스코드

  

    
    
    
    
  
public class Main {

    public static int n;

    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());
        int[] nums = new int[n];
        int[] lis = new int[n];
        int[] memo = new int[n];
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        int size = 0;
        for (int i = 0; i < n; i++) {
            int idx = Arrays.binarySearch(lis, 0, size, nums[i]);
            if (idx < 0) idx = idx * (-1) - 1;
            memo[i] = idx;
            lis[idx] = nums[i];
            if (idx == size) size++;
        }

        int idx = size - 1;
        int[] answer = new int[size];

        for (int i = n - 1; i >= 0; i--) {
            if (memo[i] == idx) {
                answer[idx--] = nums[i];
            }
        }

        sb.append(size).append("\n");
        for (int i = 0; i < size; i++) {
            sb.append(answer[i]).append(" ");
        }

        System.out.println(sb);
    }
}