[백준/자바] dp 11053번 - 가장 긴 증가하는 부분 수열

• 문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

 

 

• 풀이

작은 부분 문제들로 나눠 그 결과를 저장하면서 반복 계산해 (DP) 풀 수 있는 문제이다.

단, 이때 시간복잡도는 이중 for문 연산으로 인해 N^2 이 된다.

 

public class LIS {
	
	public static int[] seq; // 입력값 배열
	public static int[] dp; // DP 배열 (dp[i]는 seq[i]까지의 최장부분수열 길이)
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		// 입력값 배열
		seq = new int[N]; 
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i=0;i<N;i++) {
			seq[i] = Integer.parseInt(st.nextToken());
		}

		// dp 배열
		dp = new int[N];
		dp(N);
	}
	
	private static void dp(int N) {
		dp[0] = 1; 

		for (int i=1;i<N;i++) { // 1~N-1 인덱스까지의 최장부분수열 탐색 시작
			dp[i] = 1;
			
			for (int j=0;j<i;j++) { // 각 인덱스 앞까지 탐색
            	// 기준값이 비교값보다 큼 & 지금까지 구한 dp값보다 크거나 같은 dp 값일 때
				if (seq[i]>seq[j] && dp[i]<dp[j]+1) { 
					dp[i] = dp[j] + 1; // 해당 dp값 + 1로 최신화
				}
			}
		}
		
		Arrays.sort(dp);
		System.out.println(dp[N-1]);
	}

}

 

seq[1]~seq[N]까지의 증가 수열 length를 각각 dp 배열에 저장한 후, dp 배열 내에서 최대값을 구하면 되는 문제다.

ex) dp[3] = seq[3]까지의 최장증가수열 길이, dp[5] = seq[5]까지의 최장증가수열 길이

 

※ dp 값을 구할 때 기준값(seq[i])을 최대값으로 가정한다

예를 들어 dp[3]을 구할 때 무조건 seq[3]의 값을 최장부분수열의 최대값으로 가정한다.

=> seq[3] 앞에 더 큰 값이 있으면 무시한다.

 

 

전반적으로 dp 배열을 채우는 과정은

1. 기준값보다 작은 값들을 조사해

2. dp 배열에 저장해둔 이전 값들의 최장부분수열 length를 초과 시 dp 최대값에 1씩 누적해가는 과정이라고 볼 수 있다.

// 조건 1 : 앞의 값들이 기준값보다 작고 (기준값이 수열의 최대값)
// 조건 2 : 앞의 최장부분수열 length에 1 더했을 때 기준값 최장부분수열 length가 더 작으면 (중간에 감소하는 값 제외시킴 => 증가수열 길이만 누적할 수 있음)
if (seq[i]>seq[j] && dp[i]<dp[j]+1) {

 

 

처음에는 설명을 봐도 dp 배열에 어떤 값을 넣는지, 앞뒤 dp 값을 왜 비교하는지 헷갈렸는데 표를 그려가면서 직접 구해보니 이해되었다.

 

ex)

seq	10	10	20	10	40	20
dp	1	1	2	1	3	2

 

dp[0] = 1

전체 배열 길이가 1 → dp 값도 1으로 세팅한다.

 

dp[1] = 1

조건 1에 부합하는 seq 값 X → 초기값 1이 유지된다.

 

dp[2] = 2

조건 1에 부합하는 값 : seq[0], seq[1]

seq[0] : 조건2에 부합 (1 < 1+1) → dp[2] : 1+1 = 2

seq[1] : 조건2에 부합하지 않는다. (2 < 1+1)

 

dp[3] = 1

조건 1에 부합하는 값 X → 초기값 1이 유지된다.

 

dp[4] = 3

조건 1에 부합하는 값 : seq[0], seq[1], seq[2], seq[3]

seq[0] : dp[4]는 조건2에 부합(1 < 1+1) → 1+1 = 2

seq[1] : dp[4]는 조건2에 부합하지 않는다. (2 < 1+1)

seq[2] : dp[4]는 조건2에 부합(2 < 2+1) → 2+1 = 3

