KLIS 문제에서 sort 없이 O(n^2)에 해결하는 방법이 뭔가요?

  • espuer
    espuer

    종만북에서 KLIS 문제에서 정렬 없이 O(n^2) 시간안에 KLIS 문제를 해결할 수 있다고 했는데 그 방법이 뭘까요?
    제가 생각해본 더 빠른 방법은 각각의 index에서 increasing 관계를 가지는 다음 index로 넘어갈 때 특정한 저장소에 미리 그 인덱스들을 사전 순으로 저장하는 것인데요, (즉 LIS를 컴퓨팅 하는 시간에 다음 인덱스들도 사전순으로 같이 저장.) 그래도 시간 복잡도는 결국 사전 순으로 저장하기위해 priority queue를 이용하거나 다 넣고 나서 정렬을 해야되기 때문에 O(n^2 logn)일것 같은데요..
    아니면 혹시 이 방법이 amortized cost때문에 O(n^2)가 되는건가요? 사실 제가 위에 말한 방법의 시간 복잡도 계산이 어렵네요.


    8년 전
1개의 댓글이 있습니다.
  • espuer
    espuer

    자문 자답입니다.


    i를 선택한 뒤 다음 KLIS 후보들은 항상 decreasing order기 때문에 sort 할 필요가 없군요. 그러고보니 미리 저장하지 않고 KLIS를 구한 다음에 다시 다음 후보 index 대해서 조사할 때에도 다 구하고 뒤에서부터 조사하면 decreasing order라서 sort할 필요가 없겠군요.


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