Canon | Canon EOS Kiss Digital X | Normal program | Average | 1/100sec | F/3.5 | 0.00 EV | 63.0mm | ISO-1600 | Off Compulsory

2000 년 부터 시작된 국내 ACM-ICPC 대회는 ( 전국 대학생 프로그래밍 경시대회를 겸한 것은 2001 년 부터 시작 ) 첫 3년간 ( 2000년 부터 2002 년 까지 ) 대전 카이스트 캠퍼스 체육관에서 개최되었다. 그 후 대회 참가자들의 다수를 차지하는 수도권 지역 학생들의 편의를 위해 2003 년 부터 2009 년 까지는 서울에서 개최되었다가 2010 년부터 다시 대전 카이스트 캠퍼스에서 개최된다. 장소 변경에 대해서 주최측이 밝힌 이유는 없지만 아마 비용 문제가 가장 크지 않았을 까 싶다. 서울에서 대회를 개최하기 위해서는 대회를 치룰만한 장소를 2일간 대관을 해야 하는데 국내 ICPC 대회의 경우 참가비도 받지 않는지라 대회 운영비용을 전적으로 후원에 의지해야 하는 것으로 알고 있다. 
어쩃든 대회 참가비를 받지 않고 가급적 많은 팀을 본선에 출전시킨다는 것 만으로도 국내 ICPC 대회는 정말 훌륭하게 매년 치루고 있다고 생각한다.

Canon | Canon EOS Kiss Digital X | Normal program | Average | 1/250sec | F/5.6 | 0.00 EV | 63.0mm | ISO-1600 | Off Compulsory

이 문양은 바로 ACM-ICPC 대회의 로고 문양이다. Think - Create - Solve ! 
그런데, 저 깃발은 10 년전과 동일하다... 설마 10 년째 같은 로고 깃발을 쓰는 것은 아니겠지...? 

Canon | Canon EOS Kiss Digital X | Normal program | Average | 1/60sec | F/2.8 | 0.00 EV | 75.0mm | ISO-1600 | Off Compulsory

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

SRM 500 을 맞이해서 포럼에 Eeyore 라는 캐나디언이 "The Past and Present of Single Round Match" 라는 글이 올라왔는데. 흥미로운 내용이 많아서 간략하게 요약해 본다. 

내가 SnapDragon 을 처음 만난 것은 2002년 가을 University of Warterloo 졸업을 앞둔 시점이었다. 그는 ACM-ICPC 대회 준비를 도와주기 위해 학교를 방문하곤 했는데 함께 모의고사를 치루면 항상 1등을 차지하곤 했다. 그가 과격하게 키보드를 두드리면서 코딩을 하는 모습은 피아니스트가 베토벤의 광시곡을 연주하는 것 같았다. 한문자의 변수들과 괄호로 가득찬 그의 코딩 스타일은 암호문을 보는 것 같았다. 

그는 또한 거의 모든 게임 콘솔을 다 보유하고 있으면서 매일같이 몇시간씩 게임을 즐기는 게임광이기도 했다. 

"게임은 두뇌 발달에 좋아. 하지만 사람을 게으르게 만들기도 하지". 
현재 SnapDragon 은 Google 에서 근무하고 있다.  

SnapDragon 이 말하는 TopCoder 가 다른 프로그래밍 경시대회에 비해 갖는 장점은 문제의 스펙이 명확하다는 것, 그리고 대회마다 상금이 걸려있다는 것이다. 2001 ~ 2002 년 당시는 닷컴 버블의 막바지로 TopCoder 역시 많은 스폰서쉽을 받아 주당 2회씩 상금 매치가 열리곤 했다. TopCoder 의 사업모델이 컴포넌트 설계/개발에 치중하게 되고 SRM 의 상금매치가 없어지기 시작하면서 상금에 대한 매력은 줄어들었지만 SRM 은 여전히 전세계의 Problem Solver 들을 끌어모이고 있다. 

radeye 는 2002 년에서 2005 년 사이에 활발하게 활동했고 요즘도 이따금 SRM 에 참가한다. 그는 dvips 라는 유명한 DVI-to-PostScript 컴파일러의 개발자이자 LaTex Software Stack 의 개발자로도 유명하다. 최근에는 모든 루빅스 큐브는 최대 20회의 이동으로 풀수 있다 는 증명을 하기도 했다. 그는 TopCoder 의 알고리즘 문제 해결능력이 실제 프로젝트에도 도움을 주며, 자신의 프로그래밍 실력향상에 큰 도움이 되었다고 말한다. 

