[알고리즘] LIS, 최장 증가 부분 수열 (+백준 11053)

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

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

 

📚 문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 30, 50} 이고, 길이는 4이다.

 

📝 문제 풀이

테이블 정의

• arr[n] : 수열을 저장하는 배열
• dp[n] : 수열의 길이를 저장하는 배열 (n번째 수로 끝나는 부분수열 중 가장 긴 것의 길이를 저장)

/* A = {10, 20, 10, 30, 20, 50} */

dp[0] = 1;	// 10 (10으로 끝나는 부분수열 중 가장 긴 것의 길이를 저장)
dp[1] = 2;	// 10 -> 20
dp[2] = 1;	// 10
dp[3] = 3;	// 10 -> 20 -> 30
dp[4] = 2;	// 10 -> 20
dp[5] = 4;	// 10 -> 20 -> 30 -> 50

점화식 세우기

i번째 원소와 i-1번째 원소와 비교한뒤 0~i-1번째 원소들 중에서 i번째 원소보다 작은 원소들의 dp값들 중 가장 큰 값 + 1을 dp[i]에 저장 (단, j번째 수보다 i번째 수가 클 경우)

dp[i] = Math.max(dp[i], dp[j] + 1)

• dp[0] : 초기값 1
• dp[1] : 0번째보다 크므로 dp[0] + 1 = 2
• dp[2] : 10보다 큰 값이 없으므로 초기값 1
• dp[3] : 0, 1, 2번째보다 크므로 그 중 가장 큰 값인 dp[1] + 1 = 2 + 1 = 3
• dp[4] : 0, 2번째보다 크므로 그 중 가장 큰 값인 dp[0] + 1 = 1 + 1 = 2
• dp[5] : 0, 1, 2, 3, 4번째보다 크므로 그 중 가장 큰 값인 dp[3] + 1 = 4

 

초기값 설정

i 번째의 수들은 모두 수열의 시작점이 될 수 있기 때문에, dp[i]의 값은 모두 1로 초기화

 

💻 코드

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

public class BOJ11053{
    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+1];  
        int[] dp = new int[n+1];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken()); 
            dp[i] = 1;
        }
        
        int max = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < i; j++) {
                if (arr[i] > arr[j]) dp[i] = Math.max(dp[i], dp[j]+1);
            }
            max = Math.max(max, dp[i]);
        }
        
        System.out.print(max);
    }
}

💡 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)란?
원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 한다.

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

풀이 방법으로는 DP와 이진 탐색을 활용한 방법 두가지가 있다. DP를 활용하면 조금 더 단순하지만 시간 복잡도가 O(n^2)이고 이진 탐색을 활용하면 조금 더 복잡하지만 시간 복잡도는 O(nlogn)이다.

📎 참고

- https://iseunghan.tistory.com/342
- https://propercoding.tistory.com/41
- https://chanhuiseok.github.io/posts/algo-49/