백준 11053번: 가장 긴 증가하는 부분 수열 [DP][LIS] - Java

www.acmicpc.net/problem/11053

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

LIS (Longest Increasing Subsequence) 알고리즘의 대표적 문제이다.

 

LIS알고리즘이란?

수열에서 특정 부분을 지워서 부분적으로 증가하는 수열을 만드는 것이다.

 

해결방법에는 1. 완전탐색 , 2. DP , 3.이분탐색이 있는데 나는 2번 DP로 구현하였다.

 

dp[] 배열에는 각 인덱스별 증가 수열의 최장길이를 넣어준다.

 

수열이 주어지면.. 2중 for문을 통해

기준이 되는 수 i 를 잡고 0부터 i-1까지를 비교하는 수 j 로  i 와 j의 숫자 비교를 한다.

앞의 수가 나보다 작으면 그 숫자의 증가수열 최장길이값+1을 해준다.

이렇게되면 내 바로앞의 숫자까지 갈때까지 여러번 dp[]에 갱신이 일어난다.

 

*주의점: 이미 바로 앞의 숫자가 갖고있는 최장수열길이보다 내가 지금 갖고있는 수가 더 큰지를 비교해야한다.

예를들어 , { 10, 20, 10, 30 } 수열에서 i가 30일때

10에서는 dp[]가 2

20에서는 dp[]가 3

10에서는 dp[]가 2 가 된다..

그러면 30에서는 바로앞인 10이랑 비교하기때문에 dp[]가 3이 되는데...

{10,30}길이 된것보다 {10,20,30}길이가 더 길기때문에, 바로 앞 10의 dp[]와 가장 마지막으로 갱신했던 30의 dp[]의 값을 비교해준다... (코드에서 dp[j]+1 > dp[i] 의 부분이 이와 같다.)

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static int[] arr;
	public static int[] dp;
	public static int max = Integer.MIN_VALUE;

	public static void main(String[] args) throws NumberFormatException, IOException {


		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		arr = new int[N];
		dp = new int[N]; // 인덱스 별 증가 부분 수열의 최장길이
		String s = br.readLine();
		StringTokenizer st = new StringTokenizer(s);

		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		dp[0] = 1; // 첫번째는 늘 1이 최장길이이다. 앞에 수가 없기때문에..

		// 자기보다 앞에있는 숫자들의 크기를 비교한다.
		// 크기 비교해서 그 숫자의 최장증가수열길이 +1 를 자신의 최장증가수열길이로 지정한다.
		// 자기 바로앞의 숫자까지 갈때가지 최장증가수열길이는(dp) 여러번 갱신될 수 있다.
		for (int i = 0; i < N; i++) {
			dp[i] =1;
			for (int j = 0; j < i; j++) {
				if (arr[i] > arr[j] && dp[j] + 1 > dp[i]) // arr[i]>arr[j]는 앞의 수가 나보다 큰지? dp[j]+1 > dp[i]는 이미 알고있는 더 긴
															// 최장수열이 있는지?
					dp[i] = dp[j] + 1;

			}
			max = Math.max(max, dp[i]);
		}

		System.out.println(max);

	}

}

 

오홍홍 어려워랑

shoark7.github.io/programming/algorithm/3-LIS-algorithms

LIS의 길이를 구하는 3가지 알고리즘