<종만북> 08. 동적계획법_합친 LIS (JLIS, Joined Longest Increasing Subsequence
앞에서 LIS 문제는 많이 다뤘다. 하지만 이번에 다룰 내용은 더 심화된 JLIS 문제이다. 근데 책에서는 난이도가 하 라고 되어있다..하하..
예를 들어 '1 3 4 7 9'은 '1 9 4'와 '3 4 7'의 JLIS이다. 문제는 정수 수열 A, B가 주어질 때 JLIS의 길이를 계산하는 프로그램이다.
먼저 책에서 LIS 문제를 해결하는 동적 계획법 알고리즘을 알아볼 필요가 있다.
코드8.11
int n; int cache[100], S[100]; int list(int start) { int& ret = cache[start]; if (ret != -1) return ret; ret = 1; for (int next = start + 1; next < n; ++next) if (S[start] < S[next]) ret = max(ret, list(next) + 1); return ret; }
-
list()는 S(start)에서 시작하는 증가 부분 수열 중 최대 길이를 반환하는 함수이다.
-
ret가 cache[a][b]에 대한 참조형(reference)이다. ret 의 값을 바꾸면 cache[a][b]의 값도 변하기 때문에 매번 귀찮게 cache[a][b]라고 쓰지 않고, 실수를 줄여주기 위해 사용한다.
-
ret=1 로 설정하는 이유는 항상 S[start]는 있기 때문에 길이를 최하 1로 설정한다.
이 코드에서는 list()를 호출할 때 항상 증가 부분 수열의 시작 위치를 지정해 줘야 하므로 처음에 호출할 때 각 위치를 순회하며 최댓값을 찾는 코드를 작성해줘야 한다.
int maxLen = 0; for (int begin = 0; begin < n; ++begin) maxLen = max(maxLen, list(begin));
그래서 책에서는 S[-1]을 아주 작은 수, 즉 마이너스 무한대로 설정해놓고 list(-1)를 호출하면 모든 시작 위치를 자동으로 시도하게 되는 코드를 만들었다.
코드8.12
int n; int cache[101], S[100]; int list(int start) { int& ret = cache[start + 1]; if (ret != -1) return ret; ret = 1; for (int next = start + 1; next < n; ++next) if (start == -1 || S[start] < S[next]) ret = max(ret, list(next) + 1); return ret; }
- start=-1로 주어질 수도 있기 때문에 cache[]에 접근할 때 cache[start] 대신 cache[start+1]을 쓴다. 따라서 cache[]의 크기도 1 커졌다.
- 결과 값은 list(-1)-1 을 해야하다. S[-1]은 가상으로 추가한 입력 값이기 때문에 최종 반환 값에서는 1을 빼준다.
그럼 이제 jlis를 푸는 알고리즘을 생각해보자.
- jlis(index A, index B)=A[indexA], B[indexB]에서 시작하는 합친 증가 부분 수열의 최대 길이이다.
- A[indexA]와 B[indexB]중 작은 값이 앞에 온다.
- 이 증가 부분 수열의 다음 숫자는 A[index+1] 이후 혹은 B[index+1] 이후의 수열 중 max(A[indexA], B[indexB])보다 큰 수 중 하나가 된다.
- A[nextA]를 다음 숫자로 선택했을 경우에 합친 증가 부분 수열의 최대 길이는 1+jlis(nextA, indexB)가 된다.
와 같은 점화식으로 나타낼 수 있다.
const long long NEGINF = numeric_limits<long long>::min(); int n, m, A[100], B[100]; int cache[101][101]; int jlis(int indexA, int indexB) { int& ret = cache[indexA + 1][indexB + 1]; if (ret != -1) return ret; ret = 2; long long a = (indexA == -1 ? NEGINF : A[indexA]); long long b = (indexB == -1 ? NEGINF : B[indexB]); long long maxElement = max(a, b); for (int nextA = indexA + 1; nextA < n; ++nextA) if (maxElement < A[nextA]) ret = max(ret, jlis(nextA, indexB) + 1); for (int nextB = indexB + 1; nextB < n; ++nextB) if (maxElement < B[nextB]) ret = max(ret, jlis(indexA, nextB) + 1); return ret; } int main() { cin >> n >> m; memset(cache, -1, sizeof(cache)); for (int i = 0; i < n; i++) cin >> A[i]; for (int j= 0; j < m; j++) cin >> B[j]; cout << jlis(-1, -1) - 2 << endl; return 0; }
- std::numeric_limits 클래스는 자료형의 max, min값을 알아내기 위해 선언한 것인데, indexA, indexB==-1 일 경우 마이너스 무한대 값으로 설정하기 위해서다.
- A[indexA], B[indexB] 가 이미 존재하므로 ret=2로 항상 초기화 한다.
- A[-1], B[-1]은 가상으로 추가한 입력 값이기 때문에 최종 반환값에서 -2를 해줘야 한다.
- 참고로 memset()으로 int 배열을 초기화 할 때는 -1, 0으로만 '운좋게' 가능하다. 1byte 단위로 값을 초기화 하기 때문에 char type 에서 초기화 할 때 사용된다.
Author And Source
이 문제에 관하여(<종만북> 08. 동적계획법_합친 LIS (JLIS, Joined Longest Increasing Subsequence), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmy/종만북-08.-동적계획법합친-LIS-JLIS-Joined-Longest-Increasing-Subsequence저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)