[문제풀이] 10-03. 최대 부분 증가 수열(LIS)

인프런, 자바(Java) 알고리즘 문제풀이

Dynamic Programming - 1003. 최대 부분 증가 수열(LIS)

🗒️ 문제

🎈 나의 풀이

	private static int solution(int[] arr) {
       int[] dy = new int[arr.length];
       dy[0] = 1;

       for(int i=1; i<arr.length; i++) {
           int cnt = 1;
           for(int j=0; j<i; j++) {
               if(arr[i] > arr[j]) cnt = Math.max(cnt, dy[j] + 1);
           }
           dy[i] = cnt;
       }

       return Arrays.stream(dy).max().getAsInt();
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];

        for(int i=0; i<n; i++) arr[i] = sc.nextInt();

        System.out.println(solution(arr));
    }

🖍️ 강의 풀이

  	static int[] dy;
	public int solution(int[] arr){
		int answer=0;
		dy=new int[arr.length];
		dy[0]=1;
		for(int i=1; i<arr.length; i++){
			int max=0;
			for(int j=i-1; j>=0; j--){
				if(arr[j]<arr[i] && dy[j]>max) max=dy[j];
			}
			dy[i]=max+1;
			answer=Math.max(answer, dy[i]);
		}
		return answer;
	}

	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		int[] arr=new int[n];
		for(int i=0; i<n; i++){
			arr[i]=kb.nextInt();
		}
		System.out.print(T.solution(arr));
	}

💬 짚어가기

해당 문제는 그래프의 Dynamic Programming(동적 계획법)을 통해 풀 수 있다.

수열에서 n 번째 요소가 가질 수 있는 최대 부분 증가 수열의 크기를 배열 dy에 보관한다.
첫 번째 요소를 시작으로(최소 길이는 1) 다음 요소를 순차적으로 확인한다.

n번 째 요소가 이전에 등장하는 n-k 번 째 요소보다 값이 클 때, n-k 번 째 요소가 갖고있는
최대 부분 증가 수열의 크기에 1 증가시킨 값을 n 번 째 요소가 갖도록 한다.

단, 이전 요소들을 모두 검사하여 가질 수 있는 가장 큰 값을 갖도록 한다. 이렇게 마지막 요소까지
과정을 반복하여 확인한 후 dy 배열에서 가장 큰 값(최대 증가 부분 수열의 크기)를 반환한다.