gkdl996   5년 전

O(n)이라고 생각하였는데 어디서 어떻게 틀리는지도 모르겠습니다.

djm03178   5년 전

  1. unordered_set은 중복을 허용하지 않습니다. 그래서 중복된 원소가 여러 번 들어와도 원소는 하나로 남아있습니다. 그러면 index가 set의 크기를 한참 넘을 수 있는데 iterator를 이 횟수를 넘어서 증가시키는 건 당연히 안 됩니다.
  2. unordered_set은 말 그대로 정렬이 안 된 셋입니다. 그래서 iterator를 돌렸을 때 원소가 나오는 순서는 정렬된 순서라는 보장도 없고, 원소를 넣은 순서라는 보장도 없습니다. 전혀 예상하지 못한 순서로 원소가 나올 수 있습니다.
  3. 단순히 max가 등장하기까지 max 이하의 수의 등장 횟수를 센다고 해서 되는 것도 아닙니다. 1 3 2 4 이렇게 있으면 모든 수는 4 이하이지만 3 -> 2는 증가하는 상태가 아니므로 1 3 4 또는 1 2 4만 최장 증가 수열이 될 수 있습니다.
  4. 최장 증가 수열 (LIS) 알고리즘은 매우 매우 유명한 알고리즘으로, 푸는 방법이 정형화되어 있고 구글에 검색해보면 수만 가지 잘 정리된 설명 글들이 있습니다. 찾아서 공부해보세요.

gkdl996   5년 전

좋은 답변 감사드립니다.

 LIS 알고리즘 공부후에 꼭 다시 풀어보겠습니다.!! 

댓글을 작성하려면 로그인해야 합니다.