[코딩테스트 C++] 가장 긴 증가하는 부분 수열

오늘의 문제

• 급했던, 필기 시험 2개가 끝나고 이제야 여유가 난다. 다시 시작한다.

가장 긴 증가하는 부분 수열

접근 방식

• 이 문제는 '알고리즘연습' 과목을 수강하며 알게된 방식이라 문제를 보고 바로 풀 수 있었다.
• 규칙성에 따라 적용할 수있다. LIS 문제(Longest Increasing Sequence)는 해당 규칙을 따른다.

1. 벡터의 가장 큰 값(마지막 값) 보다 이번 숫자가 크다면 벡터의 마지막에 추가한다.
2. 크지 않다면, 벡터 내에서 lower_bound를 구하여, 더 작은 값으로 대체한다.

• 왜 이런 규칙이 나오는가 하면, sequence를 이루는 수열의 위치는 값의 크기에 따라 정의가 된다.
• 앞에 나온 수 중에서 이번의 나오는 수보다 작은 수의 수열의 크기에서 1이 더해져 수열을 구할 수 있다.
• 앞으로의 숫자에게 영향을 미치므로, 같은 길이를 가진 수 중 가장 작은 값을 선택해야, 다음에 더 큰 값을 이룰 수 있다. 일종의 그리디 작전.

나의 풀이

#include<iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
const int MAX = 1000;
int arr[MAX];

int solution(){
    vector<int> v;
    v.push_back(0);
    for(int i=0;i<n;i++){
        if(v.back() < arr[i]){
            v.push_back(arr[i]);
        }else{
            *lower_bound(v.begin(), v.end(), arr[i]) = arr[i];
        }
    }
    return v.size()-1;
}

다른 풀이

#include <cstdio>
int main()
{
	int n;
	scanf("%d", &n);
	int a[1001];
	int b[1001]={0,};
	int i, j;
	for(i=0;i<n;i++)
	{
		scanf("%d", &a[i]);
	}
	int t;
	int e=0;
	for(i=0;i<n;i++)
	{
		t=0;
		for(j=0;j<i;j++)
		{
			if(a[i]>a[j] && t<b[j]) t=b[j];
		}
		b[i]=t+1;
		if(b[i]>e) e=b[i];
	}
	printf("%d", e);
	return 0;
}

배울 점

• 함수를 사용하지않고 앞에서부터 비교를 하셨다.
• 이 방법이 더 가벼울 것이다.