ACM 프로그래밍 콘테스트
글쓴이: geekforum / 작성시간: 일, 2002/03/24 - 8:46오후
ACM 프로그래밍 콘테스트 결과가 발표되었군요. Shanghai JiaoTong 대학교가 총 6문제를 풀어서 1위를 차지했고 MIT, 캐나다의 워털루 대학교가 2, 3위를 차지했군요. 우리나라의 서울대학교도 13위에 들어 있고 이화여대도 Honorable Mention(이게 뭐지)에 들어 있네요. 모두들 축하해 줍시다.
ACM 프로그래밍 콘테스트의 홈페이지는 http://icpc.baylor.edu/icpc/이고 결과는 http://icpc.baylor.edu/icpc/Finals/Scoreboard/default.htm에서, 올해 문제는 http://icpc.baylor.edu/icpc/Finals/problems.pdf에서 보실 수 있습니다. 모두들 한번 보시고 답좀 올려 주세요~ 근데 문제가 좀 기네요. 혹시 여기 오시는 분들 중에서 출전하신 분이 만약 계신다면 경험담도 한번 들어보고 싶네요~
* 관리자 코멘트(webmaster):
pdf파일을 보실 수 없는 분들은 아래 관련 링크를 클릭하세요...
Forums:
저...저는 워털루CS 다니는 학생인데요...지금 병특으로 한국에
저...저는 워털루CS 다니는 학생인데요...
지금 병특으로 한국에서 일하구 있다가 머리좀 식힐려구
KESL.org에서 링크되어서 들어왔는데...
이 대회에 관심있으신 분들이 많군요.....
저희 학교에 대해서 많이 알구 계시네엽 ^^
어떠케 아실까.. 궁금궁금..
조금 놀라서 글써봅니당...
이번 대회에 나간애중에 한명은 저 OS할때 TA였슴다..
똘똘하네.. ^^;;
그럼!
qha@acm.org
p.s. 로그인을 안하면 다 나는 겁쟁이로 표시가 되는군요...-_-;; 아뒤가 없어서 지송~
아.. ACM에의 기억이 나네요.밑에분들의 말처럼 입상하는 사람들
아.. ACM에의 기억이 나네요.
밑에분들의 말처럼 입상하는 사람들은 전문가인가요?
캬... 근데 어떻게 하면 전문가가 될수 있나요?
뭐 교수님들이 그네들은 고딩때부터 알고리즘의 종류는 다 마스터했다고 하더라구요.
그러시면서 너희들이 게임이 안되는게 당연하다고...
참고로 절대 무식하게 백트랙킹같은 걸로는 풀리지 않습니다.
타임아웃에 걸립니다.
또 아너러블 멘션은 참가상을 뜻합니다.
yyyy
yyyy
하하 뭔가 오해하시나본데요.ACM이게 무슨 알고리듬 최적화랍디까?
하하 뭔가 오해하시나본데요.
ACM이게 무슨 알고리듬 최적화랍디까?
지역마다 다르겠지만 전 미국 남캘리포니아 지역에 참가 했었습니다. 무슨 오묘한 알고리듬 사용하려고 하면 그냥 망한다는것만 알아주세요. 그럴 시간도 없을뿐더러 영어로 하면
Brute-force 즉 무식하게 나가는 방법이 가장 효과적이죠.
일단 저희 지역은 절때 거의 시간 제한이 없습니다.
무슨 말인지 아셨죠?
그뒤로는 ACM 대단하게 않봅니다. 코드를 보고 코드의 완성도나 여러분들이 생각하는 창조적 알고리듬은 정말 주관적이라 판단하기 힘듭니다. 그러니 대회가 무식하게 나갈수 밖에요.
저희 교수님도 그러더군요. 복잡하게 생각하면 망한다.
가장 단순무식한 알고리듬을 사요하고 거의 Debug없이 프로그램 돌릴수 있을 정도로 연습하라.
무슨뜻인지 아셨죠?
참고로 저희 팀은 1문제 밖에 못풀었어여.
역시나 Caltech 과 UC San Diego 의 박빙의 승부.
이넘들은 무슨 합숙훈련하는것 같음.
나도 우리과에서 꽤나 똑똑한 넘들과 나갔었는데
역시나 연습부족이 여실히 들어나더군요.
여기시 우승하려면 하루에 10문제씩 푸세요.
그럼 이만
> 가장 단순무식한 알고리듬을 사요하고 거의 Debug없이 프로그램 돌릴
> 가장 단순무식한 알고리듬을 사요하고 거의 Debug없이 프로그램 돌릴수 있을 정도로 연습하라.
한 두 문제 정도가 목표라면 이 방법이 가장 좋죠. 하지만 단순무식한 알고리즘으로는 주어진 제한시간 내에 문제를 풀 수 없도록 문제와 테스트 데이터를 준비한답니다. 1등을 노리려면 다른 전략을 준비하세요.
요즘 저희 학교가 ACM에 관심이 없어져서 그렇지그교수님은 저희학교을
요즘 저희 학교가 ACM에 관심이 없어져서 그렇지
그교수님은 저희학교을 1990년대 초에 세계대회 결선 까지 올리셨던분입니다. 경험도 많으시죠. 제가 직접 경험해보니 그교수님 말씀이 피부로 느껴지더군요. 기억하세요 프로램 실행시간에 대한 제한이 거의 없다는게 무슨 뜻인지. 누군가 말씀하셨지만 NP문제가 많습니다. 이런건 최적화 되는게 아니에요.
NP-hard 문제는 한 대회에 많아야 1-3개 정도입니다. 올해 대회에
NP-hard 문제는 한 대회에 많아야 1-3개 정도입니다. 올해 대회에선 안 보이네요.
문제는 지역마다 틀려요.그러니 하나만 보고 판단하지 마시길
문제는 지역마다 틀려요.
그러니 하나만 보고 판단하지 마시길
음. 날카롭네요. 절대 알고리즘 최적화가 아니죠. Brute-force거
음. 날카롭네요. 절대 알고리즘 최적화가 아니죠. Brute-force거나 머리가 좋다면
약간의 최적화정도면... 항상 보면 NP에 가까운 문제들이 나오더군요...
문제를 보면 극소수 문제를 제외하곤 모두 풀 수 있을 것 같습니다. 물론
문제를 보면 극소수 문제를 제외하곤 모두 풀 수 있을 것 같습니다. 물론 머리로만요. :)
그래서 생각한 것을 무식하게 풀어봅니다. 샘플 데이터는 통과군요. 이것을 jugde에 보내면 무식하게 time-out이라고 답변이 올 가능성이 큽니다.
즉, 절대로 무식하게 백트래킹 같은것을 시도하면 실패할 가능성이 높다는 것이죠.
이 것을 공부하기가 가장 힘든 것 같습니다. 작년 11월 대회장에서 문제를 받아들었을 때 몇 문제는 풀 수 있을것 같았는데, 타임아웃에 걸릴때도 있고, 샘플 데이터에 속아서 잘못 푼 경우도 많고, 문제의 영어 의미 해석이 오묘하게(?) 되는 바람에 잘못 푼 경우도 많았습니다.
이 대회에서 입상하는 비결은 정말 많이 풀어보는 방법, 다양한 문제를 만나서 그것을 해결해 보는 것 밖에 없을 것 같습니다. :)
--
Seo, Hee-Seung.
http://anitype.net/anitype/
http://anitype.net/hirenn/
--
http://renn.sapzilla.org/
저도 ACM에 관심이 있어서... 예전부터 몇 몇 문제 풀어(? 혹은 읽
저도 ACM에 관심이 있어서... 예전부터 몇 몇 문제 풀어(? 혹은 읽어)보았습니다.
뭐... "어떻게 풀어도 서울만 가면 된다"로 풀면...
그중 몇몇 문제는 풀수 있었고... 풀수 있을것 같았습니다.
그렇치만... 바른 알고리즘으로 최적을 구해야 한다는 것에는.. 많이 모자란 풀이가....^^;;;;
코드 최적화가 아닌, 알고리즘 최적화는 정말 어려운것 같습니다. 물론 코드 최적화도 어렵지만...
사실 "변형 하노이탑" 같은 유명한 문제도.... 자신있게 "이것이 최적이다" 라고 풀어낼 자신이 없는 저에게는 ACM 같은 것은 꿈같이 보임니다.
ICCC나 생각해볼려고 합니다.... 아이디어는 있는데...
나중에 시간 나면 해봐야죠...
--
늘...
각 지역 예선 사이트가 있는데 재작년부터 대전이 아시아 예선 사이트로 추
각 지역 예선 사이트가 있는데 재작년부터 대전이 아시아 예선 사이트로 추가되어서 한국 학생들은 굳이 외국으로 나갈 필요가 없게 되었습니다. 비행기표와 경비만 있으면 가도 되겠지만요.
재작년에 청화대에서 대전에 왔던 학생들은 미리 400문제를 풀어보고 왔다고 합니다. -_-; 출제위원이었던 교수님도 많이 풀어본 놈이 잘한다고 하더군요. 그래도 많이 풀어봤든 어쨌든 잘한다는 사실만큼은 인정해야겠죠. ^_^
워털루 대학은 한국에 잘 알려지지 않은 대학인데 학생들을 MS 에서 (MS 가 나온다고 또 뭐라 하지 마시기를.. -_-) 미리 찍어놓을 정도로 CS 분야에서 강한 학교라고 하더군요.
한국 학생들도 많이 많이 도전해서 앞으로 더 좋은 결과 얻었으면 좋겠네요. ^^
워털루 대학은 Mathematica와 함께 유명한 수학/수치해석프로그
워털루 대학은 Mathematica와 함께 유명한 수학/수치해석
프로그램인 Maple을 만든 symbolic computation Group
으로 잘 알려진 학교이기도 하지요
waterloo 는 Maple 뿐만 아니라Watcom C/C++ 의
waterloo 는 Maple 뿐만 아니라
Watcom C/C++ 의 고향이기도 하죠.
캐나다에 있는 대학이고 실무를 잘 가르쳐 내보내고 캐나다이기 때문에 임금
캐나다에 있는 대학이고 실무를 잘 가르쳐 내보내고 캐나다이기 때문에 임금이 싸다고
M$가 좋아하는 대학으로 기억되네요. 잘은 모르겠구요.. 그대학이 이 대학인가보다
하는 생각이 들어서... 아님 말구효헤헤
워털루 대학은 아마 캐나다 온타리오주에 있는 대학인 걸로 알고 있고요.
워털루 대학은 아마 캐나다 온타리오주에 있는 대학인 걸로 알고 있고요.
조금은 비정상적으로 CS가 쎈 학교입니다.
학문적으로 센 것이 아니라, 실무에서 말이죠.
학교 다니면서 실무를 겸하게 되어 있고..
3학기 제인데 한학기를 실무를 하던가.. 그런 식으로 하는 것으로 알고 있습니다.
말씀하신 대로 Microsoft에서 가장 선호하는 학교로 알려져 있습니다. (단순히 임금이 싸서이지는 않을 겁니다. 그러면 한국도 선호해야죠.. -_-;;)
나는 이름없는 비겁자가 아님다.사실 메이플 열라 좋습니다. 대학원 다
나는 이름없는 비겁자가 아님다.
사실 메이플 열라 좋습니다. 대학원 다닐때 편미분 방정식 메이플로 다 풀었습니다.
열전달..
그거 웃긴게 color를 colour로 쳐도 됩니다.
캐나다서 만든거니까
포트뗬邰
맞는 걸로 알고 있어요~ ^^시설이 MIT보다 우수하다고 읽은 기억이
맞는 걸로 알고 있어요~ ^^
시설이 MIT보다 우수하다고 읽은 기억이 나네요.
음.... 대학 1학년때 학교의 Cyber-930 메인프레임에 vt-2
음.... 대학 1학년때 학교의 Cyber-930 메인프레임에 vt-220 터미널로 접속해서 포트란 배웠었는데...
그 포트란 컴파일러가 워털루 대학 꺼였었죠.
그때만 해도, 나폴레옹이 싸웠던 장소에 만들어진 학교인가? 라고 생각했었다는.... 헐헐...
암튼 이 학교에서 나온 컴파일러도 언어별로 여러가지 있데요?
참고로 저는 93학번...
Watcom C 의 Wat 가 워털루에서 따온것이었나 보군요. ^^
Watcom C 의 Wat 가 워털루에서 따온것이었나 보군요. ^^
사이버를 쓰던 대학이라면 혹시 우리 선배님? ^^
그냥 문제만 보면 쉬워보일지도 모릅니다.문제를 '읽고'나면 코드가 막
그냥 문제만 보면 쉬워보일지도 모릅니다.
문제를 '읽고'나면 코드가 막 떠오릅니다.
하지만 실제로 'Judge'를 '당해보면'...
기가 막힙니다.
정말로 당했다는 기분밖에는...
저를 비롯한 친구들에게만 해당되는 이야기일지 모르나
지난 대회 결과를 보시면 어느정도 이해가 되실 겁니다.
작년 서울대와 동경대의 막판 1위 다툼이 생각나는군요..
(문제 푸느라 정신없었지만 계속 서울대가 1위를 지켰던듯..)
국내 대학이 세계대회에서 순위에 들었다는게 자랑스럽지만
상위팀에서 아시아 대학들을 볼 수 없다는게 참 아쉽습니다.
문제들이 프로그래밍 실력보다는 수학 그리고 알고리즘을 묻기때문에 우리나라
문제들이 프로그래밍 실력보다는 수학 그리고 알고리즘을 묻기때문에 우리나라 학생들은
약할수밖에 없을듯 싶네요. 특히 고등학교때 미적은 배워도 정수론이나 이산수학 개념은
거의 배우지 않고 대학에 들어가는 우리나라 학생들에겐 더욱 불리하겠죠...
어자피 3학년 이상 출전입니다. =+=
어자피 3학년 이상 출전입니다. =+=
학년 제한은 못본것 같은데요..
학년 제한은 못본것 같은데요..
다시보세요...
다시보세요...
학년 제한 없는 걸로 아는데..저희 학과에서 2학년짜리가 팀에 포함되
학년 제한 없는 걸로 아는데..
저희 학과에서 2학년짜리가 팀에 포함되어서 출전했었거든요..
학년 제한도 있고, 휴학생은 안된다는 규정도 있습니다.
학년 제한도 있고, 휴학생은 안된다는 규정도 있습니다.
학년 제한 없는거 맞는데 -_-;1학년들도 많이 나갑니다..
학년 제한 없는거 맞는데 -_-;
1학년들도 많이 나갑니다..
학년 제한은 없습니다.대학원생 이야기라면 모를까요. --;
학년 제한은 없습니다.
대학원생 이야기라면 모를까요. --;
@ 관계자..
대회 규정을 아무리 읽어봐도 학부생 학년 제한은 없습니다. -_-; 재작
대회 규정을 아무리 읽어봐도 학부생 학년 제한은 없습니다. -_-; 재작년에 세계 대회 나갔던 카이스트 학생중 두명인가 한명이 1학년인가 2학년이었죠. -_-;
> 상위팀에서 아시아 대학들을 볼 수 없다는게 참 아쉽습니다. 아
> 상위팀에서 아시아 대학들을 볼 수 없다는게 참 아쉽습니다.
아시아 대학이 아니라 국내대학으로 정정합니다. ^^
한번 acm문제 풀어 보세요 장난이 아닙니당.
한번 acm문제 풀어 보세요 장난이 아닙니당.
서울대는 13위가 아니고 공동 11위입니다.
서울대는 13위가 아니고 공동 11위입니다.
음...저희 학교에서 어느정도 난다 긴다 하는 애들이 나갔었는데.
음...
저희 학교에서 어느정도 난다 긴다 하는 애들이 나갔었는데...
물론 핑계인지 모르겠지만...
"경시대회를 전문으로 준비하는애들이 거의 휩쓸어가더라..."
라는 말을 하더군요....
어떻게 생각하세요?
그렇죠..저희학교도 ACM에서 꽤 좋은 성적을 올리는 학교중 하나인데
그렇죠..
저희학교도 ACM에서 꽤 좋은 성적을 올리는 학교중 하나인데..
그 성적 올리는 애들은 다 특기자로 들어온..알고리즘의 스페셜리스트들입니다..-_-;
걔네들과 비교해서 일반 학생들은 출발선 부터가 조금 뒤라고 할까요?
그런 차이가 느껴질 정도죠..
대학소속 운동선수들 예를 들면, 우리나라처럼 거의 운동성적만으로 뽑는 나
대학소속 운동선수들 예를 들면, 우리나라처럼 거의 운동성적만으로 뽑는 나라도 있고 말그대로 공부하면서 취미로 운동하는 애들도 있습니다.
하지만 전문 대학운동선수들이 경기나 올림픽을 휩쓴다 해도 취미로 하는 애들이 '아마추어 정신에 위배된다'고 딴지걸지는 않습니다.
자존심 때문이기도 하겠지만 무엇보다 어떤식으로 운동을 했건간에 그 운동면에서 자신보다 잘한다는건 사실이기 때문이지요.
수능점수가 실제수학능력에 완전 비례하는 것도 아니고 토익점수가 영어실력을 그대로 대변하는 것도 아닙니다(그렇게 할 방법도 없고...) 공평하게 치뤄지고 어느정도 개연성만 있다면 뒤돌아서 시험가지고 딴지거는게 보기좋지는 않네요.
경시대회를 전문으로 준비한다는 건 좀 억지같고 그 시험을 위해 딴거 재쳐두고 보다 많은 노력을 했다면 더 좋은 성적을 얻는게 당연하다고 생각합니다.
음, 주제넘게 한마디 더 하자면 우리나라 사람들은 지식보다 지능을 더 중요시 하는거 같습니다...
지식보다 지능이 더 중요한 것 아닌가요? 지식은 성실성과 관련이있지만
지식보다 지능이 더 중요한 것 아닌가요? 지식은 성실성과 관련이
있지만 지능은 자체적인 능력과 상관이 있으니 말입니다. 지능이
뛰어난 사람에게 적절한 방법을 통해서 지식을 늘려줄 수는
있지만 지식이 많은 사람에게 지능을 올려주는 것은 힘들지
않습니까?
제가 보기엔 우리나라는 지능(잠재적인 능력)보다는 지식(성실성)
을 중요시해서 문제인 것 같은데요?
에, 제말은 우리나라가 아니라 우리나라 사람들이었습니다.하긴 그러고
에, 제말은 우리나라가 아니라 우리나라 사람들이었습니다.
하긴 그러고 보니 제도권 교육은 지식을 넘 중요시하는 면이 있군요. 미처 생각못했습니다.
음, 주위에서 또래들로부터 많이 봤던 것들로는... 예를들어 시험을 쳐서 같이 점수가 잘 나왔더래도 마치 자기가 공부 더 조금해서 잘 봤다는 식으로 얘기하는 넘들이 많았습니다.
기본실력으로 봤다는둥, 아침에 지하철 타고 오면서 본게 다라는둥 --;;;
(뭐, 제 주위에만 요상한 놈들이 많아서였는지는 모르겠네요)
그리고 연습문제 숙제따위는 그냥 부담없이 배끼면서도 까다로운 알고리즘 문제는 어떻게든 풀어보이려고 하던데요. 둘다 중요한것 같은데...
글쎄, 지능도 물론 중요하겠지만 개화되지 않는다면 그게 무슨 지능인지요. 묵혀놓은 복권이죠.
가능성은... 고등학교때까지 봐준걸로 충분하지 않을까요 (제도권 교육이야 여전히 맘에 안들지만 그나마 수능이 도입되서 학력고사보단 숨통을 틔웠다고 생각합니다)
서양애들은 대학교때 죽어라고 공부하는데 울나라는 좀 같은 기간동안 허술한것 같아서 꺼낸 말이었습니다. 지능이야 물론 중요하죠. 개인적으로도 상당히 불성실한 놈이고 수능덕에 좋은학교 올 수 있었습니다만 나이먹고 보니 성실한것도 하나의 내재된 능력이란 생각이 듭니다.
지능이 뛰어나다면 나타나는 성과도 비례해야죠. 그렇게 못만든건 일단 자기책임도 한 몫 하지 않을까요? (적성에 맞는 과로 과감하게 전과한다던지. 저처럼 아예 전공과 상관없는걸 파고 앉아 있다던지... -_-;; )
> 음, 주제넘게 한마디 더 하자면 우리나라 사람들은 지식보다 지능을 더
> 음, 주제넘게 한마디 더 하자면 우리나라 사람들은 지식보다 지능을 더 중요시 하는거 같습니다...
서류 또는 수치상으로 증명할 수 있는 것을 대단히 선호하는 경향이 있죠.
Honorable Mention...이건 아마 최소한 한 문제 이상 푼
Honorable Mention...이건 아마 최소한 한 문제 이상 푼 팀을
의미하는 것일 겁니다.
참가해서 한 문제도 못 푸는 경우도 종종 있는듯 합니다...;;
생각보다 문제가 까다롭거든요 ㅡ.ㅡ;;;;
흔히 말하는 함정이 있기 때문이죠...
작년 ACMICPC 대전대회 참가했던사람입니다.그땐 Honorab
작년 ACMICPC 대전대회 참가했던사람입니다.
그땐 Honorable... 은 한문제도 못푼 팀을 지칭하는 것이었죠.
한문제만 풀어도 등수에 올라갔었거든요.
그래서 우스갯소리로 Unhonorable 이라고 부르기도 했죠 -_-;
서울대는 20위아닌가요?20 Seoul National Unive
서울대는 20위아닌가요?
20 Seoul National University 4 699
서울대가 13위는 아니네요..10위 까지는 정확한 순위를 매기지만 그
서울대가 13위는 아니네요..
10위 까지는 정확한 순위를 매기지만 그 이후에는 맞춘문제의 수에 따라 이름 순으로 정렬을 해 놓았습니다. 즉 서울대는 11위 에서 17위 사이가 되는 거죠.
이 대회의 특징이 정확하게 1등부터 꼴찌까지의 등수를 매기지 않습니다. 상위 어디까지만 정확하게 등수를 밝히고 나머진 정답을 맞춘 수 대로 이름순 정렬만 합니다. 또한 하위 50%는 맞춘 문제의 수에 상관 없이 이름순 정렬만 하죠..
등수 일단 문제를 많이 푼팀이 등수가 높게 됩니다. 당연히.. ^^
문제를 풀면 즉석에서 문제의 답안을 제출하게 됩니다. 소스를...
그러면 어디엔가 있는 심사위원들이 그것의 정답 여부를 알려주게 됩니다.(콘테스트 시간이 5시간 정도 됩니다. 점심도 도시락을 주더군요..) 금방은 아니고 기다리면 옵니다. 이것을 처리하는 PC^2 (PC square라고 하더군요) 라는 소프트웨어가 있습니다.
문제가 오답으로 판명되면 몇분간의 벌점 시간이 주어집니다(한 20분 정도 됩니다). 무작정 올리게 되면 벌점을 많이 먹게되죠... -_-;;;
그래서 문제를 푼 시간과 이 벌점의 합계가 Penalty가 됩니다.
문제는 대부분이 알고리즘, 기하학 뭐..그런 류입니다. 모두 영어고요. -_-; 1페이지 에서 3페이지 정도 됩니다. 한문제당..
책이나 인쇄된것은 무엇이든 가져갈수 있습니다. 디스켓이나 CD같은 것은 제외 됩니다.
아시아 지역 예선을 한국에서 했는데 관심 있는 분들은 가보시길..
http://cs.kaist.ac.kr/~acmicpc/index-k.html
기회가 되고 자신이 있는 분들은 참가해 보세요. ^^
아시아 지역 예선을 한국에서 한 게 아니라 수많은(!) 아시아 지역 예선
아시아 지역 예선을 한국에서 한 게 아니라 수많은(!) 아시아 지역 예선 중에 대전 지역에서도 열린 것입니다.
각 지역 예선 1위 및 와일드카드 팀들이 모여 세계 대회에 참가합니다. 한 대학 당 최대 1 팀.