인터넷 예선 I번 문제

  • darkbeam
    darkbeam

    제가 문제를 잘못 이해한 건지... 단순히 랭크 구하는 문제 아닌가요?

    아니면 뭔가 다른 예외 사항이 있는지 궁금합니다.


    11년 전
11개의 댓글이 있습니다.
  • astein
    astein

    단순히 랭크 구하는 문제가 맞긴 합니다만. N <= 10만, Query <= 20만 이니까 N * Q로 구하면 무조건 Time Limit Exceeded 입니다.


    11년 전 link
  • hyunhwan
    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"와 같은 검색어로 구글에서 검색을 해보면 도움이 될 것입니다. 참고로 두 자료구조는 다른 종류의 자료구조 입니다.

    끝으로 질문의 목적을 구체적으로 해주시면 답을 하는데 도움이 될것 같습니다 :)


    11년 전 link
  • Being
    Being

    OS가 허용하는 범위 하라면 상관없고 별도의 제한을 두지는 않습니다만, 일반적으로 큰 메모리를 사용하는 문제는 잘 내지도 않거니와 그로 인한 퍼포먼스 감소도 염두에 두셔야 할 것 같습니다.


    11년 전 link
  • darkbeam
    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로도 바꾸어 보기도 했습니다.

    11년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    큰 메모리를 잡아야 한다면, 그냥 전역 변수로 선언하는 걸 추천합니다. 여러가지 이유가 있는데.. 음.. 일단 한 가지. 해제하는 게 귀찮으니까요..;; (물론 저도 실제 프로그램 개발에서 이러진 않습니다.)


    11년 전 link
  • 김우현
    김우현

    일단은 39번 째 라인의 fflush(stdin); 부분이 문제가 될 것 같습니다. ㅠ


    11년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    지역변수로 int score[100000] 배열을 이만큼 잡아도 별 문제가 없을까요..? VS2010은 모르겠는데, VS2008 버전에서는 지역변수로 배열을 10000까지만 잡아도 문제가 발생했던 경험이 있습니다.


    11년 전 link
  • astein
    astein
    1. 한 번의 랭크를 구하는데 O(N)이라는 시간복잡도를 가지게 되면, Query 수만큼 반복하게 되기 때문에 O(QN)이 됩니다.
    2. fflush(stdin); scanf("%c",&check); 이 부분은 scanf(" %c", &check); 정도로 바꾸어주면 편하게 처리할 수 있습니다. scanf에서 앞에 공백 하나 넣어주면 space는 무시하고 읽어옵니다.

    11년 전 link
  • Being
    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 를 받게 되실 것으로 추정합니다.

    11년 전 link
  • darkbeam
    darkbeam

    우선 PC^2 의 이해도가 떨어져서 그렇군요. 제가 풀었던 다른 모든 문제도 fflush 및 메모리 에러가 났을 가능성이 높겠군요. 이제 궁금증이 해결 되었습니다. 감사합니다. 저는 로컬에서 돌아갈 수 있다면 다 돌아 갈 것이라고 생각 하고 푼게 문제였던거 같습니다.
    그 외에 추가로 궁금한 사항은 문제를 보면 메모리에 대한 언급이 없는 경우가 대부분이었는데 그냥 malloc 따위로 큰 메모리를 잡아도 상관이 없었는지가 좀 궁금합니다.


    11년 전 link
  • VOCList
    VOCList

    대부분의 온라인 저지를 보시면 문제마다 주어지는 Memory Limit가 표기되어 있습니다. malloc과 같이 스택영역이 터질 일이 없는 함수라면 위 메모리 제한 한도 내에서는 자유롭게 선언하실 수 있습니다. 그러나 대규모의 메모리 할당 및 해제는 일반적으로 프로그램에 큰 부하를 주는 것이 사실이고, 한번에 몇백메가씩 할당하는 경우에는 종종 할당 과정에서 TLE로 이어지기도 합니다.


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