'Google Code Jam'에 해당되는 글 3건

  1. 2009/09/13 Google Code Jam 2009 - Round 1
  2. 2009/09/04 2009 Google Code Jam
  3. 2008/07/18 Google Code Jam 2008 - Qualification Round (2)
일상 이야기/머리속 이야기2009/09/13 19:58

Google Code Jam 2009 - Round 1


이번엔 C++

목표했던 라운드1 까지 통과.

B번부터 풀었는데, next_permutation이라는 편한 함수를 이용해서 쉽게 풀 수 있는 문제 였다. 비록 1 wrong try가 있지만 -_-; 단순하게 생각했는데 n자리 숫자이기 때문에 앞에 0이 오면 따로 처리를 해 줘야 했다. ㅠㅠ

그 다음에 A번을 풀었는데, 역시 1 wrong try.. 구문 파싱해서 곱해주기만 하면 되는건데 파싱을 제대로 못해서 결과가 나오지 않았었다. orz..

새벽 1시부터 진행되었던 Round 1B에 참가를 했었는데, (Round 1A는 서울에서 대전에 오는 동안 있어서 참가 못함) C번을 풀려고 하니 벌써 새벽 2시 30분, 대회는 1시간이나 남았지만 졸리고 문제는 어려워 보이고 스코어 보드를 보니 C번을 푼 사람이 100명도 안될꺼 같아 상위 1000등까지 올라가는 대회에 별 지장이 없을꺼 같아서 자버렸는데 아침에 확인해 보니 다행히 통과했다.

Round 2는 Round 1A ~ 1C에서 통과한 3000명이 참가하며 상위 500위 안에 들면 Round 3에 참가 자격이 주어진다. 난 현재의 내 위치를 알기에 Round 3까지 가는건 기대도 하지 않는다. 하하하. 어서 공부하자 -_-;

