예제: 최대 증가 부분 수열
문제
어떤 정수 수열에서 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;
}풀이 후기
알고리즘 문제해결 전략을 보니 이보다 더 빠른 해법이 있다고 한다. 갈 길이 머니, 이 구현은 다음에 찾아보기로 한다. 역시 내가 아는 대부분의 알고리즘은 더 빠르고, 더 어려운 알고리즘들이 즐비한 것 같다.
