ALGOSPOT - LIS

문제

https://algospot.com/judge/problem/read/LIS

풀이

가장 긴 증가하는 수열의 길이를 찾는 문제이다. 알고리즘 공부를 처음 시작했을무렵 이 문제를 접했을때는 정말 어떻게 풀어야할지 막막했었다 ㅠㅠ. 문제를 풀고 나니 이미 4달전에 해결 한 문제인데 기억이 나지 않는걸 보면 제대로 공부하지 않았던게 아닐까 싶다.

아무튼 이 문제는 처음에 완전 탐색 코드를 짜고 접근했다. 첫번째 수(0번째)부터 N-1번째 수 까지 모든 경우를 돌면서 가장 긴 LIS를 찾는 코드이다.

#include <stdio.h>
int n,num[500];
int max(int a,int b){return a>b?a:b;}
int solve(int pos){
	int i, ret = 0;
	for(i=pos+1;i<n;i++){
		if(num[pos] < num[i]){
			ret = max(ret, solve(i)+1);
		}
	}
	return ret;
}
int main(void) {
	int i,t;
	scanf("%d",&t);
	while(t--){
		int ans = 0;
		scanf("%d",&n);
		for(i=0;i<n;i++){
			scanf("%d",&num[i]);
		}
		for(i=0;i<n-1;i++){
			ans = max(ans, solve(i));
		}
		printf("%d\n",ans);
	}
	return 0;
}

위 코드는 메모이제이션을 적용하지 않은 코드라 같은 값을 여러번 구한다. 그러니 여기서 메모이제이션을 적용해줘야한다. 메모이제이션을 적용할 dp 배열을 만들고 dp[x] = x번째 수부터 시작할때 가장 긴 LIS의 길이의 값을 저장하게 하였다.

#include <stdio.h>
#include <string.h>
int n,num[500],dp[500]; //dp[x] == -1이면 x번째 수부터 시작하는 LIS 길이를 아직 구하지 않은것이다
int max(int a,int b){return a>b?a:b;}
int solve(int pos){
	int i, ret = 1;
	//이미 pos번째 수부터 시작하는 LIS 길이를 구했다면 바로 반환한다.
	if(dp[pos] != -1) return dp[pos];
	
	//pos번째 수보다 뒤에있는 더 큰 모든 수들을 확인하며 LIS의 길이를 찾는다.
	for(i=pos+1;i<n;i++)
		if(num[pos] < num[i])
			ret = max(ret, solve(i)+1);
	//메모이제이션하고 반환한다.
	return dp[pos] = ret;
}
int main(void) {
	int i,t;
	scanf("%d",&t);
	while(t--){
		int ans = 0;
		memset(dp,-1,sizeof(dp));
		scanf("%d",&n);
		for(i=0;i<n;i++)
			scanf("%d",&num[i]);
		//0번째 수부터 n-1번째 수까지 돌면서 LIS 길이를 찾는다.
		for(i=0;i<n-1;i++)
			ans = max(ans, solve(i));
		
		printf("%d\n",ans);
	}
	return 0;
}