[코딩테스트] 다이나믹 프로그래밍(가장 긴 증가하는 부분 수열)

reference : 2021 코딩테스트 기초(최백준) 강의를 공부하며 정리한 내용입니다.

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

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

문제

• 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제, 수열 길이 출력

풀이

• Longest Increasing Subsequence = LIS 문제
• 부분 수열 : 수열 수를 선택해서 만드는 수열, 수열에 있던 수의 순서 변경 불가능
• 부분 수열을 만드는 건 2ⁿ 이고 n≤1000이기 때문에 다이나믹 이용해야 함.
• D[i] = A[1]부터 A[i]까지 있고 A[1],A[2]가 존재하는 LIS 구하고 A[1],A[2],A[3]이 존재하는 LIS 구하고… 반복, 이 때 A[i]를 마지막으로 하는 LIS의 길이
• A[i] 앞에 와야 하는 수는 알 수 없기에 A[j] 처럼 변수를 사용. j는 j < i 이며(부분수열은 순서 바뀔 수 없으니) A[j] < A[i] 이다. A[i] 앞의 부분수열은 A[j]를 마지막으로 하는 LIS고 길이는 D[j]가 됨. 여기에 A[i]가 더해지면 길이는 식에 +1을 하면 된다.
• D[i] = max(D[j])+1 (j < i, A[j] < A[i])
• 시간복잡도 : N(N개에 대해 문제를 구하고) x N(하나 값 구하기 위해 N개 검사해야함) = O(N²)

import java.util.*;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int a[] = new int[n];
		for(int i=0; i<n; i++) {
			a[i] = sc.nextInt();
		}
		int d[] = new int[n];
		for(int i=0; i<n; i++) {
			d[i] = 1; //최소값을 먼저 설정해준다. 최소값은 0이 아닌 1임! 본인 하나 들어간
			for(int j=0; j<i; j++) {
				if(a[j]<a[i] && d[i] < d[j]+1)
					//d[i]<d[j]+1은 a[i]앞 부분수열은 a[j]를 마지막으로 하는 길이 d[j]인 LIS니까
					d[i] = d[j]+1;
			}
		}
		int ans = d[0];
		for(int i=0; i<n; i++) {
			if(ans<d[i])
				ans = d[i];
		}
		System.out.println(ans);
	}
}

가장 긴 증가하는 부분 수열(14002번)

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

문제

• 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제, 수열과 수열 길이 출력

풀이

• 어떤 d라는 배열이 앞쪽의 다른 배열에 의해 바뀔때 이걸 ‘역추적’한다고 한다. 역추적할 때 어떤 값이 변경되었을 때 왜 변경되는지 기록하면 그 때 답도 구할 수 있다.
• V[i] = A[i] 앞에 와야 하는 수의 인덱스(A[i]앞에 A[V[i]]일때 길이가 가장 길다), V[i] = j

• LIS의 길이는 D[1]~D[N] 까지의 최댓값

  i	0	1	2	3	4	5
  A[i]	10	20	10	30	20	50
  D[i]	1	2	1	3	2	4
  V[i]	0	1	0	2	3	4

• LIS는 A[6]으로 끝나고, V[i]를 활용하면 그 앞에 A[4], 그 앞에 A[2], 그 앞에 A[1] 이런식으로 역추적
• 재귀 A[p]로 끝나는 LIS구한다고 하면 go(p) -> go(v[p]) 후 a[p] 출력 / 또는 저 표 과정을 코드로 구현

import java.util.*;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int a[] = new int[n];
		for(int i=0; i<n; i++) {
			a[i] = sc.nextInt();
		}
		int d[] = new int[n];
		int v[] = new int[n];
		for(int i=0; i<n; i++) {
			d[i] = 1;
			for(int j=0; j<i; j++) {
				if(a[j]<a[i] && d[i] < d[j]+1) {
					d[i] = d[j]+1;
					v[i] = j;
				}
			}
		}

		int ans = d[0];
		int m = 0;
		for(int i=0; i<n; i++) {
			if(ans<d[i]) {
				ans = d[i];
				m = i;
			}
		}
		System.out.println(ans);

		//m은 D[i]가 최댓값인 i
		int s[] = new int[d[m]+1];
		while(m!=0) {
			s[d[m]] = m;
			m = v[m];
		}

		for(int i=1; i<s.length; i++) {
			System.out.print(a[s[i]]+" ");
		}

	}
}

-> 풀이에 있는 재귀방법이 아니라 표를 구현하는 방법을 사용했다. 부분 수열에서 m=0이 최소값일땐 while문이 m!=0까지만 도니까 while문에선 배열 s에 m=0값은 안 들어가지만 int 배열 기본값이 0이니까 정답 잘 나온다~! m=1이 최소일땐 알아서 값 잘 들어가고..

연속합(1912번)

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

문제

• n개의 정수로 이루어진 임의의 수열, 이 중 연속된 몇 개의 숫자를 선택해 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 숫자는 한 개 이상 선택해야 함.
• 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 일 경우 정답은 12+21 = 33

풀이

• 음수를 빼버리는 건 3, -1, 3 같은 경우가 있기에 안됨
• D[i] = i번째 수로 끝나는 가장 큰 연속합.
• 점화식을 구했으면 i번째 수에게 가능한 경우를 세야함. 이건 다시 생각해 보면 A[i-1]로 끝나는 가장 큰 연속합 뒤에 A[i]가 추가된 것. 따라서 D[i-1] + A[i]
• i-1번째 수 A[i-1]과 연속하는 경우 + A[i]
• D[i] = max(A[i] , D[i-1]+A[i])
• 총 N개값을 계산하는데 비교할 때 두개 값을 비교하니까 O(N)

import java.util.*;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		for(int i=0; i<n; i++) {
			a[i] = sc.nextInt();
		}
		int[] d = new int[n];
		for(int i=0; i<n; i++) {
			d[i] = a[i];
			if(i==0) continue;
			if(d[i]<d[i-1]+a[i]) {
				d[i] = d[i-1]+a[i];
			}
		}
		int ans = Integer.MIN_VALUE;
		for(int i=0; i<n; i++) {
			if(ans<d[i])
				ans = d[i];
		}
		System.out.println(ans);
	}
}