2007년 ACM ICPC 서울 Puzzle문제 도와주세요 !! ㅜㅜ

  • Repil
    Repil

    문제를 보고 고민 많이 해봤는데, 도저히 감이 안잡혀서 Kureyo 님이 작성하신 에디토리얼을 봤습니다.
    (http://algospot.com/discussion/183/2007%EB%85%84-%EC%84%9C%EC%9A%B8-%EC%98%A8%EC%82%AC%EC%9D%B4%ED%8A%B8-%EB%B3%B8%EC%84%A0-h%EB%B2%88-puzzle/p1)

    헉.. 신기하다. 이러면서 읽고 있었는데 중간 부분부터 전혀 이해가 가지 않습니다.
    ("ACG에 A를 붙이든 B를 붙이든 C를 붙이든 전부 해당하는 prefix가 없기 때문에 CGA GA A를 체크해보고 CGB GB B를 체크해보고 CGC GC C를 체크해봐야합니다. 그런데 방법을 바꿔서 ~ " 정확히는 이 부분부터 전혀 이해가 안갑니다.)

    그래서 코드를 보고 이해할려고 했는데, 코드를 쳐다봐도 왜 이렇게 짜놨는지 전혀 이해가 안가구요.
    음.. 어떻게 쉽게 풀이 방법을 이해 시켜 주실 분 안계신가요? ㅜㅜ


    13년 전
6개의 댓글이 있습니다.
  • wookayin
    wookayin

    먼저 드리고싶은 말씀은, Puzzle 문제는 DFS나 BFS를 처음 배운 뒤 응용으로 풀만한 수준의 문제는 아닌것 같아요..

    일단 좀 더 이해하기 쉬운 접근방법이 있다면, 결국에 오토마타 그래프를 그리는 게 목표인데..

    Aho-corasick 알고리즘에서 trie를 구성해놓고 failure function 를 구하면 (이건 Aho-corasick 설명을 참고.. KMP를 완벽하게 이해하셨으면 이해할 수 있을거에요) state-transition graph를 얻죠. (이것도 구체적인 detail을 생략하자니 이정도밖에 쓸 수가 없어서 이해하기 쉬운 설명은 아닌것 같지만..ㅠㅠ)


    13년 전 link
  • Repil
    Repil

    wookayin 님//
    아, 그렇군요. 어쩐지 너~~무 어렵다고 생각했습니다.
    나름대로 프로그래밍에 자신감이 있었는데 좌절했었거든요.

    쉽게 설명해주신다고 해주셨는데 무슨 말인지 모르겠습니다.
    좀 더 공부해야겠습니다. 답변 감사합니다!!

    덧)
    Aho-corasick 알고리즘.. KMP 알고리즘.. 다 처음 들어 보는 것들이네요.
    state-transition graph는 전공 시간에 들어본 기억이 있구요.


    13년 전 link
  • VOCList
    VOCList

    적용해볼 겸 퍼즐 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
    ㅠㅠㅠㅠ 숙제가 파워잔인


    13년 전 link
  • 꿀호떡
    꿀호떡

    오잉.. 혹시 저번에 피지알에서 뵌 그 분이신가요 ㄷㄷㄷ


    13년 전 link
  • Repil
    Repil

    VOCList 님 //
    진심 미쳐 버릴 것 같습니다 ㅜㅜ 완전 부담ㅋㅋㅋㅋ

    꿀호떡 님//
    네ㅋㅋㅋㅋ 맞습니다 ㅋㅋㅋ 아 매번 숙제 때문에 돌아 버릴 것 같아요 ㅋㅋㅋ


    13년 전 link
  • Kureyo
    Kureyo

    엄... 굉장히 어려운 숙제를 받으셨군요-_-;;


    13년 전 link

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