11개의 댓글이 있습니다.
-
-
hyunhwan -
랭크를 구하는 문제가 맞습니다.
하지만 매번 프로게이머들의 점수 변동 Query와 랭크를 구하는 Query를 입력으로 받게 됩니다.
만약 매번 프로게이머 랭크에 대한 Query가 들어올 때 sort나 pivoting을 한다고 했을 경우 매번 O(N) 혹은 O(N) time이 소요 되게 되는데(여기서 N은 프로게이머의 수), 이렇게 될 경우 Judge에서 주어진 시간보다 많은 시간이 걸려서 정답이 제한시간 이내에 나오지 않습니다. 왜냐면 Q개의 query가 들어올 경우 Q * (sorting 할 때 걸리는 시간) 이 되버리죠. 만약 N = 10^5 이고 Q = 10^5 일 경우 적어도 query에 소모되는 명령의 수행 수는 10^10 가량이 되어서 1초당 명령 수행 수가 10^8 이라고 하면 100초 가량정도 걸린다 볼 수 있는데, 이 정도의 시간 제한을 줄리는 만무 합니다.
아마도 이 문제는 2가지 query에 대해 O(logN) 의 시간복잡도를 보장 할 수 있는 자료구조를 구현하여 빠른 시간 내에 답을 구하는 문제라고 볼 수 있을 것 같습니다. 이렇게 될 경우 모든 Query에 대해 O( Q * logN ) 의 시간복잡도를 가지게 되고, 시간 제한 내에 모든 경우에 대한 답을 구할 수 있게 될 것 같습니다. 이러한 자료 구조에 대해서 공부를 하고자 하시면, "balanced binary search tree" 나 "binary indexed tree"와 같은 검색어로 구글에서 검색을 해보면 도움이 될 것입니다. 참고로 두 자료구조는 다른 종류의 자료구조 입니다.
끝으로 질문의 목적을 구체적으로 해주시면 답을 하는데 도움이 될것 같습니다 :)
13년 전 link
-
-
-
darkbeam -
제가 아는 랭크 구하는 문제는 자신보다 큰 점수를 가진 경우 +1 을 해주어 실시간으로 구하는 방식이 가장 빠를 것이라고 생각하여 그런 방식으로 구하였습니다. 소트를 하면 너무 큰 값이기 때문에 N의 갯수가 많아지면 문제가 될테니까요. 즉 각 검색 쿼리에 대해서는 1번 사람의 랭크를 알고 싶다면 Rank=1 로 초기화 한뒤, 1~N까지 비교하면서 큰 경우 Rank++; 를 해주는 방식이 동순위 처리에도 유용하다고 생각합니다. O(N) 시간의 복잡도를 갖는 단순한 문제라고 생각했는데 우선 Wrong Answer 의 답을 얻게 되었고요. 제가 무엇을 잘못한지 잘 모르겠어서 질문했습니다. 참고로 제가 작성한 코드를 올리겠습니다.
#include <stdio.h> void main() { int ha,n,qe,nu,s,score[100000],rank,i,j,k; char check; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d",&ha);//선수수 scanf("%d",&qe);//질문수 for(j=0;j<ha;j++) { score[j]=0; } for(j=0;j<qe;j++) { fflush(stdin); scanf("%c",&check); if(check=='R') { scanf("%d",&nu); scanf("%d",&s); score[nu-1] += s; } else { scanf("%d",&nu); rank=1; for(k=0;k<ha;k++) { if(score[k]>score[nu-1]) lank++; } printf("%d\n",rank); } } } }
- 참고로 예외상황은 없을거라고 생각하고 짰는데 혹시나 else 문이 잘못됐나 해서 else if로도 바꾸어 보기도 했습니다.
13년 전 link
-
-
-
Taeyoon_Lee -
큰 메모리를 잡아야 한다면, 그냥 전역 변수로 선언하는 걸 추천합니다. 여러가지 이유가 있는데.. 음.. 일단 한 가지. 해제하는 게 귀찮으니까요..;; (물론 저도 실제 프로그램 개발에서 이러진 않습니다.)
13년 전 link
-
-
-
Taeyoon_Lee -
지역변수로 int score[100000] 배열을 이만큼 잡아도 별 문제가 없을까요..? VS2010은 모르겠는데, VS2008 버전에서는 지역변수로 배열을 10000까지만 잡아도 문제가 발생했던 경험이 있습니다.
13년 전 link
-
-
-
Being -
- 400k니까 스택이 꽤 위험할 겁니다. 대신에 recursion이 없으니까 권장할 수는 없지만 작동은 할 것 같네요. 링커가 기본으로 1M을 잡을 겁니다.
- fflush(stdin)은 C 표준에 정의되지 않은 용법으로써 input buffer를 날리는 Visual C++에서 지원하는 확장 기능입니다. 이 게 비표준적일 뿐더러 file redirection의 경우 완전히 예측 불가능한 행동을 갖게 됩니다. 만약 콘솔에서 interactive 하게 입력을 받는 중간이라면, 입력하는 만큼 버퍼에서 바로바로 처리되기 때문에 상관이 없지만 파일에서 읽어오는 경우 입력 중간에 사람이 '엔터'를 침으로써 버퍼에 넣어 주는 것이 아니기 때문에 내부에서 일정 크기 기준으로 묶어 버퍼를 채우게 됩니다. 즉 입력 파일을 임의로 잘라먹는다는 뜻입니다. 따라서 절대 사용하지 말아야 하며, 아마 Wrong Answer가 나온 이유는 입력을 임의로 자르다가 엉망으로 받았기 때문일 것이라 생각합니다. 자세한 내용은 구글링해보시면 수도 없이 많은 포스트를 찾으실 수 있을 겁니다.
- 마지막으로 리베님께서 지적해주신 대로 쿼리당 O(N)의 알고리즘을 사용하게 되면 전체 쿼리를 사용하는 데에는 O(NQ) 의 시간복잡도를 가지며, 대부분의 경우 이터레이션이 10^10 정도 되면 대강 100초 단위의 시간이 걸릴 것이라 추정됩니다. 즉, O(NQ) 알고리즘은 출제자가 의도한 풀이가 아니며 만약 위에서 말씀드린 문제를 해결하신다고 해도 (이제 프로그램이 정상적으로 작동하는 만큼) 주어진 수행 시간 안에 답을 내어놓지 못해 Time-limit Exceeded 를 받게 되실 것으로 추정합니다.
13년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
darkbeam
제가 문제를 잘못 이해한 건지... 단순히 랭크 구하는 문제 아닌가요?
아니면 뭔가 다른 예외 사항이 있는지 궁금합니다.
13년 전