[알고리즘] 동적 계획법(DP) - LIS(Longest Increasing Subsequence)

부분 수열은 일부(0개 이상) 숫자를 지우고 남은 수열이다. 즉 순서를 유지해야 한다.

순 증가 부분 수열(LIS)은 부분 수열 중 오름 차순의 형태를 띄는 수열이다. LIS의 최대 길이를 구해보자.

 

int LIS(int pos)
{
    //기저 사항
	if(seq.size()-1==pos)
    	return 1;
    //캐시 확인
	if(cache[pos] != -1)
    	return cache[pos];
 ...

LIS는 int를 반환한다. 이것은 순 증가 부분 수열의 길이다.

매개변수로 int pos를 받는데 LIS의 첫번째 원소의 위치다.

seq는 대상이 되는 수열이고 pos가 seq의 마지막 원소일 경우 LIS의 길이는 1이기 때문에 이것을 기저 사항으로 둔다.

그리고 cache에 값이 저장되어 있으면 그 값을 반환한다.

 

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

이제 LIS의 최대 길이를 구할건데 최소 길이는 1이므로 cache[pos]는 1부터 시작한다.

그리고 pos 다음 원소들을 탐색하며 seq[pos]보다 seq[next]가 크다면 (LIS라면) 1  + LIS(next) 가 cache[pos]가 된다.

LIS(0)의 경우 LIS가 seq의 첫번째 원소부터 시작한다 가정하고 그 다음 원소를 몇번째 원소로 하느냐에 따라

LIS 길이 값이 달라질 것이고 그 중 가장 큰 값을 cache[0]에 저장한다.

 

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

LIS(pos)는 LIS의 첫번째 원소가 pos일 때 한정해서 최대 길이를 구해주므로

pos가 seq의 첫원소일 때부터 마지막 원소일 때까지 루프를 돌리면 seq 수열의 LIS 최대 길이를 구할 수 있다.