EDITORWARS 질문

  • Namnamseo
    Namnamseo

    (핸드폰으로 작성중이라 어색한 부분이 있을 지도 몰라요)
    안녕하세요, 올해 여름동안 국제 정보올림피아드 교육생 여름학교에 갔다왔던 학생입니다...만 사실 실력이 그렇게 뛰어난 편은 아니고, 배운걸 제대로 익히지 못했었어요ㅠㅠ 좀 더 공부하고 갔더라면 더 좋았을텐데...

    잡담은 그만하고, 여름학교때 나온 문제랑 같은 내용의 문제가 보여서 풀어보려 했으나, 거기서도 못푼 문제라 여기서도 못풀고 있습니다 (...)
    룸메이트 형이 Union & Find를 사용하면 된다고 했었는데, 그때 강의에서 처음 들어본 개념을 응용하는게 생각보다 어렵더라구요.
    제가 가장 고민하고 있는 문제는,
    ACK 쿼리의 경우 union 으로 두 집합을 묶으면 되는데,
    DIS의 경우 바로 처리할 수 없다는 문제점이 생겨요.
    그렇다고 0번, (n+1)번같은 super parent를 잡게 되면 훨씬 복잡해질테고 게다가 Union & Find가 적용될 부분이 없어 보여요.
    그렇다면 DIS 쿼리를 모두 저장해서, 모든 쿼리마다 두 사람의 관계가 적절한지 확인하는 방법은 심각하게 복잡하구요.
    Union & Find 문제는 처음이라 고민하다가 안되겠길래 글을 올리고 있어요.

    힌트라던가, 'ㅁㅁ에서 조금만 더 생각해보세요~' 라던가,
    간단한 조언이라도 해주시면 감사하겠습니다.

    아, 참고로 book.algospot.com 의 책은 아직 안읽어봤어요. 지금은 읽어볼 여유도 별로 없네요ㅋ


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

    Union Find를 그대로 사용해서는 풀기 어렵고, 이 문제를 푸는 데 유용한 추가 정보를 저장해서 새로운 버전을 만들어야 할겁니다.


    11년 전 link
  • Namnamseo
    Namnamseo

    혹시 그런 자료구조를 일컫는 말이 따로 있나요?


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