dangelo 는 2002 년부터 2005 년사이에 77 회의 SRM 에 참가했다. 그는 facebook 의 CTO 였으며 최근에 Facebook 을 떠나 소셜 Q&A 서비스인 Quora 를 설립했다. 자신이 Caltech 의 빡센 코스웍을 소화하기에 벅차서 SRM 참가가 뜸해졌다고 말한다. 그가 말하는 TopCoder 의 장점은 프로그래밍 경시대회를 통해 알고리즘을 빠른 시간에 적용하고, 설계하는 기술을 쌓을 수 있다는 것이다. 물론, 이 것 이외에도 현업에서의 프로젝트는 다른 여러가지 기술들도 필요하므로 이에 대해서 공부해야 한다고 조언한다. 

2005 년에는 2 명의 괴물이 등장한다. 이해 3월에 데뷔한 Petr 은 지금까지 Div1 의 Easy / Medium / Hard 각각의 문제 성공률이 96% / 93% / 85% 에 이르며 그의 230 번 매치중 136 번을 우승했다. ACRush 는 Petr 보다 8개월 늦게 데뷔했다. 그는 TopCoder 1등이 되기까지 치룬 79 번의 매치 중에서 30 번을 우승했다. 이 두사람은 모두 ACM-ICPC 월드파이널에서 2등을 한 경험이 있으며, Google Code Jam, Facebook Hacker Cup 등의 외부 대회에서 우승을 차지한 바 있다.  TopCoder Algorithm 랭킹 1위와 2위를 업치락 뒤치락 하는 이들이지만 ACRush 는 Petr 과 같은 라이벌이 있어서 무척 행복하다고 말한다. Petr 은 현재 Google 에서 근무중이다. 

dcp 는 2006년 4월에 데뷔한 이래 지금까지 201 번의 매치를 치뤘고, 데뷔 후 3년이 지난 137번째 매치에서 Div 1 에 올라선다. dcp 는 자신이 도달할 수 없는 구체적인 목표를 세우지 않는 대신 일주일에 5~6 문제를 푸는 정도의 스스로 달성가능한 목표를 세우고 있다고 한다. 매주 3-4 시간정도 연습한다는 그는 rating 에 크게 연연해 하지 않고 SRM 자체를 "정신적인 운동" 으로 즐긴다고 말한다. 

과연 SRM 이 이렇게 즐길만한 가치가 있을까? Minilek 은 MIT 3학년때 TopCoder 를 시작해서 이제 MIT 박사과정 졸업을 앞둔 학생이다. 그는 TopCoder SRM 의 옹호주의자이며 SRM 을 즐기는 사람 중 한명이다. 그에게 프로그래밍은 가장 즐거운 취미생활이며, 또한 TopCoder 는 취업 인터뷰에도 큰 도움을 주었다고 한다. Minilek 은 스스로에게 강요하지 않고 SRM 을 즐기는 것이 중요하다는 충고를 한다. 지금까지 193 회의 SRM 을 치룬 그는 첫 151 번의 매치에서 green 에서 red 로 점증적으로 rating 을 향상시켰다. Minelik 은 말하길 "자신이 즐길 수 있다면 많이 하게 되고, 자연스럽게 실력이 향상될 겁니다. 이건 재미있게 즐기는 거지 일 하는 것과는 다릅니다"

Olexiy 는 2005 년 8월 부터 2009년 2월까지 많은 문제를 출제하면서 SRM 의 코디네이터로 공헌했다. 그는 이후 ivan_metelsky 에서 자신의 자리를 넘겨주었다. Olexiy 는 과거와 현재의 SRM 에 대한 비교에 비해 SRM 의 문제들이 요새는 매우 어려워졌다는 점을 달라진 점으로 꼽는다. 요새TCO 2003 이나 2004 의 결승 문제가 SRM 에서 출제된다면 200 명 이상이 풀수 있을 것이라 한다. 그는 문제 출제자로서 누군가가 자신이 만든 문제가 정말 좋다고 칭찬할 때가 가장 즐겁다고 한다. 자신이 만든 문제중 가장 기억에 남는 문제로 TakeBus 를 꼽는다. Olexiy 는 현재 TopCoder 의 스탭으로 일하고 있다.

Rustyoldman 은 TopCoder에서 가장 나이가 많은 코더 중 한 명일 것이다. (자기 나이가 154 세라고 구라를 치고 있지만. 그의 진짜 나이는 아무도 모른다... 40 은 훌쩍 넘겼을 거고 50 이 넘었을 수도 있음.. ) 자신의 업무와 잠을 빼고는 SRM 이 자신의 생활에서 가장 중요한 일 중 하나라고 말한다. 하지만 흥미롭게도 그는 거의 연습은 하지 않는다 한다.

