[종만북]8.동적 계획법-합친 LIS

문제

출처 : https://www.algospot.com/judge/problem/read/JLIS

어떤 수열에서 0개 이상의 숫자를 지운 결과를 원 수열의 부분 수열이라고 부릅니다. 예를 들어 ‘4 7 6’은 ‘4 3 7 6 9’의 부분 수열입니다. 중복된 숫자가 없고 오름 차순으로 정렬되어 있는 부분 수열들을 가리켜 증가 부분 수열이라고 부르지요. 예를 들어 ‘3 6 9’는 앞의 수열의 증가 부분 수열입니다.

두 개의 정수 수열 A 와 B 에서 각각 증가 부분 수열을 얻은 뒤 이들을 크기 순서대로 합친 것을 합친 증가 부분 수열이라고 부르기로 합시다. 이 중 가장 긴 수열을 합친 LIS(JLIS, Joined Longest Increasing Subsequence)이라고 부릅시다. 예를 들어 ‘1 3 4 7 9’ 은 ‘1 9 4’ 와 ‘3 4 7’ 의 JLIS입니다. ‘1 9’ 와 ‘3 4 7’ 을 합쳐 ‘1 3 4 7 9’를 얻을 수 있기 때문이지요.

A 와 B 가 주어질 때, JLIS의 길이를 계산하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 c ( 1 <= c <= 50 ) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 A 와 B 의 길이 n 과 m 이 주어집니다 (1 <= n,m <= 100). 다음 줄에는 n 개의 정수로 A 의 원소들이, 그 다음 줄에는 m 개의 정수로 B 의 원소들이 주어집니다. 모든 원소들은 32비트 부호 있는 정수에 저장할 수 있습니다.

출력

각 테스트 케이스마다 한 줄에, JLIS 의 길이를 출력합니다.

풀이(책 참고)

해당 문제를 풀이에 앞서, 기본적인 LIS 문제를 해결하는 방법을 정의해야 한다. 이 책을 보기 전 기존에 내가 풀었던 LIS 문제의 동적 계획법 풀이는 다음과 같다.

// A = 입력받은 배열, B = 메모이제이션(해당 인덱스에서 시작하는 LIS의 요소 수)
for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= i; j++) {
				if (A[j] < A[i] && B[i] <B[j]+1) {
					B[i] = B[j] + 1;
				}
			}
		}

2중 반복문으로 입력받은 배열 A를 모두 순회하면서 배열의 시작 부분부터 현재 위치까지의 요소들을 각각 비교하여, 값이 기존값보다 작은경우에 해당 위치의 LIS 요소수를 더하였다. 이렇게 배열의 모든 부분을 순회하면서 메모이제이션을 통해 B에 각각의 인덱스에서 시작하는 LIS의 요소수를 기록하고, 여기서 B의 최대값을 뽑아 최대 LIS 길이로 산출하였다.

이를 책의 방식대로 풀면 다음과 같다.

// A = 입력받은 배열, cache = 메모이제이션(해당 인덱스에서 시작하는 LIS의 요소 수)
static int LIS(int start) {
		int ret = cache[start + 1];
		if (ret != 0)
			return ret;
		ret = 1;
		cache[start + 1] = ret;
		for (int next = start + 1; next < n; next++) {
			if (start == -1 || A[start] < A[next]) {
				ret = Math.max(ret, LIS(next) + 1);
				cache[start + 1] = ret;
			}
		}
		return ret;

	}

책에서는 이를 재귀함수로 풀었다. 마찬가지로 매개변수 start 인덱스에서 시작하는 LIS의 요소 수를 반환하도록 정의하였고, 메모이제이션 또한 이를 저장하도록 하였다. 핵심은, -1 인덱스에서 매우 작은 값을 초기값으로 갖도록 하여 시작위치를 고정함으로써 최댓값을 찾을필요 없이 -1 위치에서 시작하는 LIS를 최대 길이로 설정한 것이다.

JLIS의 경우, 입력으로 배열을 두 개 받아서 각 배열의 LIS를 추출하여 합친 LIS를 얻기 때문에, 시작 위치가 2차원으로 각 배열의 인덱스를 받을 때, 해당 인덱스에서 시작하는 JLIS의 길이를 메모이제이션을 통해 저장하도록 구현한다. 마찬가지로 -1 인덱스에는 매우 작은 값을 넣도록 구현하여 (-1, -1) 위치에서 최대 길이를 갖도록 하는데, 이 때 중요한 것은 합친 LIS를 이어나갈 때, 두 배열에서 가장 큰 값보다 더 큰 값을 이어나가야 하기 때문에 해당 인덱스의 값들 중 최댓값을 계산하여 각각의 배열에서 다음 인덱스의 값과 비교하도록 한다.

static int JLIS(int a, int b) {
		int ret = cache[a+1][b+1];
		if(ret!=-1) return ret;
		
		ret = 0;
		cache[a+1][b+1] = 0;
		
		long val_a = a==-1?Long.MIN_VALUE:A[a];
		long val_b = b==-1?Long.MIN_VALUE:B[b];
		
		long max = Math.max(val_a, val_b);
		
		for(int next_a=a+1;next_a<n;next_a++)
			if(max<A[next_a]) {
				ret = Math.max(ret, JLIS(next_a, b)+1);
				cache[a+1][b+1] = ret;
			}
		for(int next_b=b+1;next_b<m;next_b++)
			if(max<B[next_b]) {
				ret = Math.max(ret, JLIS(a,next_b)+1);
				cache[a+1][b+1] = ret;
			}
		return ret;
		
		
	}

입력으로 받은 A배열과 B배열을 재귀함수 내에서 각각 해당위치로부터 비교하는 반복문을 나란히 사용한 것을 볼 수 있다. 이를 통해 현재 위치로부터 A 또는 B 배열에서 이어나갈 요소를 찾아 JLIS를 출력하도록 구현할 수 있다.

Menu

문제

입력

출력

풀이(책 참고)