problem set archive

Contents

Valladolid 라는 대학이 있다. 어디붙은 대학인지는 모르겠다... 허나 이 대학에서 만든 사이트에는 매우 재밌는것이 있으니 그것이 바로 online judge system - problem set archive 라는 것인데. 프로그램 문제를 내면 자기가 편한 언어로 소스를 만들어 온라인으로 보내면 서버에서 컴파일하고 실행해서 등수를 매겨주는것이다. 이 사이트엔 수천개의 문제도 있거니와 정기적으로 온라인 컨테스트도 한다. 이 사이트는 꽤 오래돼었는데 나도 몇년전에 문제를 풀어보고는 가끔 해봐야지 하구선 잊고 있다가 다시 생각이 났다.

ACM

이 사이트에 오늘 다시 들어가서 봤는데 한국은 영 순위에도 별로 없고 그 자체로 잘 보이질 않는다.. 먹고살기 바빠서 인가. 3일후에 또 다시 컨테스트가 있던데 그때까지 연습삼아 아카이브의 문제 몇개 풀어서 채점해보는 연습좀 하다가 컨테스트가 시작되면 이곳에서 자기 코드도 올려가며 보다 나은 버젼을 맹글어서 그곳에 올려봄이 어떨련지. 태극기좀 게양해 보자구우..

컨테스트가 비교적 자주 하긴 하지만 그건 그거대로 하구 평소땐 여기서 계속 아카이브의 문제들을 풀어봄도 좋을듯한데..어짜피 머리 회전에도 도움이 되는것이니. 팀으로 짜서 아카이브의 문제들을 지속적으로 풀어나가는데 걸린 시간과 비교해서 팀 성적을 누계내는데 여전히 태극기는 매우 아래에 있다. 조인씨 팀을 하나 짜서 등록한후 (등록하면 그때부터 시간을 잰다) 다들 짬짬이 풀어나가면 언젠가 상위에 랭크되지 않을까.

시작이 중요하다고..문제 아카이브의 첫번째 문제 (100번문제)를 여기서 함 풀어보자. 각각 소스도 올리고 (설명은 소스에서 간단히 주석으로) 판정결과도 올림 좋겠다.

제목	저자	변경일

각 문제별 위키 페이지 생성 룰 및 항목에 대해서 제시하고자 한다.

• 먼저 각 문제번호에 해당하는 페이지를 'http://www.joinc.co.kr/modules/moniwiki/wiki.php/Site/Test/ACM/문제번호' 식으로 생성한다.
• 첫번째 항목으로는 개요 를 두어 문제번호, 문제 제목, 문제 원문 링크, 이 문제에 대한 Ranklist의 링크를건다.
• 두번째 항목으로는 문제 설명 을 두어 문제의 원문을 번역한 내용을 소제목을 두어가며 넣는다. 이 때 온라인판정을 위해 Input/Output에 대해서 정확히 파악된 바가 있다면 반드시 추가로 소제목하에 부연설명을 한다.
• 세번째 항목으로는 문제 풀이 를 두고 하위 소제목으로 작성자명을, 그 아래에서 CPUT Time, Memory, 온라인판정결과 링크, 설명, 소스, 대화 를 하위제목으로 두어 채우면 좋을것이다.

이메일로 소스를 보내어 답장으로 판정결과를 받아보는 방법도 있지만, 시간도 더 오래걸리고 더 번거롭다. 직접 온라인으로 소스코드를 제출하고 즉석에서 판정결과를 받아보는 방법을 사용하자. 그 과정은 아래와 같다. (최근에는 이메일로 판정을 받는것을 더이상 하지 않는다고 적혀있다.)

• 먼저 사용자등록을 한다. 이때 적은 메일주소로 등록확인 링크와 함께 id/pw 를 알려준다. 그럼 그 링크로 접속하여 id/pw를 입력하면 등록이 완료된다. 이후 온라인 판정때 이때 부여받은 id를 입력한다.
• 문제에 대한 해답 소스를 작성하였다면 온라인으로 판정받고 순위도 봐야할것이다. 온라인판정을 할때의 항목은 다음과 같다.
  • Problem: 문제번호를 적는다 (번호만)
  • ID with suffix: 부여받은 ID를 적는다 보통 '숫자+알파벳2개' 로 이루어진다.
  • Lanaguage: 소스코드의 언어타입을 선택한다. C/C++/Pascal/Java 가 가능한다.
  • Comment: 비워도 상관없다.
  • Source code: 소스코드를 붙여넣는다. 이때 주의점은 아래 항목을 참조하라.
  • Or upload your code: 혹은 txt파일로 만들어서 업로드 하여도 된다.

첫번째로 중요한것은 Input/Output의 처리이다. 자동으로 판정하기때문에 어떻게 Input이 들어오는지 정확히 알고 소스를 만들어야 타임아웃 같은 에러가 안날것이다. 또한, 원하는대로 정확히 output을 해줘야 틀린답이라는 에러가 안날것이다. 허나, 문제의 Input/Output에 대한 설명 - 특히 Input에 대한 설명 - 이 좀 부실한 면이 없잖아 있어서 정확히 어떻게 여러 데이터가 들어온다는건지 알송달송할때가 있다. 다음 문서들을 반드시 먼저 읽어보고 소스들을 판정받기 바란다.

아래 링크에 보면 나와 있듯이 온라인 판정시엔 ONLINE_JUDGE 가 반드시 define되므로 로컬에서 테스트시의 편의를 위해서는 이것을 이용하여 전처리항목을 두어도 좋을것이다.

• Write source code
• Art of Programming Contest book by Ahmed Shamsul Arefin
• common mistakes
• Teamwork
• Tom Verhoeff guide

부연하자면, 각 문제들의 풀이 순위를 보면 대다수 CPU타임이 0.000 밖에 걸리지 않는다. 그리고 메모리 점유율도 매우 적다. 다만 정답을 푸는것에만 만족하지말고 최소한 그들과 동률을 이룰수 있는 알고리즘들을 생각해보자. 그러자면 이 문제들이 결코 쉽지가 않다는것을 알게 된다.

두번째로 중요한것은 온라인컴파일시 소스 언어의 표준으로 컴파일된다는 것이다. 이를테면 C로 짜게되면 // 으로 된 주석은 에러가 되는것이다. 그러므로 특정 컴파일러 (특히 GCC)에 국한된 확장기능은 배제하고 소스를 만들어야 한다. 아래 링크 사이트에서는 온라인으로 선택한 표준에 맞춰서 컴파일해주므로 미리 여기서 테스트해보는게 필요할 것이다.

웹 컴파일