(출처) https://algospot.com/judge/problem/read/
메모이제이션을 어떻게 처리해야 할까
해당 문제는 바로 앞의 예제인 증가부분수열 찾기의 확장판 같았다. 기존의 예제는 단 하나의 수열에서 증가부분수열을 찾는 것이었다면, 이번 문제는 2개의 수열을 탐색하며 증가부분수열을 합쳐서 만들어야 한다는 것.
우선 가장 처음 생각한 방법은 단순하게 A, B 두 수열에 기존 증가부분수열을 찾는 로직을 돌려보는 것이었다. 즉 단순하게 앞 예제의 로직을 그대로 가져오지만, 이번에는 2개의 수열을 탐색해야 하므로 약간의 구현을 추가시켜서 A의 수열과 B의 수열을 번갈아가면서 탐색하게 살짝 변형시키는 방법이었다.
따라서 메모이제이션 cache를 200개로 두고 cache[index] 는 index로 부터 만들 수 있는 최대 증가부분 수열의 값으로 해당 문제를 풀어보고자 했다.
하지만 역시 이 방법으로는 오류가 생긴다는 걸 발견하게 됐는데 정답이 아닌 범위를 정답으로 구해내게 되는 허점이 발생했다.
예제와 같은 로직으로 JLIS를 구하게 된다면 cache[S(A)[1]] 는 { 7, 9 } 가 만들어지고 따라서 해당 자리 cache 값은 2로 저장되게 된다. 여기까지는 별다른 문제가 없어 보이지만 S(B)의 3번째 원소 '3'의 차례를 본다면 오류가 발생한다는 걸 알 수 있었다. 기존의 S(A)[1] cache에는 '2' 가 저장되어 있고 따라서 cache[S(B)[2]] 는 {3, 7, 9}의 수열을 만들며 cache에 '3' 을 저장해 버리게 된다. 이때 {3, 7, 9}는 만들어지면 안 되는 잘못된 답이므로 해당 방법으로는 문제를 해결할 수 없다는 걸 알았다.
따라서 방법을 약간 수정하여, A->B 혹은 B->A 처럼 다른 수열로 이동하여 탐색을 진행할 때는 이동하기 전의 정보를 메모이제이션에 추가하여 위와 같은 사례가 발생하지 않도록 해보기로 했다.
따라서 메모이제이션을cache [current] [before] 로 구현하여 다른 수열로 이동하는 탐색이 일어나는 경우엔 before 값에 이동 전 수열의 index를 저장하는 방법을 사용하였다. (current 는 현재 바라보고 있는 원소의 인덱스)
해당 방법으로는 총 cache [200][200] 최대 4만 개의 부분문제가 발생하고, 부분문제 한 개당 최대 200번의 for문을 반복하게 됨으로 최대 800만의 계산 횟수가 발생한다. 시간복잡도는 O(N^3).
코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
using namespace std;
vector<long long> s;
int n, m;
int memo[201][201];
long long INF_M = -9999999999;
int jlis(int current, int before ) {
//메모이제이션
int& ret = memo[current][before];
if (ret != -1) return ret;
ret = 1;
if (current <= n) {
for (int next = current + 1; next <= n; next++) {
if (s[current] < s[next]) {
ret = max(ret, jlis(next, before) + 1);
}
}
for (int next = before + 1; next <= n + m ; next++) {
if (s[current] < s[next]) {
ret = max(ret, jlis(next, current) + 1);
}
}
}
else {
for (int next = current + 1; next <= n + m; next++) {
if (s[current] < s[next]) {
ret = max(ret, jlis(next, before) + 1);
}
}
for (int next = before + 1; next <= n; next++) {
if (s[current] < s[next]) {
ret = max(ret, jlis(next, current) + 1);
}
}
}
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int testcase;
cin >> testcase;
while (testcase--) {
cin >> n >> m;
long long temp;
s.clear();
s.push_back(INF_M);
for (int i = 0; i < n; i++) {
cin >> temp;
s.push_back(temp);
}
for (int i = 0; i < m; i++) {
cin >> temp;
s.push_back(temp);
}
memset(memo, -1, sizeof(memo));
int ret = jlis(0, n);
cout << ret - 1 << "\n";
}
return 0;
}
기억하고 싶은 점
책에 나와있는 방법도 문제를 풀면서 한 번 생각해 봤던 방법인데 이게 과연 제대로 될지 감이 잡히지 않아서 도중에 포기했었다. 답안을 보고 부분문제 내 2개의 다른 방향성을 갖는 재귀를 이용하여 문제를 푸는 방식도 익숙해져야겠다는 걸 느꼈다. 그리고 확실히 내가 알고리즘 문제의 경험이 많이 부족하다는 걸 느꼈다. 어느 정도 경험이 쌓인다면 문제를 풀 때 생각의 가지가 여기저기 뻗어나가는 것을 잘라내고 불확실한 가지는 확실히 쳐낼 수 있을 것 같은데 그런 부분이 아직 부족하다는 걸 느꼈다. 동시에 여러 가지를 고민하는 경험들이 나중에 확실히 도움이 될 것 같다는 것을 느낌.