John.de.Ruiter 는 SRM 이 일종의 중독성이 있다고 말한다. 또한 그는 "나의 rating 은 나의 아이덴티티의 일부가 되었다" 는 표현을 쓴다. 많은 TopCoder 멤버들이 이렇게 느낄 것이다. 

사실, TopCoder 의 Algorithm Rating 이 나의 프로그래밍 실력을 정의한다고 생각하지는 않는다. 하지만 대회 환경이라는 압박감이 있는 제한된 환경에서 문제를 푸는 능력은 개발자로서 나의 아이덴티티의 중요한 부분이라고 생각한다.   

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

앞서 포스팅 한 "뉴욕의 프로그래머" 라는 책에서 언급하고 있는 이야기 중 하나이다. 
원래 이것은 조수아 블로흐( Joshua Bloch ) 라는 유명한 소프트웨어 엔지니어가 구글랩 블로그에 올린 글에서 유래하는 이야기이다.  조수아 블로흐는 자바 플랫폼의 유명한 개발자이자 Effective Java (2001년 Jolt Award 수상작)  의 저자이기도 하다. 현재 구글에서 자바 아키텍트로 근무중.

글의 원문 : Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken

저자가 카네기멜론 대학의 박사과정에 입학해서, 알고리즘 수업을 듣던 첫날, 존 벤틀리 교수 (Jon Bentley, Programming Pearl 의 저자, 국내에는 "생각하는 프로그래밍" 이란 책으로 번역. ) 가 학생들에서 이진검색을 구현해 보라고 시킨 후에 그중 몇명을 앞에 나와서 발표하라고 했을 때의 충격을 아직도 기억하고 있다고 쓰고 있다. 물론, 당연하게도 ^^, 대부분의 학생들이 구현한 이진검색은 버그가 있었다.

문제는 자바 라이브러리에 기본으로 포함되어 있던 이진검색 조차도 버그가 숨어있었다는 것이다. 아래 글을 읽어보면 왜 20 여년간이나 이 버그가 쉽게 발견되지 않았는지에 대한 설명이 있다. 수십년간 사람들이 아무 문제없이 써오던 대중적인 라이브러리에도 이와같이 숨어있는 버그를 지적하면서 Bug-Free 소프트웨어가 얼마나 힘든 것인지를 말하고 있다.

최근까지 Java.util.Arrays 에 포함되어 기본 라이브러리로 제공되던 바이너리 서치의 코드는 아래와 같다.

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

Chinese, Russian teams take top spots
중국과 러시아 팀이 상위권을 차지

Students from Shanghai Jiaotong University have been named the 2010 ACM International Collegiate Programming Contest (ICPC) World Champions. Moscow State University, National Taiwan University, and Taras Shevchenko Kiev National University followed in the second, third and fourth ranked positions, with all four teams being honored with Gold status recognition. 

상해교통대 학생들이 2010 ACM International Collegiate Programming Contest (ICPC; 세계대학생 프로그래밍 경시대회) 에서 세계챔피언이 되었다. 모스크바 주립 대학, 대만국립대, Taras Schevchenko 키에프 국립 대학이 그 뒤를 이었으며, 이상 네 팀이 금메달을 수여받았다.

                                                                     우승 : Shanghai Jiaotong University.
 

The competition, sponsored by IBM, took place February 1 to 6 at Harbin Engineering University in Harbin, China. 

IBM 이 후원하는 이 대회는 2월 1일부터 6일까지 중국 하얼빈 공대에서 개최되었다.

Referred to as "The Battle of the Brains," the ACM ICPC World Finals challenged the world's top 103 university teams to use open standard technology in designing software that solves real-world problems. Each team of three students faced 11 problems of varying levels of difficulty. The contest problems were modeled after real-world issues such as developing programs which will predict where rain water from tsunamis and hurricanes will accumulate. In five short hours, students solved more than a semester's worth of computer programming material. 

"두뇌의 전투" 로 불리는 ACM ICPC 세계 결선은 전세계 103 개 대학의 팀이 실 세계와 관련된 문제를 해결하는 능력을 겨루었다. 3명의 학생으로 구성된 각 팀은 다양한 난이도의 11개 문제를 풀어야 한다. 대회에 출제된 문제는 실 세계에서 벌어진 이슈들과 관련된 문제 - 예를 들면 쓰나미와 허리케인의 강우량을 예측하는 문제 - 들을 푼다. 5 시간의 짧은 대회 시간 동안 학생들은 학기중에서 배운 컴퓨터 프로그래밍 교재에 나오는 것 이상의 문제를 해결해야 한다.

