알고리즘 문제해결 전략 Chapter 08 - LIS(C++)

madpotato1713·2020년 1월 1일
0

알고리즘

목록 보기
15/76

예제: 최대 증가 부분 수열

문제
어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. 단, 10 4 7 은 원래 수열의 순서와 다르므로 10 7 4 9 의 부분 수열이 아니다.

어떤 부분 수열이 순증가할 때 이 부분 수열을 증가 부분 수열 (increasing subsequence) 라고 한다. 주어진 수열의 증가 부분 수열 중 가장 긴 것의 길이를 계산하는 프로그램을 작성하라.

어떤 수열의 각 수가 이전의 수보다 클 때, 이 수열을 순증가 한다고 한다.

입력
입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 가 주어진다. 각 테스트 케이스의 첫 줄에는 수열에 포함된 원소의 수 N (<= 500) 이 주어진다. 그 다음 줄에 수열이 N개의 정수가 주어진다. 각 정수는 1 이상 100,000 이하의 자연수이다.

출력
각 테스트케이스마다 한 줄씩, 주어진 수열의 가장 긴 증가 부분 수열의 길이를 출력한다.

예제 입력

3
4
1 2 3 4
8
5 4 3 2 1 6 7 8 
8
5 6 7 8 1 2 3 4

예제 출력

4
4
4

풀이

예전에 풀었던 최적화 동적계획법 문제이다. 역시 두번째로 푸니, 처음보단 훨씬 수월하게 풀었다. 물론 풀이를 한번 봤던 덕분도 있겠지만, 이런 과정이 배우는 것이라고 생각한다.

이 문제가 보통의 다른 동적계획법 문제와 다른점은, 기저사례가 따로 없다는 점이다. for문에 끝나는 지점에서 res를 return하기 때문이다.

이 문제를 작게 나누면, 해당 위치(index)에서의 최대 증가 부분수열을 구하는 문제가 된다.
이 점에 유의하여 최대 증가 부분 수열을 구하도록 알고리즘을 구성하였다.

전체적인 소스코드는 아래와 같다.

소스 코드

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int N;
int seq[500];
int cache[501];

int lis(int idx) {
	
	int& res = cache[idx + 1];
	if (res != -1) return res;

	res = 1;
	int sum = 0;
	for (int i = idx + 1; i < N; i++) {
		if (idx == -1 || seq[i] > seq[idx]) {
			sum = max(sum, lis(i));
		}
	}
	res += sum;

	return res;
}

int main() {

	int testCase;
	cin >> testCase;

	for (int tc = 0; tc < testCase; tc++) {
		memset(cache, -1, sizeof(cache));
		cin >> N;
		for (int i = 0; i < N; i++) {
			cin >> seq[i];
		}

		cout << lis(-1) - 1 << endl;
	}

	return 0;
}

풀이 후기

알고리즘 문제해결 전략을 보니 이보다 더 빠른 해법이 있다고 한다. 갈 길이 머니, 이 구현은 다음에 찾아보기로 한다. 역시 내가 아는 대부분의 알고리즘은 더 빠르고, 더 어려운 알고리즘들이 즐비한 것 같다.

profile
개발자 성장일기

0개의 댓글