[algospot] 최대 증가 부분 수열 LIS

최대 증가 부분 수열 (ID : LIS)

---

내 풀이 코드 (완전 탐색)

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
#define MAX 500
// LIS 완전 탐색

int cache[MAX][MAX];
int n;

int max(int a, int b) {return a < b ? b : a;}

int lis(const vector<int>& a){
	// 기저 사례 : 돌고 있는 vector 가 비어 있으면
	if(a.empty()) return 0;
	
	/* 내가 작성한 코드
	int ret = -1;
	
	for(int i = 0; i < n; i++){
		vector<int> b;
		for(int j = i + 1; j < n; j++){
			if(seq[i] < seq[j]) b.push_back(seq[j]);
		}
		int bSize = b.size() + 1;
		ret = ret < bSize ? bSize : ret;
	}
	return ret;
	*/
	
	int ret = 0;
	for(int i = 0; i < n; ++i){
		vector<int> b;
		for(int j = i; j < n; ++j)
			if(a[i] < a[j])
				b.push_back(a[j]);
		ret = max(ret , 1 + lis(b));
	}
	return ret;
}

int main(){
	int C;

	cin >> C;
	cin.ignore();
	vector<int> seq(MAX, 0);

	while(C-- > 0){
		cin >> n;
		cin.ignore();
		for(int i = 0; i < n; i++){
			cin >> seq[i];
		}
		cin.ignore();
		int res = lis(seq);
		cout << res << endl;
	}
	
}

문제의 간단한 해법

:

내 풀이 코드 (최적화 문제 동적 계획법)

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
#define MAX 500
// LIS 동적 계획법

int cache[MAX];
int S[MAX];

int n;

int max(int a, int b) {return a < b ? b : a;}

// S[start] 에서 시작하는 증가 부분 수열 중 최대 길이를 반환
int lis2(int start){
	int& ret = cache[start];
	
	// 기저사례 : 계산한적 있다면 바로 반환
	if(ret != -1) return ret;
	
	// "길이" 이기 때문에 항상 S[start] 자신이 있으므로 최소 길이 1
	ret = 1;
	
	for(int next = start + 1; next < n; ++next)
		if(S[start] < S[next])
			ret = max(ret, lis2(next) + 1);
	return ret;
	
}

int main(){
	int C;

	cin >> C;
	cin.ignore();

	while(C-- > 0){
		cin >> n;
		cin.ignore();
		for(int i = 0; i < n; i++){
			cin >> S[i];
		}
		cin.ignore();
        // cache 를 -1로 초기화 해준다
		memset(cache, -1, sizeof(cache));
		int res = 0;
		for(int i = 0; i < n; i++)
			res = max(res, lis2(i));
		cout << res << endl;
	}
}

문제의 간단한 해법

: S[start] 에서 시작하는 부분 증가 수열 중 최대의 길이 를 메모이제이션 한 것을 알 수 있다.

하지만, 실수 했던 것은 역시나 초기화 부분이었다. std::fill 함수를 사용하여 cache 배열을 -1로 제대로 초기화해주었더니 동작하였다.

전역 변수 선언시, int cache[MAX] = {-1}; 이라고 한다면, 첫번 째 원소만 -1로 초기화 될 뿐이고 나머지 원소는 0으로 초기화된다는 것을 자꾸 실수하였다.

std::fill 이나 std::fill_n 을 활용하여 적절히 초기화 하자. 하지만, 이것은 동적 배열에는 적용되지 않으므로 동적 배열을 활용할 시에는 다른 방법을 사용해야 한다는 점도 유념해두자.