개발개발자

JLIS 본문

알고리즘(Algorithm)/ALGOSPOT

JLIS

맛두부 2018. 8. 1. 15:57

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
Comments