Learn more about the 2010 ACM ICPC and all of the team rankings.

- Official Final Standing  (출처 : algospot.com)

파란색은 한국인 학생이 포함된 팀.
붉은색은 한국팀.

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

Announcing the winner and champion of Google Code Jam 2009: China's Lou TianCheng, *ACRush*!  He takes home $5,000 and the title of Code Jam champion!

In second place came China's Qi ZiChao (*qizichao*); and our third-place finisher was Japan's Iwata Yoichi (*wata*).

ACRush (칭화대 3학년) 는 2008 년 대회에 이어 2009 년 GCJ 까지 2 년 연속 우승이다.
올해 ACM-ICPC 세계 결선에서 2 등에 그친 한을 여기서 푸는가 -_-;
문제는 결승전 스코어. 2위에 비해 거의 더블 스코어로 완전히 Dominate 한 모습을 보여줬다. ㄷㄷㄷ

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

제 9회 대학생 프로그래밍 경시대회와 함께 열린, 2009 ACM-ICPC Asia Regional Contest - Seoul 대회 결과가 나왔다.
 
출처 : http://acm.kaist.ac.kr





Result

Honorable Mentions

제 9회 대학생 프로그래밍 경시대회 수상 결과 ( 출처  : algospot.com )

NHN 특별상

KAIST -  Royal Roader

서울대 - srand()

동상

전북대 - AL++

인하대 - I Sell Fish

경북대 - Effective ACM

광운대 - No-Name

은상

고려대 - Yuna_Kim

서강대 - SNSD

숭실대 - SCCC.BM

금상

포항공대 - POSCAT@POSTECH

서울대 - rand()

대상

KAIST - Nondeterminist!

2003 년 이후 우승을 못하던 KAIST 가 6 년만에 다시 우승을 차지하면서, 서울대의 최근 3 년 연속우승에 종지부를 찍었다. 개인적으로는 Royal Roader 를 우승후보로 꼽았었는데. 4 시간이 지날때까지 Royal Roader가 1위를 차지하다가 막판에 순위가 뒤집혀버렸다. ㅋ

대회 수준은 꾸준히 향상되고 있고 참가팀들의 수준도 점점 상향평준화되는 느낌이지만, 서울대와 KAIST 의 아성은 여전히 굳건하다... ICPC 서울대회 10년간 2005년에 중국팀이 한번 우승한 것 빼고는 저 두 학교가 번갈아가며 우승을 해 왓는데, 이게 언제까지 이어질지 관심사다. 그나저나 올해는 넥슨이 스폰서에서 빠지면서 수상팀도 줄었다. 스폰서쉽이 더 늘어나야 할 판에 줄어들다니... 이것도 경제위기의 여파인가.

링크

2009 ACM ICPC KAIST 1등
ACM-ICPC 참가후기 (이현섭 작성)
제 9회 대학생 프로그래밍 경시대회 은상

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

얼마전 글에서 국내 Online Judge 가 별로 없다고 한탄하는 글을 썼지만...
최근에 우연히 알게 된 국내 Online Judge 2개...

http://www.dovelet.com 

디자인이나 구성이 개인 사이트틱 하지만 문제 분류등은 상당히 잘 되어 있고 난이도 별로 문제가 배치되어 매우 교육적인 느낌이 풀풀 풍기는 사이트. 전체적으로 USACO 를 많이 참고하여 제작한 듯.
문제들이 모두 한글로 되어 있어서 KOI 준비하는 학생들에게 상당히 좋아 보임.
문제별 카테고리를 나누어 놓고 이를 총 30 단계로 분류하고 중간마다 알고리즘 튜토리얼 문서가 있는 형식은 USACO 와 매우 유사.
전체적으로 쉬운 문제들이 많아 보이기는 하지만... 수록된 문제 갯수도 수백문제는 되어 보인다.
제출 시 각 테스트테이스별 성공 여부를 보여주고 실패한 테스트 케이스를 보여주는 방식 역시 USACO 와 동일.
C/C++/Java 지원

http://hello-world.co.kr

