책에서 가장 처음인 A[-1],B[-1]에는 -inf 값이 들어있다고 가정하기 때문에 성립됩니다.
예제는 전부 양수기 때문에 그냥 -1을 가정하면
A={-1,1,2,3}
B={-1,4,5,6}
맨 처음 -1 vs -1대결로 각각 {-1}{-1}상태가 되고
그리고 -1보다 큰 A의 1값이 들어가게 됩니다. {-1,1}{-1}
그리고 1보다 큰 A의 2값이 들어갑니다 {-1,1,2}{-1}
...
그렇게 되서 각각에서 {-1,1,2,3}{-1,4,5,6}을 고르게 되겠지요.
sidafra
238p 합친 LIS에서 이해가 안되는 부분이 있는데요..
중간 좀 아랫부분에
"A[index]와 B[index]중 작은 쪽이 앞에 온다고 합시다. 그러면 이 증가 부분 수열의 다음 숫자는 A[indexA + 1]이후 혹은 B[indexB + 1] 이후의 수열중 max(A[indexA], B[indexB])보다 큰 수중 하나가 됩니다."
라고 나와있습니다.
그런데 A를 {1,2,3} B를 {4,5,6}이라고 하면
A[0]과 B[0]을 비교해서 {1,4}가 되고 그 다음 수가
A[0]과 B[0]의 max값인 4보다 큰 수인 5가 된다는 얘기인가요?
위의 예로는 {1,2,3,4,5,6}이 되어야 할텐데..
이 부분이 잘 이해가 되지 않는데 설명해주시면 감사하겠습니다~!!
9년 전