[알고리즘]Algospot_LIS
문제
어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. 단, 10 4 7 은 원래 수열의 순서와 다르므로 10 7 4 9 의 부분 수열이 아니다.
어떤 부분 수열이 순증가할 때 이 부분 수열을 증가 부분 수열 (increasing subsequence) 라고 한다. 주어진 수열의 증가 부분 수열 중 가장 긴 것의 길이를 계산하는 프로그램을 작성하라.
어떤 수열의 각 수가 이전의 수보다 클 때, 이 수열을 순증가 한다고 한다.
입력
입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 가 주어진다. 각 테스트 케이스의 첫 줄에는 수열에 포함된 원소의 수 N (<= 500) 이 주어진다. 그 다음 줄에 수열이 N개의 정수가 주어진다. 각 정수는 1 이상 100,000 이하의 자연수이다.
출력
각 테스트케이스마다 한 줄씩, 주어진 수열의 가장 긴 증가 부분 수열의 길이를 출력한다.
정답코드
#include<bits/stdc++.h>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n'
using namespace std;
int longestSeq(vector<int>& v, vector<int>& c, int pos)
{
//이 코드를 추가해줬더니 정상 작동. why?
if(pos+1==v.size()) return 1;
int &ret = c[pos+1];
if(ret != -1) return ret;
ret = 1;
for(int i = pos+1; i<v.size(); i++)
{
if(pos == -1 || v[pos] < v[i]) ret = max(ret, 1 + longestSeq(v,c,i));
}
return ret;
}
int main()
{
FASTio;
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
vector<int> v(n, 0);
vector<int> c(n, -1);
for(int i=0; i<n; i++)
cin >> v[i];
cout << longestSeq(v,c,-1)-1 << endl;
cout << endl;
}
return 0;
}
풀이 및 사고과정
이 문제에서 많은 시간을 할애했다.
일단 문제를 이해하는데에 조금 시간이 걸렸고
결국엔 책을 참고했는데 DP를 활용하는 부분이 이해가 안돼서 시간이 걸렸고
책과 거의 유사하게 코드를 쳤는데 정답이 안돼서 시간이 걸렸다.
이 문제도 나중에 한 번 더 봐야되는 문제인듯하다
Author And Source
이 문제에 관하여([알고리즘]Algospot_LIS), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@whddnjs5167/알고리즘AlgospotLIS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)