자바 최장 증가 부분 수열 (LIS, Longest Increasing Subsequence) 정의 및 작동 원리

최장 증가 부분 수열 (LIS, Longest Increasing Subsequence) 정의

주어진 수열에서 원소들의 순서를 유지하면서 증가하는 가장 긴 부분 수열을 찾는 알고리즘으로 별도로 정렬이 필요 없다.

 

증가하는 부분 수열

증가하는 가장 긴 부분 수열

위 그림은 주어진 배열에서의 증가하는 부분 수열을 나타낸 예시로 최장 증가 부분 수열(LIS)은 두 번째로 보이는 그림이다.

 

 

최장 증가 부분 수열 작동 원리

최장 증가 부분 수열을 찾기 위해서는 다이나믹 프로그래밍(dp)을 사용해야 된다.

 

dp[i]는 i번째 수를 마지막 원소로 가지는 최장 증가 부분 수열의 길이다.

i번째의 LIS 길이를 구하는 방법은 0부터 i-1번째까지의 값에서 i번째 수보다 값이 작고 dp값이 가장 큰 값의 +1이다.

 

위의 그림으로 예제를 보겠다.

arr 배열에 첫 번째 인덱스부터 값을 넣었다고 가정하고, dp 배열도 첫 번째 인덱스부터 보면 된다.

arr[0] = dp[0] = 0이다.

 

두 번째 원소는 1. 이전 원소들 중 값이 작은 건 0이고, dp값은 0

0 + 1 = 1

 

세 번째 원소는 5. 이전 원소들 중 값은 0, 1 중에서 가장 큰 dp값은 1

1 + 1 = 2

 

 

네 번째 원소는 2. 이전 원소들 중 값이 작은 건 1이고, dp값은 1

1 + 1 = 2

 

다섯 번째 원소는 3. 이전 원소들 중 값이 작은 건 0, 1, 2 중에서 가장 큰 dp값은 2

2 + 1 = 3

 

여섯 번째 원소는 6. 이전 원소들 중 값이 작은 건 0, 1, 5, 2, 3 중에서 가장 큰 dp값은 3

3 + 1 = 4

 

마지막 원소는 7. 이전 원소들 중 값이 작은 건 0, 1, 5, 2, 3, 6 중에서 가장 큰 dp값은 4

4 + 1 = 5

 

dp 배열을 완성했다면 가장 큰 값을 찾으면 된다.

arr 배열의 최장 증가 부분 수열의 값은 5

 

 

최장 증가 부분 수열 구현 (Java)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
		
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N+1];
        int[] dp = new int[N+1];
		
        st = new StringTokenizer(br.readLine());
        for (int i=1; i<=N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
		
        int max = 0;
        for (int i=1; i<=N; i++) {
            for (int j=0; j<i; j++) {
                
                // 이전 원소들 중 가장 큰 dp값에서 +1
                if (arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
			
            // LIS 개수 구하기
            max = Math.max(dp[i], max);
        }
		
        System.out.println(max);
    }
}