이 사이트의 장점은 다른 Online Judge 에서 볼수 없는 풍부한 언어지원.
C/C++/Java/Pyhon/C#/PHP/Perl/Visual Basic 까지 지원된다!
특히 기존의 다른 Online judge 에서 구할 수 없었던 ICPC 서울 대회의 온라인 예선 문제가 여럿 수록되어 있어서 좋았다.
( 안타깝게도 예선 문제들 중에서도 비교적 쉽고 해법이 잘 알려진 문제들만 있다. 운영자가 자기가 풀어본 문제만 올린 것일지도...  -0-;; )
수록된 전체 문제 숫자가 이 글을 쓰는 현재 54 문제밖에 안될 정도로 너무 적고, 최근에 사이트 업데이트가 잘 안되고 있다는 점이 단점.

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

Code Jam is back!

We're excited to announce Google Code Jam 2009, this year's iteration of
Google's annual programming competition, which offers coders from around the
world an opportunity to solve complex algorithmic problems under time
pressure, using the programming languages and tools of their choice.
The contest will have a new format this year, starting with online rounds
and ending in a 25-person final in our Mountain View, California
headquarters. We're still choosing exact times for everything, but for
planning purposes we wanted to give you this tentative schedule. Please note
that the timing may change:

Early-Mid August: Registration will open.
+4 Weeks: Qualification round
+1 Week: Rounds 1A, 1B, 1C
+1 Week: Round 2
+1 Week: Round 3
November: World Finals in Mountain View

Online rounds begin soon, so start practicing!

The Google Code Jam Team
http://code.google.com/codejam

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

미국발 금융위기로 시작된 경제 불황은 전 세계적으로 영향을 주고 있다.

내 주위 사람들과 주위 환경도 이래 저래 직,간접적으로 불황의 영향을 받고 있는데, 그 중 하나가 바로 TopCoder 이다. ( TopCoder 소개는 여기... )

여러가지로 드러나는 정황을 볼 때, 최근 수년간 급성장하던 TopCoder 역시 많이 어려운 시기를 맞고 있는 것으로 보인다.

우선, Member Referral Bonus 서비스가 TopCoder Studio 를 제외하고는 모두 종료되었다.

As of December 5, 2008, the referral program will award commission based on the winnings of new members of TopCoder Studio only. TopCoder will honor all commission payments due based on non-Studio referrals made before 12/5/08.

또한, 2009 년도 일정이 공개되었는데, SRM 은 기존의 1 주당 1회 열리던 것이 2 주당 1 회씩 열리게 되어있고,  TopCoder Business 의 핵심이라 할 수 있는  Design and Development 는 아예 일정도 나오지 않았다. 물론 계속 열리기야 하겠지만... 2009 년이 1 주일도 채 남지 않았는데 아직 일정조차 확정되지 않았다는 것이 충격이다.

여기에 대해서 여러가지로 많은 논란이 있는데...

SRM 에 참가하기 위해 참가비를 받자는 의견도 있고...

호스팅 비용에 보태기 위해 TopCoder 에 구글 애드센스를 달자는 좀 유치한 의견도 있었다.. -0-

개인적으로는 여러모로 많이 아쉽다. 원래 취지에 비추어 볼 때 SRM 에서 참가비를 받는 것은 옳지 않은듯 하고, 참가비를 받자는 것에 대해 여러 회원들의 반발도 만만치않다. SRM 을 자주 여는 것이 어느정도의 예산이 필요한지는 잘 모르겠지만... 다른 형태의 지출을 절감하더라도 SRM 을 비롯한 여러 이벤트들을 자주 여는 것이 좋지 않나 하는 생각도 든다.

사실 약간은 이해가 안가는 것이 아마 예산에서 가장 크게 차지하는 비용이 호스팅 비용일텐데... 서버는 항시 돌아가고 있을테니 호스팅 비용은 고정적일텐데 SRM 을 한 번 열때마다 어느정도의 추가 예산이 필요하길래 SRM 횟수까지 줄이는 건지 궁금하기도 하다.
 
어쨌든... 프로그래머들의 실력 향상과 커뮤니케이션에 지대한 공을 세우고 있는 사이트이니 만큼... 하루빨리 정상화 되기를 바랄 뿐이다. -0-;

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

풀수 있는 문제들은 최대한 풀어보자...

그런데... 다른 지역들은 대회 공식 홈페이지에 Judge Data 를 오픈한 곳들도 많은 반면...
ICPC 한국지역 대회의 기출문제들은 그런 면에서 좀 부족한듯...;;
유일하게 Judge Data 를 오픈했던 것이 2001 년...

출제되었던 문제의 테스트 데이터를 공개하지 않는 것은 혹시라도 있을 참가자들의 어필을 우려하기 때문이라고 밖에는 생각이 들지 않는데...;;; 쩝...


Taejon 2000 :

