ALGOSPOT - 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;
}
