알고리즘 문제해결전략 책 내용중에 질문있습니다 (JLIS관련)

  • sidafra
    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}이 되어야 할텐데..
    이 부분이 잘 이해가 되지 않는데 설명해주시면 감사하겠습니다~!!


    10년 전
1개의 댓글이 있습니다.
  • Kureyo
    Kureyo

    책에서 가장 처음인 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}을 고르게 되겠지요.


    10년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.