Taejon 2001 :
본선문제 PKU 1060 ~ 1092  or  ARC 2321 ~ 2328
http://acmicpc-live-archive.uva.es/nuevoportal/region.php?r=as4&year=2001
http://acm.pku.edu.cn/JudgeOnline/searchproblem?field=source&key=Taejon+2001

Taejon 2002 :
본선문제 PKU 1330 ~ 1337
http://acm.pku.edu.cn/JudgeOnline/searchproblem?field=source&key=Taejon+2002

Seoul 2003 :
본선문제 ZJU 2679 ~ 2687
2679 : http://acm.zju.edu.cn/show_problem.php?pid=2679

Seoul 2004 :
예선문제 Hello-World 44
http://www.hello-world.co.kr/?q=node/110

Seoul 2005 :
예선문제 Hello-World 41 - 43
http://www.hello-world.co.kr/?q=node/104

본선문제 TJU 2501~2510
http://acm.tju.edu.cn/toj/search_process.php?s=Asia+-+Seoul+2005

Seoul 2006 :
예선문제 Hello-World 35 - 40
http://www.hello-world.co.kr/?q=node/98

본선문제 ZJU 3131 ~ 3140
http://acm.zju.edu.cn/onlinejudge/searchProblem.do?contestId=1&titlefrom=0&authorfrom=0&sourcefrom=0&query=Seoul%202006

Seoul 2007 :
본선문제 ARC 3900~3909
http://acmicpc-live-archive.uva.es/nuevoportal/region.php?r=as4&year=2007


Seoul 2008 :


원본 출처 : wookayin.com

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

Problem Solving 의 정수론 분야 중 두 수의 최대공약수와 최소공배수를 이용한 문제들은 매우 자주 등장하는 편이다.
구하는 방법은 여러가지가 있는데...


방법 1) 소인수 분해 (Prime Factorization)
중학교 때 배우게 되는 소인수 분해를 이용한다
어떤 수의 모든 소인수를 구하는 방법은 소수구하기 알고리즘을 이용한다.

소인수분해는, a 와 b 를 소수로 나눌 수 있는 만큼 인수분해하여, 최대공약수는 두 수의 공통된 소인수들 중에서 차수가 최소인 값들의 곱이 되며, 최소공배수는 두 수의 모든 소인수들 중에서 차수가 최대인 값들의 곱이 된다.

#include <iostream> #include <algorithm> #include <vector> #include <cmath> #include <set> using namespace std; int prime[1000]; bool isprime(int n) { if( n <= 2 ) return true; if( n%2 == 0 ) return false; for( int a = 3; a*a <= n; a++ ) if( n%a == 0 ) return false; return true; } int main() { int a, b, i, n, cnt, tmp, lcm = 1, gcd = 1; vector<pair<int,int> > prime1, prime2; for( i = 2; i < 10000; i++ ) if( isprime(i) ) prime2.push_back(make_pair(i,0)); prime1 = prime2; cin >> a >> b; tmp = a, cnt = 0; while(tmp > 1) { n = prime1[cnt].first; while( tmp%n == 0 ) { tmp /= n; prime1[cnt].second++; } cnt++; } tmp = b, cnt = 0; while(tmp > 1) { n = prime2[cnt].first; while( tmp%n == 0 ) { tmp /= n; prime2[cnt].second++; } cnt++; } for( i = 0; i < prime1.size(); i++ ) { if( prime1[i].second > 0 && prime2[i].second > 0 ) { n = min( prime1[i].second, prime2[i].second ); gcd *= (int) pow((double) prime1[i].first, (double)n); } if( prime1[i].second > 0 || prime2[i].second > 0 ) { n = max( prime1[i].second, prime2[i].second ); lcm *= (int) pow((double) prime1[i].first, (double)n); } } cout << gcd << " " << lcm << endl; return 0; }
이 방법은 수학시간에 배운 직관적인 방법이고, 많은 이들에게 익숙하지만 위에서 보듯이 코딩으로 옮기기에는 꽤나 귀찮다는 단점이 있다. 또한 두 수 a, b 의 모든 소인수를 구해서 저장해 놓아야 하므로 별도의 메모리를 필요로 한다. ( 위의 코드는 10000 까지의 소인수에 대해서 구현한 코드 )


