알고스팟 알고리즘: Longest Increasing Sequence(LIS) [C++]

문제 출처: https://algospot.com/judge/problem/read/LIS

algospot.com :: LIS

1. 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector <int> a)
{
	int ret = 0;
	vector <int> b;					//최대 길이 저장
	for (int i = 0; i < a.size(); i++)		//기준
	{
		int longest = 0;
		for (int j = 0; j < i; j++)		//이전의 값들 비교
			if (a[j] < a[i] && longest < b[j])
				longest = b[j];

		b.push_back(longest + 1);		//자기 자신 포함
		ret = max(ret, b[i]);
	}
	return ret;
}

int main(void)
{
	int C;
	cin >> C;

	while (C--)
	{
		int N;
		cin >> N;
		vector <int> arr;

		int temp;
		for (int i = 0; i < N; i++)
		{
			cin >> temp;
			arr.push_back(temp);
		}
		cout << solution(arr) << endl;
	}
}

(실행)

2. 풀이

int solution(vector <int> a)
{
	int ret = 0;
	vector <int> b;		//최대 길이 저장
	for (int i = 0; i < a.size(); i++)		//기준
	{
		int longest = 0;
		for (int j = 0; j < i; j++)			//이전의 값들 비교
			if (a[j] < a[i] && longest < b[j])
				longest = b[j];

		b.push_back(longest + 1);	//자기 자신 포함
		ret = max(ret, b[i]);
	}
	return ret;
}

이중 반복문을 통해서 해결할 수 있는데 왼쪽부터 끝까지 검사를 하는데 기준이 되는 수 이전의 값들과 비교하여 그 값보다 크고 현재의 최대 길이의 값이 작다면 해당 인덱스 값에 위치한 최대 길이 값을 저장한 뒤 그 값을 +1을 추가시켜 저장한다. 그리고 그 값들 중 가장 큰 값을 출력하면 이 문제는 쉽게 해결할 수 있다.

3. 느낀점

이 문제는 상당히 오래걸렸다. 책을 보고 해결하려고 해도 아직 실력이 부족하여 이해하기 힘들어서 검색을 통해 생각보다 간단한 알고리즘으로 작동하는 코드를 보고 이해하며 해결할 수 있었다.