덧) 우리 나라에선 199명이나 참가를 했는데 반 정도가 Round2 에 올라 간듯. ( http://www.go-hero.net/jam/09/regions/South%20Korea ) 올레~

저작자 표시
Posted by Mastojun
TAG Google Code Jam
Trackback 0 Comment 0
일상 이야기/머리속 이야기2009/09/04 12:49

2009 Google Code Jam

이번엔 basic(?)

올해도 돌아온 구글 코드 잼!
올해도 참가한 구글 코드 잼!

느낌상으론 작년 Qualification Round보단 쉬워진거 같다. 

어제 저녁 10시쯤 운동좀 다녀올까 하고 차비를 하는 중에 생각이 나서 부랴부랴 접속해서 부랴부랴 풀었으나, 역시 느리다 -_ㅠ 누구는 한문제에 10분도 안걸려서 후다닥 풀어 내던데 난 한시간은 족히 걸리는듯 하니.

더군다나 C번 문제는 너무나도 전형적인 문제인데 Large case를 제 시간에 푸는 알고리즘을 떠올리는데 오래 걸렸다. 덕분에 Small 과 시간차이가 1시간 20분. ㅠㅠ

그래도 한번의 Wrong try도 없이 모두 깨끗히 통과 했다는것과 3개 모두 small과 large를 풀었다는거에 만족을 하며 올해는 Round1 만이라도 통과했으면 하는 소박한 꿈을 꿔본다. :D

저작자 표시
Posted by Mastojun
TAG Google Code Jam
Trackback 0 Comment 0
일상 이야기/머리속 이야기2008/07/18 23:53

Google Code Jam 2008 - Qualification Round

사용자 삽입 이미지

C언어가 나올때까지 리플래쉬 해서 찍은 이미지!

뛰어난 프로그래머의 등용문 이라고 불려지는 구글 코드잼!
24시간이라는 제한시간에 3문제 밖에 나오지 않아서 처음엔 문제의 난이도가 얼마나 어려운거야 @_@ 라고 생각을 했는데, 이미 3문제를 모두 푼 사람이 수두룩 했다 -_-;

문제는 생각보다 어렵지 않았다, A와 B번 문제는 쉽게 풀 수 있었는데, small을 한번에 가볍게 통과하고 large도 대회가 끝나고 체점이 된것을 확인하니 모두 통과 50점으로 마감할 수 있었지만.. 문제를 풀었다고 해도 이렇게 풀면 왜 정답이 나오는지는 증명하는 방식을 모른다. 학부 알고리즘 시간에도 알고리즘 증명 방법 같은건 배웠던 기억이...-_-; Algospot에 A번 증명하는 글은 올라왔으니 보고 머리를 굴려보도록 하자!
(문제는 정말 쉬웠는데, 영어 해석이 잘 안됐고 [......] 알고리즘은 쉽게 떠올렸으나 코딩이 잘 안됐다 [......]  코딩연습 부족 ㅠㅠ)

C번은 어려웠다, ACM문제 풀때도 저런 복잡한 그림이 나오면 일단 지나가고 봤었는데 large를 두개다 틀리면(기우였지만) 25점을 넘기지 못해 Online Round1에 진출할 수 없기 때문에 풀려고 덤볐는데.

처음엔 적분을 이용해서 풀까? 라고 생각을 하다가 예전에 풀었던 문제가 생각이 나서(난 적분을 이용해서 풀었는데 같이 스터디를 진행했던 Andstudy분들은 중학교 수학지식으로 풀으셨다. 왠지 진기분 -_-;;) 적분 말고 다른 방법을 골똘히 생각해보기 시작! 하지만 결국 gg를 쳤고, gpgstudy에 누군가가 "이 문제는 적분을 이용해야 한다는군요" 라는 글을 보고 그냥 깔끔하게 적분을 이용해서 풀기 시작했다.

라켓의 전체 영역을구하고 파리를 잡을 수 있는 영역을 구해서 나누는 식으로 문제를 접근!
라켓의 중심을 원점으로 생각하고 1사 분면의 영역만 구한다음에 4를 곱해서 계산을 했는데......
테스트 케이스의 1번째와 3번째는 제대로 나오는데 2번째와 4, 5 번째는 제대로 안나오는거다. 뭐가 문제인지 몇시간 동안 고민을 해보고 디버깅을 해봐도 생각했던 적분 방식대로 코드는 제대로 돌아가고, 혹시 적분 테이블에 있던 root( a² - x² )의 부정적분 연산 결과가 잘못되었나 의심이 들어서 [.....] 몇가지 방식으로 검증도 해봤으나 아무런 이상이 없다.

결국 몹쓸 생각(예시로 나와있는 답이 잘못된거야!)을 해버리고 그대로 풀어서 제출 -____-; incorrect를 받고 gg쳐버리고 그냥 잠을 잤다.

일어나서 회사에서 일을 하려고 해도 머리속에서 계속 맴도는 그 문제, 다시 소스코드를 들여다보니 왠걸.. 파리는 살짝 스치기만 해도 돌아가시기 때문에 모든 Hit영역에 파리의 반지름을 적용해서 계산해야 하는데 안쪽 스트링에는 제대로 적용시켰지만 라켓의 테두리엔 그걸 빼먹었던거다. 안쪽 영역을 구했던 S = R-t; 라는 코드를 S = R-t-f; 로 고치고 (딱 2bytes추가) 제출해보니 Correct.

이것만 풀어도 순위가 2000여 등에서 500등 정도까지 쑥 올라가는건데 너무 아쉽다. 본격적인 Online Round가 시작되면 제대로된 알고리즘 문제가 출제되기 시작할테고, 그럼 아직 잘 모르는 난 실력차이가 확실히 나서 저만치 밀릴꺼 같은데 ㅠ_ㅠ..

더도 말고 덜도 말고 구글코리아에 가서 티셔츠라도 받아봤으면 하는 작은 바람..

Posted by Mastojun
TAG ACM-ICPC, algospot, Google, Google Code Jam, 알고리즘
Trackback 0 Comment 2