seq[3] : dp[4]는 조건2에 부합하지 않는다. (3 < 1+1)

 

dp[5] = 2

조건 1에 부합하는 값 : seq[0], seq[1], seq[3]

seq[0] : dp[5]는 조건2에 부합(1 < 1+1) → 1+1 = 2

seq[1], seq[3] : dp[5]는 조건2에 부합하지 않는다. (2 < 1+1)

 

 

 

• + 풀이2 (이분탐색)

위 DP 방식보다 더 낮은 시간복잡도로 풀 수 있는 알고리즘으로는 이분탐색이 있다. => O(nlogn) 

 

이 방식에서는 입력값들을 순회하면서 이분탐색을 통해 lis 배열을 업데이트한다.

1. 입력값이 lis 배열 마지막 값보다 클 때 : 입력값을 lis 마지막 값 다음 index에 대입한다.

2. 입력값이 lis 배열 마지막 값보다 작을 때 : lis를 이분탐색한 후 오름차순 정렬했을 때 적절한 위치에 대입한다.

이렇게 만들어진 lis 배열은 정확한 최장부분수열을 갖고 있지 않지만 그 길이를 구할 수는 있다.

 

lis = [1,3,5] 탐색할 입력값 = 2 일 때 -> lis = [1,2,5]

 

위 예시에서는 탐색하는 중인 입력값이 lis에 마지막으로 저장된 5보다 작으므로 lis 내부에 덮어씌워진다. 그리고 덮어쓸 위치를 찾기 위해 lis를 이분탐색한다.

이때 이분탐색 시 lis[0]와 lis[1]의 사이에 놓인 값이기에 하나를 선택해 덮어씌워야 한다. 결과적으로 lis[1]을 덮어쓰는데, 가상 최장부분수열 배열의 값들을 최소값으로 갱신해나가야 하기 때문이다. 

 

입력값 = [4,7,5,6,3,5,7]
lis = [4,5,6,7]

위 예시처럼 이분탐색 후 입력값보다 앞에 있는 값을 덮어쓰면 lis 배열이 최소화가 안 된다. lis에 마지막 값 이후로 대입될 수 있는 값들의 가능성이 축소되는 것이다.

ex.

앞을 덮어쓸 때 lis : [5, 7] 

뒤를 덮어쓸 때 lis : [4, 5, 6, 7]

 

public class LIS2 {

    public static void main(String[] args) throws IOException {
        // 입력값 배열 length
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        // 입력값 배열
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int[] seq = new int[N];
        for (int i=0;i<N;i++) {
            seq[i] = Integer.parseInt(st.nextToken());
        }

        // lis 연산
        System.out.println(lis(seq, N));
    }

    private static int lis(int[] seq, int N) {
        int[] lis = new int[N]; // 가상의 최장부분수열 (오름차순)
        lis[0] = seq[0];

        int lastIndex = 0; // lis에 업데이트된 마지막 인덱스
        for (int i=1;i<N;i++){
            if (seq[i] > lis[lastIndex]){ // 입력값이 lis에 저장된 마지막 값보다 크면
                lis[++lastIndex] = seq[i]; // 이어서 저장
            } else {
                lis[binarySearch(lis, 0, lastIndex, seq[i])] = seq[i]; // lis 이진 탐색 후 적절한 위치에 입력값 덮어쓰기
            }
        }

        return lastIndex + 1; // lis 개수
   }

   private static int binarySearch(int[] lis, int left, int right, int target){
        int mid;

        while (left < right){
            mid = (left + right) / 2;

            if (target > lis[mid]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return right; // 새로 대입할 위치 (lis 인덱스)
   }

}

 

 

 

• 참고

https://code-angie.tistory.com/2

https://jins-dev.tistory.com/entry/%EC%B5%9C%EC%A0%81%ED%99%94%EB%90%9C-LISLongest-Increasing-Subsequence-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EA%B3%BC-%ED%95%B4-%EC%B0%BE%EA%B8%B0

https://seungkwan.tistory.com/8

https://sskl660.tistory.com/89

https://song-ift.tistory.com/253