[알고리즘] 최장 증가 수열(LIS, Longest Increasing Subsequence)

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

최장 증가 수열이란 어떤 수열이 주어졌을 때, 최장으로 증가하는 부분 수열을 말한다.

 

즉, 1, 2, 3, ..., i, i+1, i+2, ..., n까지의 수열 a[n]이 주어졌을 때,

 

a[i] <= a[i+1] <= a[i+2] <= ... 를 만족하는 부분 수열 중 가장 긴 부분 수열을 의미한다.

 

예를 들어, a[n] = {1, 3, 4, 5, 2, 3, 4, 9}라는 수열이 주어졌다면

 

1번째 원소까지{1, 3, 4, 5, 2, 3, 4, 9}의 최장 증가 수열은 {1}이므로 길이가 1이다.

 

2번째 원소까지{1, 3, 4, 5, 2, 3, 4, 9}의 최장 증가 수열은 {1, 3}이므로 길이가 2가 된다.

 

3번째 원소까지{1, 3, 4, 5, 2, 3, 4, 9}의 최장 증가 수열은 {1, 3, 4}이므로 길이가 3이 된다.

 

4번째 원소까지{1, 3, 4, 5, 2, 3, 4, 9}의 최장 증가 수열은 {1, 3, 4, 5}이므로 길이가 4가 된다. 

 

5번째 원소까지{1, 3, 4, 5, 2, 3, 4, 9}의 최장 증가 수열은 {1, 3, 4, 5}이므로 길이가 그대로 4이다. 

 

n번째 원소까지 모두 구하면

 

최장 길이 수열은 {1, 3, 4, 5, 2, 3, 4, 9} 빨간 숫자들로 이루어진 수열 {1, 2, 4, 5, 9}이고 길이는 5가 된다.

 

최장 증가 수열 과정

최장 증가 수열은 동적 계획법(DP, Dynamic Programming)을 이용해 풀 수 있다.

 

a[n]라는 수열이 주어졌을 때, n크기의 배열에다가 i부터 n원소까지 각각의 최장 길이를 저장하는 방식이다.

 

a[n] = {1, 3, 4, 5, 2, 3, 4, 9}이라 하고, 각각의 최장 길이를 기록하는 배열를 dp[n]이라고 했을 때, 

 

 

a[n] = {1, 3, 4, 5, 2, 3, 4, 9}

dp[n] = {1, 0, 0, 0, 0, 0, 0, 0}

 

첫번째 원소까지 탐색을 하면 원소가 하나밖에 없으므로 최장 길이는 무조건 1이다.

 

a[n] = {1, 3, 4, 5, 2, 3, 4, 9}

dp[n] = {1, 2, 0, 0, 0, 0, 0, 0}

 

두번째 원소까지 탐색을 하면 {1, 3}이 되므로 길이는 2이다.

 

a[n] = {1, 3, 4, 5, 2, 3, 4, 9}

dp[n] = {1, 2, 3, 0, 0, 0, 0, 0}

 

세번째 원소까지 탐색을 하면 {1, 3, 4}이 되므로 길이는 3이다.

 

a[n] = {1, 3, 4, 5, 2, 3, 4, 9}

dp[n] = {1, 2, 3, 4, 0, 0, 0, 0}

 

네번째 원소까지 탐색을 하면 {1, 3, 4, 5}이 되므로 길이는 4이다.

 

a[n] = {1, 3, 4, 5, 2, 3, 4, 9}

dp[n] = {1, 2, 3, 4, 2, 0, 0, 0}

 

다섯번째 원소까지 탐색을 하면 {1, 2}이 되므로 길이는 2이다.

 

a[n] = {1, 3, 4, 5, 2, 3, 4, 9}

dp[n] = {1, 2, 3, 4, 2, 3, 0, 0}

 

여섯번째 원소까지 탐색을 하면 {1, 2, 3}이 되므로 길이는 3이다.

 

a[n] = {1, 3, 4, 5, 2, 3, 4, 9}

dp[n] = {1, 2, 3, 4, 2, 3, 4, 0}

 

일곱번째 원소까지 탐색을 하면 {1, 2, 3, 4}이 되므로 길이는 4이다.

 

a[n] = {1, 3, 4, 5, 2, 3, 4, 9}

dp[n] = {1, 2, 3, 4, 2, 3, 4, 5}

 

여덜번째 원소까지 탐색을 하면 {1, 3, 4, 5, 9}이 되므로 길이는 5이다.

 

최장 길이의 패턴을 살펴보면,

 

i번째 원소까지의 최장 길이 dp[i]는 이전까지 원소의 최장길이 + 1이 된다. 즉,

 

j번째 원소 (1 <= j < i)가 a[i] >= a[j] 와 dp[j] + 1 > dp[i]를 만족할 때,

 

dp[i] = dp[j] + 1이 된다.

 

최장 증가 수열 구현

package algorithm;

import java.util.*;

public class LIS {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			int n = sc.nextInt();
			int[] a = new int[n];
			int[] dp = new int[n];
			int max = 0;
			for(int i = 0; i < n; i++) {
				a[i] = sc.nextInt();
			}
			
			dp[0] = 1;
			
			for(int i = 1; i < n; i++) {
				dp[i] = 1;
				for(int j = 0; j < i; j++) {
					if(a[i] >= a[j] && dp[j] + 1 > dp[i]) dp[i] = dp[j] + 1;
				}
				max = Math.max(max,dp[i]);
			}
			System.out.println("#" + t + " " + max);
		}
	}
}