방법 2) Brute force
최대공약수의 정의를 이용하여, brute force 방법으로 직접 구한다.
즉, 두 수 a, b 를 나누어서 나머지가 0 이 되는 수들 중에서 가장 큰 숫자를 구하면 이 숫자가 최대공약수가 되며, 두 수 a, b 의 배수를 구하여 공통된 배수 중 가장 작은 숫자를 구하면 이 숫자가 최소공배수가 된다.
int main() { int a, b, i; cin >> a >> b; int n = min(a,b); int m = max(a,b); for( i = n; i >= 1; i-- ) if( a%i == 0 && b%i == 0 ) break; cout << "gcd = " << i << endl; for( i = m; i <= a*b; i++ ) if( i%a == 0 && i%b == 0 ) break; cout << "lcm = " << i << endl; return 0; }
위의 코드에서 만약 a, b 간의 공약수가 존재하지 않는 경우는 두 수의 최대공약수는 자연스럽게 1이 되며, a, b 간의 최소공배수 중 가장 클 가능성이 있는 수는 a*b 가 되므로 a*b 까지만 검사를 하면 된다.

이 방법은 최대 a*b 번의 연산을 해야 하므로,  a 와 b 가 커질수록 수행시간이 급격히 늘어난다.


방법 3) Euclid's algorithm - Using Recursion
사실 최대공약수와 최소공배수를 구하는 것은 고대 그리스의 수학자, 유클리드가 고안한 "유클리드 알고리즘"(Euclid's algorithm) 을 쓰면 간결하게 해결할 수 있다. 이 방법은 The Art Of Computer Programming 의 제 1장에도 소개된 바 있다.
a, b 중 큰 수를 a, 작은 수를 b 라 하자. 이 두 수의 최대공약수를 구하려면 a 를 b 로 나눈다. 이 연산을 한 후에 b 와 a%b 를 갖고 어느 한쪽이 0 이 될때까지 이 과정을 계속 반복한다. a%b 가 0 이 될 때의 b 가 바로 최대공약수가 된다. 이를 코드로 옮기면 다음과 같다.
int recursion(int a, int b) { if ( a%b == 0 ) return b; else return recursion(b, a%b); } int main() { int a, b; cin >> a >> b; int gcd = recursion(a,b); cout << "gcd = " << gcd << endl; cout << "lcm = " << (a*b)/gcd << endl; return 0; }

최대공약수와 최소공배수의 성질을 이용하면 아래와 같이
최소공배수 = (a*b) / 최대공약수
최대공약수 = (a*b) / 최소공배수
가 되므로, 최대공약수나 최소공배수 둘 중 하나만 구하면 나머지 하나는 쉽게 구할 수 있다.


방법 4) Euclid's algorithm - Using Iteration
방법 3 은 매우 간결한 코딩이 가능하지만, 재귀호출을 이용한다는 단점이 있다. 재귀호출은 상당히 비싼 작업이므로 이를 좀더 효율적인 iteration 버전으로 바꿀 수 있다. 실제로 방법 3은 a, b 가 매우 큰 서로소일 경우 답을 얻는데 꽤 오랜 시간이 걸리게 된다.
int gcd(int a, int b) { int tmp; while( b ) { tmp = a; a = b; b = tmp%b; } return a; } int main() { int a, b, g; cin >> a >> b; g = gcd(a,b); cout << "gcd = " << g << endl; cout << "lcm = " << (a*b)/g << endl; return 0; }


방법 5) Euclid's algorithm - Using Iteration, Original Version
유클리드가 처음 이 알고리즘을 제안했을때 사실은 modular 연산을 사용하지 않고, 아래와 같이 뺄셈 연산을 이용했다 한다.
int gcd(int a, int b) { if( a == 0 ) return b; while( b ) { if( a > b ) a = a-b; else b = b-a; } return a; } int main() { int a, b, g; cin >> a >> b; g = gcd(a,b); cout << "gcd = " << g << endl; cout << "lcm = " << (a*b)/g << endl; return 0; }  
방법5 는 방법 4와 비교하여, tmp 변수를 사용하지 않아도 되므로 메모리를 약간 절약한다는 장점이 잇다 ^^

유클리드 알고리즘의 증명 = 자세한 설명은 생략한다 Wikipedia 참고
유클리드 알고리즘의 시간복잡도 = O(n^2), n = length of integer bits, 그 이유는 n-bit 숫자 나눗셈 연산의 시간복잡도가 O(n(m+1)) 이기 때문이다 ( m 은 몫의 길이 )

3개 이상의 수에 대해 최소공배수와 최대공약수를 구할 때는, 두 수의 최소공배수와 최대공약수를 구한 후, 이 수와 나머지 수들에 대해 최소공배수와 최대공약수를 구하면 된다.

유클리드 알고리즘을 처음 보았을 때 무릎을 쳤던 기억이 난다. 그래서 최대공약수와 최소공배수에 대해서 글을 반드시 함 써보려 했는데... 위키피디아에 유클리드 알고리즘이 깔끔하고 멋지게 정리가 되어 있었다 ㅋ

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

