[C++ 자/알 Note] LIS (Longest Increasing Subsequence) 문제

LIS 개념

- Sequence(수열)

수를 나열한 것을 의미한다

ex. 1 9 2 5 7

 

- Subsequence(부분 수열)

기존 수열의 순서는 유지한 채로 일부 숫자를 지우고 남은 수열을 의미한다
ex. 기존 수열이 1 9 2 5 7이라는 가정하에

1 2 5, 1 9 5 7,...

- Increasing Subsequence(순 증가 부분 수열)

증가하는 규칙이 지켜진 부분 수열을 의미한다

ex. 1 2 5 (O), 1 9 7 (X)

- LIS(Longest Increasing Subsequence, 최장 증가 부분 수열)

제일 긴 Increasing Subsequence을 의미한다
ex. 기존 수열이 1 9 2 5 7이라는 가정하에

1 2 5 7 -> length가 4로 가장 길다

 

LIS 구현 주의사항 with 동적계획법

- 동적계획법의 코드 형식

기본적으로 동적계획법을 사용하는 경우

코드를 작성할 때는 "기저사항 -> 캐시확인 -> 연산" 형식으로 진행하는 것이 좋다

 

- LIS(int pos)

LIS의 시작위치(index)를 지정해서

먼저 해당 인덱스는 선택을 하고 경우의 수를 찾도록 구현한다

그러다 보니 최종적으로 모든 원소들을 시작위치로 지정해서

한 번씩 다 실행해줘야 한다

 

- 전반적인 논리

기존 수열이 3 1 9 5 7이라는 가정하에

3을 시작위치로 선택해서 LIS(0)을 호출했다면,

다음으로는 for문을 돌면서 자신보다 큰 수들만

LIS(N)를 호출해 주면 된다

ex. 3 -> 9, 5, 7 재귀적으로 호출

3 -> 9 -> X

3 -> 5 -> 7

3 -> 7 -> X

 

- LIS() 재귀

LIS함수가 재귀적으로 호출될 때마다

LIS의 길이가 1씩 증가되기 때문에

"1 + LIS(next)"로 작성을 해서 증가부분수열의 길이를 반환하도록 한다

 

- max(a, b)

a와 b 중에 큰 값을 반환한다

해당 함수를 이용해서 쉽게 최대치를 저장해 반환할 수 있다

 

LIS 구현 with 동적계획법

int cache[100];
vector<int> seq;

int LIS(int pos)
{
	// 기저사항
    // 딱히 없기에 미작성 

	// 캐시확인
	int& ret = cache[pos];
	if (ret != -1)
		return ret;

	// 연산
    
	ret = 1;// 최소 seq[pos]은 있으니 1부터 시작

	// 구하기
	for (int next = pos + 1; next < seq.size(); next++)
		if (seq[pos] < seq[next])
			ret = max(ret, 1 + LIS(next));

	return ret;
}

int main()
{
	::memset(cache, -1, sizeof(cache));
	seq = vector<int>{ 10, 1, 9, 2, 5, 7 };

	int ret = 0;
	for (int pos = 0; pos < seq.size(); pos++)
		ret = max(ret, LIS(pos));

}