7-2. 동적 계획법 예제 문제 - #1. LIS(최장 증가 부분 수열)

1. LIS(최장 증가 부분 수열 ; Longest Increasing Subsequence)

부분 수열은 수열의 일부 숫자를 지우고 남은 수열이다.

(단, 수열의 순서가 변경되면 안됨)

 

순 증가 부분 수열은 수열의 배열이 증가하는 형태인 수열이다.

(ex. 1, 3, 5는 순 증가 부분 수열, 1, 3, 7, 4는 순 증가 부분 수열이 아니다)

 

LIS는 제일 긴 순 증가 부분 수열을 뜻한다.

즉 수열에서 가장 긴 순 증가 부분 수열의 길이를 찾는 것이 목표이다.

 

2. 코드 분석

#include <iostream>
#include <windows.h>
#include <vector>
using namespace std;

int cache[100];

vector<int> seq = { 1,9,2,5,7 };

// 문제가 요구하는 정답을 반환한다

int LIS(int pos) // pos번 인덱스가 포함이 된 부분 수열을 만든다
{
	// 예외 사항 확인

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

	// Seq : 1 9 2 5 7
	// 최소한 seq[pos]는 1부터 시작해야 함
	ret = 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()
{
	// 길이일 리 없는 값으로 초기화하기
	std::memset(cache, -1, sizeof(cache));

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

(1) 캐시 확인하기

cache는 요소가 100개인 배열로 이루어져있다. 이 캐시는 main 함수에서 -1로 초기화 된다.

ret는 cache 배열을 참조하게 되어있어,  ret로 값을 구하면 cache에 하나씩 값을 저장할 수 있다.

 

(2) 정답 구하기

next 인덱스를 사용하여 처음 0번째 수 부터 seq 배열의 끝까지 반복한다.

순 증가 부분 수열을 충족하기 위해 지금(pos) 값이 다음(next)보다 작아야 한다.

조건을 만족하면 ret는 LIS로 구해진 길이와, 다음 인덱스를 재귀적으로 호출한 길이와 비교하여 더 큰 값을 취한다.

 

(3) 재귀적 호출

ex) seq = {1, 9, 2, 5, 7}

부분 배열은 최소한 하나의 요소가 존재하여야 하므로 ret의 기본값은 1이다.

순 증가 부분 수열의 조건을 만족하는 경우, 길이를 1 증가시킴과 동시에 그 다음 인덱스의 값과 방금 구한 값을 이용해

다시 순 증가 부분 수열의 조건을 만족하는지 확인한다.

그리고 순 증가 부분 수열의 조건을 만족하지 못하면 ret을 반환한다.

 

(1, 9) -> 만족 -> (1, 9, 2) -> 불반족, ret = 2 반환

(9, 2), (9, 3), (9, 7) -> 불만족, ret = 1 반환

(2, 5) -> 만족 -> (2, 5, 7) -> 만족, ret = 3 반환

(5, 7) -> 만족 -> ret = 2 반환

(1, 2) -> 만족 -> (1, 2, 5) -> 만족 -> (1, 2, 5, 7) -> 만족 -> ret = 4 반환

(이하 생략)

 

max 함수를 사용하여 가장 큰 값을 추출하기 때문에 결과값은 4가 반환된다.