개발개발자
JLIS 본문
1. 문제 해설
- 기존에 사용했던 LIS 재귀 DP 알고리즘을 변형하여 사용한다.
- JLIS(idxA, idxB) = A[idxA]와 B[idxB]에서 시작하는 합친 증가 부분수열의 최대 길이
2. 이해해야 할 핵심 사항
1) A[idxA]와 B[idxB]를 무조건 포함하는 LIS
: LIS를 구하는데 있어서 두 배열의 임의의 인자값을 포함하거나 포함하지 않을 수 있다. 하지만, LIS를 구할 때처럼 인덱스의 선택/미선택을 재귀함수 내에서 고민하지 않는다. 즉 현재 JLIS 함수 내에 정해진 A배열 인덱스 값과(idxA) B배열의 인덱스 값(idxB)은 무조건 포함하는 LIS를 구하는 방식이다.
2) 시작 인덱스를 A[-1], B[-1]로 접근한다.
: A[-1], B[-1]에 각각 음의 무한대가 들어있다고 가정한다. jlis(idxA, idxB)를 호출했을 경우 아래와 같다.
int a = A[idxA];
int b = B[idxB];
int seq0 = min(a,b);
int seq1 = max(a,b);
→ 이 때, [seq0, seq1, …] 로 시작하는 JLIS를 반환환다. |
만약 main 함수에서 JLIS로 처음 시작하는데 있어서 음수 인자를 사용하지 않으면
A배열과 B배열의 처음 선택되는 인자 2개 값을 모두 선정해서 call 해줘야 한다. 즉 100*100번의 call이 발생한다.
main()
…
int ans = 0;
for(int i=0; i<a.len; i++) {
for(int j=0; j<b.len; j++ {
ans = Math.max(ans, JLIS(i, j));
}
}
System.out.println(ans);
} |
이를 main에서 이러한 경우를 없애고, 초기 호출 경우를 재귀함수 내에 녹이는 개념이라고 생각하면 좋을 것 같다.
main() {
…
int ans = 0;
ans = JLIS(-1, -1);
System.out.println(ans);
} |
즉, JLIS(-1, -1)을 호출하면 항상 -∞부터 시작하기 때문에 모든 시작 위치를 자동으로 시도하게 된다.
* 유의사항
① start = -1인 경우, cache[][]에 접근할 때 cache[start][start] 대신 cache[start+1][start+1]로 쓰는 것을 유의해야한다. 따라서, cache 크기도 1 크게 선언해야한다.
② 결과값에서 -2를 해줘야한다.
A[-1], B[-1]은 가상으로 추가한 입력 값이기 때문에, 최종 결과값에 -1,-1 두 개의 값이 반영되기 때문이다.
따라서, 최종 반환 값에서 빼 줘야한다.
※ 정답 : System.out.println(JLIS(-1, -1) -2);
3) A[idxA] != B[idxB] 인 경우는 호출되지 않는다.
: JLIS 함수 내 선택된 두 인자의 maxElement보다 큰 값을 next idx로 선택하여 재귀호출을 진행하기 때문이다.
※ 참고 : 종만북, https://algospot.com/forum/read/1851/
'알고리즘(Algorithm) > ALGOSPOT' 카테고리의 다른 글
TRIPATHCNT (0) | 2019.02.04 |
---|---|
PI (0) | 2019.02.03 |
WILDCARD (0) | 2019.01.06 |