ACM-ICPC 국내예선 대회를 일주일 앞둔 지난 9월 20일,
모교에서는 교내 프로그래밍 경시대회가 열렸다.

작년도 교내 프로그래밍 경시대회 포스팅

금년도 교내대회 출전팀 숫자는 총 67 팀 ( 참가자 숫자 3*67 = 201 명 ). 작년보다는 약간 줄기는 했지만 여전히 국내 최대 규모로 치루어졌다. 작년에는 교내대회 상위 2팀 + 국내예선 상위 2 팀을 해외대회에 파견하였는데, 그렇게 하다보니 서울대회는 참가하지 않는 팀이 ( 물론 대학원 면접, 회사 면접 등이 겹치는 어쩔수 없는 사정들이 있었다고는 하나... ) 해외대회만 출전하는 상황이 생기면서 문제가 되었던 것 같다.

실제로, 이런 이유로 서울대회에서도 올해는 "참가확인" 을 받으면서 대회불참팀이 생기지 않도록 규정을 새로 만든 모양이다.

관련글 보러가기

그래서 올해의 교내대회는, 국내예선에 출전하는 상위 30 개팀을 선발하는 목적으로 치뤄지며 ( 물론 교내대회 성적에 따른 상금 시상은 있다 ), 해외대회 파견팀은 국내예선 상위 4 개팀만을 파견하기로 결정되었다.

나는 작년에 이어 올해도 교내대회 문제출제자 겸 심사위원으로 참관했다. 아주 재미있는 경험이었다. ^^

Canon | Canon EOS 40D | Normal program | Pattern | 1/60sec | F/4.0 | 0.00 EV | 17.0mm | ISO-400 | Flash fired, compulsory flash mode

이곳이 바로 Judge Room 이다. 교수님 외에 6 명이 Judge 로 수고했다.

Canon | Canon EOS 40D | Normal program | Pattern | 1/60sec | F/4.0 | 0.00 EV | 17.0mm | ISO-400 | Flash fired, compulsory flash mode

대회 오리엔테이션. 올해는 학장님도 오시고 해서 작년보다 좀 더 격식을 갖췄다고 할까.

NIKON CORPORATION | NIKON D200 | Manual | Pattern | 1/30sec | F/4.5 | 0.00 EV | 28.0mm | ISO-400 | Flash did not fire

Judge 룸 상황. 실제 대회가 시작되면 Judge 들도 대회 치루는 것 처럼 정신이 없다. Judge 들은 각자 자신들이 출제한 문제에 대해 judge 를 맡게 되는데, A, B 번을 맡은 사람들은 대회 시작부터 끝까지 아주 죽어난다. -0- 반면 G, H 를 맡은 사람들은 할일이 없어서 심심하게 보내게 된다. ㅋㅋ 나는 적당히 바쁜 D 번 문제에 대한 출제 및 심사를 맡았다.

Canon | Canon EOS 40D | Normal program | Pattern | 1/60sec | F/5.0 | 0.00 EV | 17.0mm | ISO-400 | Flash fired, compulsory flash mode

올해는 ACM-ICPC 서울대회와 비슷하게 격식을 갖춰, 티셔츠 까지 제작해서 나눠줬다. 그 외에 대회시간 내내 간단한 다과가 제공...
사실 참가자와 스탭들이 티셔츠를 입으니 여러가지로 대회 운영상 편리한 점이 많았다. 대회 참가자와 스탭을 쉽게 구분할 수 있고, 대회 운영 중 통제도 더 쉬워진다. 앞으로는 매년 이렇게 티셔츠 제작도 하게 될 것 같다.

Canon | Canon EOS 40D | Normal program | Pattern | 1/80sec | F/5.6 | 0.00 EV | 17.0mm | ISO-400 | Flash fired, compulsory flash mode

실제 대회 시간 중...

Canon | Canon EOS 40D | Normal program | Pattern | 1/60sec | F/4.0 | 0.00 EV | 17.0mm | ISO-400 | Flash fired, compulsory flash mode

대회 종료 후, 시상식 장면.
이 팀이 1위 팀인데, 문제해결 수업 때 매우 두각을 나타냈던 친구들이라 한다.

그런데 아쉬운 것은, 정작 국내예선에서는 이 교내대회 1 위팀이 2 문제에 그치면서 서울대회 출전이 좌절 된 것 -0-;

개인적으로도 매우 재미있는 시간이었다.

problemset.pdf

교내대회 출제문제

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.