JLIS(합친 최대 증가 부분수열) 풀이, 오답노트

algospot.com/judge/problem/read/JLIS

algospot.com :: 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 코드>

#include <iostream>
#include <cstring>
using namespace std;

int C, N, arr[500], chk[500];

void LIS(int n)
{
	int tmp;
	chk[0] = 1;
	for (int i = 1; i < n; i++)
	{
		tmp = 0;
		for (int j = i - 1; j >= 0; j--)
		{
			if (arr[i] > arr[j])
			{
				tmp = max(tmp, chk[j]);
			}
		}
		chk[i] = tmp + 1;
	}
}

int main()
{
	cin >> C;
	for (int ci = 0; ci < C; ci++)
	{
		memset(arr, 0, sizeof(arr));
		memset(chk, 0, sizeof(chk));
		cin >> N;
		for (int i = 0; i < N; i++) cin >> arr[i];
		LIS(N);
		int ans = 0;
		for (int i = 0; i < N; i++) ans = max(ans, chk[i]);
		cout << ans << '\n';
	}
}

 

 

LIS를 구현할 때 나는 탐욕법으로 구현했었다.

책에서는 LIS(index)를 index부터 시작해서 만들 수 있는 LIS를 구하며 캐시를 이용하는 dp를 사용했다.

 

LIS푼 방법으로 똑같이 JLIS를 풀려고 했는데, 그리디 방식이었던 내 접근 방법으로는 JLIS에 도저히 적용할 수가 없었다. 

이유는 주어진 두 수열에 중복된 원소가 있으면 그걸 따로 처리하는 코드를 작성할 수가 없었기 때문이다.

중복된 원소를 처음부터 한 수열에서 지우고 시작하는 방법으로도 짜봤지만, 예외 예제가 존재해서 결국 접근 방식을 바꿀 수 밖에 없었다.

 

내 힘이 아닌 책의 코드를 보고 푼 문제이기 때문에 내 것으로 만들기 위해서는 코드 복기가 필요하다고 생각했다.

 

<JLIS 코드 복기하기>

 

<정답코드>

#include <iostream>
#include <cstring>
#include <limits>
using namespace std;

const long long NEGINF = numeric_limits<long long>::min();
int n, m, a1[101], a2[101];
int chk[101][101];

int JLIS(int a, int b)
{
	int& ret = chk[a + 1][b + 1];
	if (ret != -1) return ret;
	ret = 0;
	long long aa = (a == -1 ? NEGINF : a1[a]);
	long long bb = (b == -1 ? NEGINF : a2[b]);
	long long maxElement = max(aa, bb);

	for (int na = a + 1; na < n; na++) 
    {
		if (maxElement < a1[na]) 
        {
			ret = max(ret, JLIS(na, b) + 1);
		}
	}
	for (int nb = b + 1; nb < m; nb++) 
    {
		if (maxElement < a2[nb]) 
        {
			ret = max(ret, JLIS(a, nb) + 1);
		}
	}
	return ret;
}

int main()
{
	int c; cin >> c;
	for (int k = 0; k < c; k++)
	{
		cin >> n >> m;
		memset(chk, -1, sizeof(chk));
		for (int i = 0; i < n; i++) cin >> a1[i];
		for (int i = 0; i < m; i++) cin >> a2[i];
		cout << JLIS(-1, -1) << '\n';
	}
}

 

<다이나믹 프로그래밍을 사용해서 얻는 특징들>

책에서는 함수 parameter로 탐색을 시작하는 index를 넣어서 지금 원소보다 큰 원소가 있을 경우 함수를 재귀하여 채워나가는 방식을 선택했다.

 

이 방법을 선택하여 풀면 생기는 이점은 완전탐색이 가능하다는 점과, 중복되는 원소에 대해서 깔끔하게 넘어갈 수 있는 장치를 만들 수 있다는 것이다.

 

<numeric_limits>

문제 내에서 주어진 원소의 크기 범위를 벗어나서 더 작은 값을 만들어 저장해야한다. (즉, -무한대)

문제에서 원소의 값 범위는 32bit의 부호있는 정수라고 했으므로, 64비트인 long long을 사용해서 가장 작은 값을 만들 수 있으면, 원소 크기 비교를 위한 최소 기준값을 만들어낼 수 있다.

 

const long long NEGINF = numeric_limits<long long>::min();

 

이 줄이 바로 그것을 구현한 줄이다. 이렇게 되면 문제에서 주어진 어떠한 원소보다 작은 값을 NEGINF에 저장할 수 있다.

 

numeric_limits는 #include <limits> 라이브러리를 통해 사용할 수 있었다.

 

<재귀함수 작동방식>

재귀함수의 작동방식은 두 수열의 첫 원소부터 값을 비교하며 큰 것부터 부분 증가 수열에 추가해나가는 식으로 세고, 추가할 때마다 ret를 통해 캐시값으로 하나씩 증가시켜 저장하는 식으로 나아간다. 결국 모든 JLIS를 완전탐색하고 그 중 가장 길이가 긴 값을 리턴하며 끝난다.

 

<참조자 활용>

int& ret = chk[a-1][b-1];

에서 &를 사용했는데, 이는 ret를 단순히 상수를 저장한 변수로 사용하는 것이 아니라, chk[a-1][b-1]과 주솟값을 공유하여 ret를 변경하면 chk[a-1][b-1]의 값도 변할 수 있도록 만들어서 cache값을 저장하는 방식으로 사용한 것이다.

그냥 단순히 chk[a-1][b-1] 대신 (타이핑하기에 너무 기니까) ret를 사용했다고 생각하면 쉽다.