11053 : 가장 긴 증가하는 부분 수열

네르기·2021년 9월 9일

동적 프로그래밍 생각

알고리즘

목록 보기

52/76

어떤 문제인가?

메모이제이션을 이용해 어떤 주어진 수열 중 오름차순으로 증가하는 부분 수열을 찾는 문제.

시행착오 횟수

5번

1차 시도 : 구상

처음에 든 생각.

앞에서부터, 첫번째 수를 기준으로 첫번째 수보다 큰 수들을 먼저 기록한다.
기록한 첫번째 수부터 끝까지 돌면서, 만일 첫번째 수보다 뒤에 있는 어떤 수가 첫번째 수보다 작다면 길이를 1 늘린다.
이때 길이가 최댓값보다 크다면, 최댓값이 곧 길이가 된다.

다음은 위에 대한 반례다.

50, 10, 20, 10, 5, 10, 70

2차 시도 : 구상

내 알고리즘은 시간 복잡도가 $O(N^2)$ 였다. $N$ 이 최대 1,000밖에 되지 않지만, DP를 이용한다면 더 줄일 수 있지 않을까 생각했다.

테스트 케이스들로 쓸 수열들을 계속 쓰다가 갑자기 이런 생각이 들었다.

$A_{j} < A_{j+1}$ 이면, $D_{A_{j}}=D_{A_{j+1}}+1$ 이지 않을까.

그래서 이를 좀 더 다듬었다.

$A_{j} \geq A_{j-1}$ 이라면 $D_{A_{j-1}}=D_{A_{j}}+1$ 이다. 그렇지 않다면 $D_{A_{j-1}} = max(D_{j}-1, 0)$ 이다.

잘만 돌아간다면, 분명히 시간복잡도를 $O(N)$ 로 줄일 수 있었다. 그러나 그런 일은 없었다. 다음은 반례이다.

10, 20, 30, 10, 20, 30

3차 시도 : 구상

맨 오른쪽부터 시작해서, $i$ 번째 수가 $i+1$ 번째 수보다 작다면 $k$ 값을 1씩 증가시킨 후, 반대로 $i$ 번째 수가 $i+1$ 번째 수보다 크거나 같다면 $D_{i}=k+D_{i}$ 처럼 계산했다.

다음은 이에 대한 반례이다.

10 20 30 10 20 50

4차 시도 : 구상

이렇게 되자 스택까지 쓰려고 했다.

맨 끝 원소를 먼저 스택에 집어넣는다. 스택의 첫번째 원소가 배열의 어떤 원소보다 크다면, 해당 원소를 스택에 집어넣는다. 이 때 스택의 현재 크기가 최댓값보다 크다면, 최댓값을 갱신한다. 그 반대로 작거나 같다면 해당 원소보다 큰 원소가 나올때까지 스택에서 원소를 제거한다. 배열에 있는 모든 원소를 전부 탐색하였다면 최댓값을 출력한다.

공책에 쓴 수열 중 어떤 수열이 반례였는지는 기억나지 않지만, 어찌되었건 이것도 틀렸다.

5차 시도 : AC

그래프를 그려보니 내게 남은 방법은 단 하나였다. $O(N^2)$ 를 각오하고 전부 비교하는 방법. 다음은 내 코드다.

#include <stdio.h>

int D[1001],S[1001];

int main()
{
	int N,M=0,i,j;
	scanf("%d",&N);
	for(i=0;i<N;i++) scanf("%d",S+i);
	for(i=N-2;i>=0;i--) {
	    for(j=i+1;j<N;j++) {
	    	if(S[i]<S[j]) D[S[i]]=D[S[i]]>D[S[j]]+1?D[S[i]]:D[S[j]]+1;
	    	if(M<D[S[i]]) M=D[S[i]];
	    }
	}
	printf("%d",M+1);
}

생각해보니, 이렇게 DP를 쓰지 않고 일일히 반복하면서 전부 비교한다면 아래의 경우에는 경우의 수를 나눠서 탐색해야 한다.

10 20 50 30 40

또한 이미 구한 값을 재계산해야 하기 때문에, $O(N^2)$ 보다 더 시간이 걸렸을 것이라 확신한다.

다른 분들의 풀이

int main() {
	int n, x, lis[1000], len=0, i, j;
	
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &x);
		for (j = len;; j--)
			if (lis[j] < x)
				break;
		
		lis[j + 1] = x;
		len = j == len ? j + 1 : len;		
	}
	printf("%d\n", len);
}