[알고리즘 스터디]알고리즘 문제해결전략 LIS

[문제]

주어진 수열에 대해 최대 증가 부분 수열 구하기.

최대 증가 부분수열이란?

- 원소들이 순증가하는 부분수열 중에 가장 긴 것

 

[풀이] 

나의 풀이

n 크기의 수열에 대해 n*n 크기의 이차원 cache를 사용하자.

 

이 문제의 알고리즘은 위와 같다. 

그리고 추가적으로 maxCount를 새 cache값을 계산해서 저장할 때 마다 갱신시켜야 한다.

그 이유는, maxCount가 첫 번째 원소부터 시작한 경우에서 나오지 않을 수 있기 때문이다.

ex) 5,3,4의 경우 최대증가부분수열은 3,4가 된다. 

따라서 모든 cache 내부의 값중에서 최댓값을 찾아야하는데 이 과정을 계산할 때 한번에 하기 위해서 maxCount를 사용한다.

(뒤에 코드를 보면 이해가 더 잘 될 것이다.)

 

알고리즘에 대해 좀 더 복잡한 예시를 적용해보자.

1,3,2,4,6,8 의 수열에 대한 cache를 구해보자

규칙을 적용해서 cache를 모두 채우면 아래와 같다.

 

여기서 중요한 것은, cache 내의 max값에 +1을 해줘야 최종 output이 된다는 것이다.

왜냐하면 cache에서는 최대부분증가수열의 값을 저장할 때 '시작점'의 원소는 세지 않고 저장한다.

ex) 2번째 원소 ~ 5번째 원소 사이의 최대 부분증가 수열의 길이는

2번째 원소 ~ 4번째 원소 사이의 최대 부분증가 수열의 길이  + 4번째 원소 ~ 5번째 원소 사이의 최대 부분증가 수열의 길이 가 된다.

이 과정에서 4번째 원소가 두 번 세어지기 때문에, cache에 값을 저장할 때 시작지점의 원소의 개수를 세지 않고 저장하였다. 

#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
	int n;
	int arr[101];
	int cache[101][101] = { 0, };
	scanf_s("%d", &n);
	for (int i = 0;i < n;i++)
		scanf_s("%d", &arr[i]);

	int maxCount=0;
	for (int i = n - 2;i >= 0;i--) {
		if (arr[i + 1] > arr[i])
			cache[i][i + 1] = 1;
		for (int j = 2;j < n - i;j++) {
			if (arr[i + j] > arr[i]) {
				cache[i][i + j] = cache[i][i + j - 1] + cache[i + j-1][i+j];
				if (cache[i][i + j] > maxCount)
					maxCount = cache[i][i + j];
			}
		}
	}
	printf("result = %d\n", maxCount+1);
	/*
	printf("--cache--\n");
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {
			printf("%d ", cache[i][j]);
		}
		printf("\n");
	}
	*/
	
}

cache와 관련된 for문에서

i를 n-2부터 시작하는 이유는, 맨 마지막줄에는 채울 값이 없기 때문이다. 

j를 2부터 시작하는 이유는, j=1일 때 (바로 다음숫자와 구할 때)를 for문에 들어가기 전에 if문에서 처리해주기 때문이다.

 

정답 풀이 

책에 기재된 풀이는, 재귀와 일차원 cache를 사용하는 방식이었다. 

LIS의 응용문제인 JLIS를 풀기 위해서, 재귀로 접근하는 방법을 알아야 했다.

 

우선, 코드는 이러하다. 

#include <stdio.h>
#include <algorithm>
using namespace std;

int n;
int cache[101], arr[100];

int lis_recursive(int start) {
	int& ret = cache[start + 1];
	if (ret != -1) return ret;
	ret = 1;
	for (int next = start + 1; next < n;next++)
		if (start == -1 || arr[start] < arr[next])
			ret = max(ret, lis_recursive(next) + 1);
	return ret;
}
int main() {
	fill(cache, cache + 101, -1);
	scanf_s("%d", &n);
	for (int i = 0;i < n;i++)
		scanf_s("%d", &arr[i]);
	
	printf("result = %d\n", lis_recursive(-1)-1);
}

cache[i]에는 i+1번째 칸~끝 칸까지의 최대 LIS길이를 저장한다.

특이한 점은, main에서 함수를 호출 할 때 start를 0으로 시작하는 것이 아니라, -1로 시작하는 점이다. 

주어진 수열의 -1번 칸을 -무한대라고 가정하고 풀이하는 방식이다. (모든 시작 위치를 자동으로 시도하기 위해 적용) 

그래서 return 된 ret값에 -1번칸 까지 세어진 것이므로 1을 빼줘야 최종 LIS의 길이가 된다.