JLIS 관련 질문입니다.

  • canuyes
    canuyes

    JLIS (합친 증가수열) 관련 질문입니다.
    종만님의 ‘알고리즘 문제 해결 전략 세트’ 책에도 수록되어 있는
    JLIS문제 관련하여 질문 올립니다. (page.238 입니다.)

    문제를 풀었고, 해답도 제출했지만 종만님의 책에 담겨있는 풀이
    (두개의 집합에서 DP를 수행하는 부분이 이해가 되질 않아 질문 올립니다.)

    우선, 질문에 앞서 제가 푼 해답은 다음과 같습니다.

    수열 A,수열 B가 주어질 때,

    A,B에 공통인 숫자가 없다면 두수열 A,B의 합친 증가 수열의 길이는 단순히 두 수열의 LIS를 합친 것 과 같습니다.
    왜냐하면 어차피 중복이 없다면 A에서 구해진 LIS에 B에서 구해진 LIS를 적당한 자리에 끼워 넣기만 하면 되기 때문입니다.

    만약 A,B에 공통인 숫자가 있다면 합친 LIS에서 공통인 숫자들은 A에 나온 순서를 만족하거나 B에 나온 순서를 만족해야 합니다.
    따라서, A에서 공통인 숫자를 제거한 A' 수열에서 LIS를 구하고, B에서 LIS를 구한 뒤 공통인 숫자가 없는 것으로 간주하여 두 LIS를 합칩니다. (1)
    다음 B에서 공통인 숫자를 제거한 B' 수열에서 LIS를 구하고, A에서 LIS를 구한 뒤 공통인 숫자가 없는 것으로 간주하여 두 LIS를 더합니다. (2)

    (1)과 (2)중 큰 것을 답으로 합니다.

    오류가 있으리라고 생각 합니다. 있다면 바로 잡아 주십시오.

    이제 종만님의 책 내용 질문입니다.

    1. jlis(indexA,indexB) = A[indexA]와 B[indexB]에서 시작하는 합친 증가부분 수열의 최대 길이. (p.238) ‘A[indexA]와 B[indexB]에서 시작하는 합친 증가부분 수열’이 무슨 뜻인가요?? 예를 들어 주실 수 있으신가요?
    2. A[indexA]!=B[indexB]라고 가정한다. 이 이야기는 중복을 빼놓고 한다는 이야기인가요? 아니면 생각하지 않아도 답이 나온다는 이야기 인가요?

    위의 2가지가 우선 제가 궁금한 점 들입니다.

    답변해주시면 감사하겠습니다.
    좋은 하루되세요 ^^


    11년 전
6개의 댓글이 있습니다.
  • JongMan
    JongMan

    A[indexA]와 B[indexB]에서 시작한다는 뜻은, 증가부분 수열의 첫 두 수가 각각 A[indexA]와 B[indexB]라는 뜻입니다. 물론 이 둘 중 더 작은 수가 앞에 와야겠지요. A[indexA]=B[indexB]이면 이 두 수가 둘다 수열에 포함될 수 없으니 이런 경우에 대해선 정의하지 않는다는 얘깁니다. 좀 더 명확한가요? ^^;


    11년 전 link
  • canuyes
    canuyes

    우선 진심으로 답변 감사드립니다 ^^

    그런데, 만약 수열의 시작이 A[indexA],BindexB 이라면 다음과 같은 input을 처리 하지 못하지 않나요?

    수열 A : 1 , 2
    수열 B : 3 , 4

    원래 이수열로 만들어지는 JLIS의 길이는 1,2,3,4 로서 4이지만
    캐시에는
    1,3으로 시작 / 1,4로 시작 / 2,3으로 시작 / 2,4로 시작
    다음과 같이 4개의 경우 밖에 담지 못하는 것 아닌가요?

    실제로 우리는 1,2로 시작하는 수열을 찾아야 하는데 말입니다..

    사실 아직 A[indexA]=B[indexB]에 대한것도 이해가 되질 않아서요 ㅠㅠ

    jlis(indexA,indexB) = A[indexA]와 B[indexB]에서 시작하는 합친 증가부분 수열의 최대 길이

    를 이용한 로직만 이해하면 참 이해될듯 한데..ㅠㅠ
    멍청해서 그런지 정말 이해가 잘 되질 않네요 ㅠㅠ


    11년 전 link
  • JongMan
    JongMan

    책의 솔루션의 경우에는 A[-1]과 B[-1]에 각각 음의 무한대가 들어가 있다고 가정합니다. 따라서 해당 경우를 해결할 수 있죠. jlis(indexA, indexB)를 호출했을 경우,

    int a = a[indexA];
int b = b[indexB];
int seq0 = min(a, b);
int seq1 = max(a, b);
// 이 때 [seq0, seq1, ...]로 시작하는 JLIS를 반환한다

    이렇게 쓰면 좀더 이해가 쉬울까요?


    11년 전 link
  • canuyes
    canuyes

    답변해주실 의무도 없으신데 매번 답변해주시네요 ㅠㅠ
    정말 감사합니다 ^^

    음의 무한대를 도입해보니 정말 이해가 되네요!! 감사합니다.

    그런데, 아직 'A[indexA]!=B[indexB]라고 가정한다'를 이해하지 못하겠습니다.ㅠㅠ

    저는 결국 다시 풀면서도,
    A[indexA]와 B[indexB]가 같은 경우와 다른 경우를
    if문으로 분리해서 풀었는데요.

    '같은 경우에 대해 정의 하지 않는다'
    라는 말씀은 만약 같은경우에

    1.CACHE[indexA][indexB]에는 어떤 값이 저장 된다는 말씀이신가요??

    특히 제가 혼란스러운 부분은 p.239 코드 8.13 - 21,24번째 줄입니다.
    ret=max(ret,jlis(nextA,indexB)+1);
    ret=max(ret,jlis(indexA,nextB)+1);
    과 같이 나와있는데요.

    만약 A[indexA]와 B[indexB]가 같다면,
    둘을 중복해서 계수해주면 안되므로,
    2. ret=max(ret,jlis(nextA,indexB)); 가 되어야 하지 않나요?

    염치불구하고 한번더 답변을 기다려봅니다.


    11년 전 link
  • JongMan
    JongMan

    제 설명이 부족해서 그런것이니 당연히 답변 드려야죠. 제때제때 답변 못드리는 것은 죄송합니다 ㅜㅜ

    분리해서 푸셔도 됩니다. 하지만 그럴 필요는 없습니다. 왜냐면 해당 경우가 호출되지 않기 때문입니다.

    편의에 따라, A[-1]은 -infinity + 1, B[-1]은 -infinity 라고 가정해 봅시다. 그러면 jlis()가 호출되는 곳은 jlis() 함수 내부의 재귀호출 뿐입니다. 그런데 이 때 A[nextA]나 B[nextB]는 모든 경우 maxElement보다 크지요. 따라서 jlis()가 호출되었을 때 A[indexA]와 B[indexB]가 같을 가능성은 없습니다.

    좀더 명확한가요?


    11년 전 link
  • canuyes
    canuyes

    답변 감사드립니다^^
    정말로 덕분에 너무 명쾌하게 다 이해했습니다.!
    체증이 확 내려가는 기분이네요 ! ^^
    감사합니다.!


    11년 전 link

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