순서가 섞여있는 수열을 최소로 뒤집어서 정렬하기..

  • hyida
    hyida






    순서가 섞여있는 수열이 있는데 이수열들을 1 2 3 4 5 이런식으로
    최소횟수로 뒤집어서 정렬하는 문제..입니다.
    1) 구간이 정해져 있지않고 뒤집는문제
    2) 문제에서 구간이 주어지고 뒤집는 문제.
    어떤식으로 해결할수있을까요? 고수님들 좀 도와주세요...;
    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]


    14년 전
9개의 댓글이 있습니다.
  • helloneo
    helloneo

    뒤집는다는게 무슨 의미인지 잘 모르겠는데..최소 # of swap 을 구한다고하면 cycle을 찾고 각 cycle의 size를 더하는게 방법이 가장 쉽겠네요..
    자세한 설명은 아래 링크에..
    http://online-judge.uva.es/board/viewtopic.php?t=4598


    14년 전 link
  • Stun
    Stun

    좋은글 링크 감사드립니다 +_+ ㅎ 그런데 여기서 Cycle의 의미가 조금 명확하게 해석이 안되는데 조금 설명해주실수 있나요?
    예를들어 5 4 2 3 1 의 경우 어떻게 Cycle을 찾아야 하는지 잘 모르겠습니다;;


    14년 전 link
  • nocut98
    nocut98

    swap을 최소로 구할때, n번 뒤집는 것의 집합을 차례대로 전부 구해나가다가 어느 순간 정렬된 수열이 나오면 그때의 n이 최소가 되겠죠...백트래킹 짱 ㅋㅋㅋ n이 많이 작아야 겠죠? ㅎㅎㅎ


    14년 전 link
  • helloneo
    helloneo

    1 2 3 4 5
    5 4 2 3 1
    위 아래로 지그재그로 가면서 보면 되요
    1 -> 5 -> 1 (첫번째 cycle)
    2 -> 4 -> 3 -> 2 (두번째 cycle)


    14년 전 link
  • hyida
    hyida

    ex) 2 5 4 3 1 같은 배열에서 [2,5]를 뒤집으면 2 1 3 4 5 이런식으로.. 된다는거에요..^^


    14년 전 link
  • helloneo
    helloneo

    아.. SRM 397 의 SortingGame 문제가 비슷하네요.. ㅋㅋㅋ
    http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm397


    14년 전 link
  • Being
    Being

    [k, n] 꼴만 뒤집을 수 있다면 유명한 pancake sorting problem이 되겠네요 'ㅅ'


    14년 전 link
  • hyida
    hyida

    11 감사합니다. 그런데 [k,n] 꼴로만 뒤집을 수 있는 문제들이네요..
    모든 구간을 뒤집을 수 있다면 어떤식으로 해결할 수 있을까요??


    14년 전 link
  • helloneo
    helloneo

    똑같이 모든 구간에 대해서 BFS로 탐색하면 되지 않을까요..?더 효과적인 방법은 저도 잘 모르겠네요..


    14년 전 link

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