ACM_ICPC 2016 후기

[이민석], [정진경], [홍성현]

https://docs.google.com/document/d/1-d-yv20PJ9UYaibZUk9oq7jg5y7TrMzhHUJ3Z7EgN_A/edit

''''ACM-ICPC 대회 참여를 고민하는 사람에게''''

'''대회 준비가 현실적으로 도움이 되는지?'''

JG: 도움이 되는 요소를 2가지로 나누자면 소위 스펙이라는 외재적 요소와 코딩 능력이라는 내재적 요소로 나뉜다고 생각하는데, 정말로 쓸모있는 스펙이 되려면 아주 많은 노력을 들여야 할 지도 모릅니다. 다만 제가 강조하고 싶은 부분은 대회에서 입상을 하지 못하더라도 준비 과정에서 얻게 되는 코딩 능력이 꽤나 유익하다고 판단합니다. 여러 IT 기업들이 ACM-ICPC 방식의 문제를 이용해서 입사 문제 등을 활용하고 있기도 하기에 취업 준비에도 직접적인 도움이 될 가능성도 있습니다. 다만 현업에서의 실무는 분야에 따라 요구되는 능력이 다양합니다. 대용량 코드 유지보수, 동시성 처리, 호환성 이슈 등 소프트웨어 개발에는 다양한 이슈가 존재하는데 ACM-ICPC가 그런 이슈들을 모두 다루지 않습니다.

대회를 준비한다면 조언하고 싶은 것들
JG: 못 푸는 문제 끈질기게 풀어보는 연습 필요. 코드잼, 해커컵, 코더스 하이, UCPC, SCPC 등 나갈 수 있는 대회는 다 나가볼 것. 알고스팟, 백준 등 커뮤니티 참여해서 모르는 것 질문할 수 있는 창구 늘리고, 좋은 포스팅 등 있으면 공유 받기. 코드포스나 탑코더 등 콘테스트 해볼 것. 이미 한 번 푼 문제의 코드를 발전시켜 볼 것.

동기부여
JG: 공부를 더 해보고 대회에 출전한다는 생각 버렸으면 함(경험상 이 핑계가 가장 많은 것 같다). 실력을 드러내지 않으면 성장할 기회를 하나 잃어버린 것. 본인은 원고리즘 B학점임. 용기를 가지셈.

SH: 대회로 입상하면 상금도 받고, 상장도 생각보다 가산점으로 혜택을 보게 됩니다. 온라인 저지에서 문제를 풀거나 콘테스트 참가해서 랭킹 올리는 재미도 있으니 취미 생활로 해도 좋습니다.

'''''ACM-ICPC 썰'''''

팀 개개인의 실력이 너무나도 출중해 그냥 가도 올 솔브 → 이 문서를 볼 필요가 없다
대회 5시간 안에 최대한의 퍼포먼스를 발휘하려면?

'''공부 자료'''

남이 공부했던 자료 어차피 안 봄
알아서 공부하세요
알고리즘 문제 풀이 책, 온라인 저지 애용

'''인터넷 예선'''

문제 유형
온라인 competitive programming 콘테스트들은 기형적인 문제들이 많아
ACM-ICPC는 전형적인 문제로 구성 (주지스피셜)

대회 환경(DOM Judge)에서 가능한 것 테스트해보기
메모리를 이만큼 잡으면 터지나?
이 연산이 저지 시스템에서 속도가 얼마나 걸리나?
재귀 함수를 얼마나 호출하면 스택이 터지는가?

예선 문제들이 본선에도 비슷하게 나온다
예선에서 네트워크 플로우 문제 → 본선에도 네트워크 플로우 문제 나옴
예선에서 inch worm 문제 → 본선에도 inch worm 문제 나옴

대회와 비슷한 환경에서 예습
코드포스 같은 데서 다 같이 버츄얼 콘테스트 돌려보기
셋이 5시간 동안 남의 나라 리저널에 버츄얼 콘테스트
ㄴ 여건이 힘들더라도 이거 한 번이라도 하는 거 추천


'''팀노트 준비'''

알고리즘은 아는데 코딩하기 귀찮은 것 / 까먹을 위험이 있는 것 / 못 외울 것
ex) 네트워크 플로우, 벨만-포드, 펜윅 트리

모르는 거 적어가봐야 못 품

팀노트 만들면서 배웠던 거 총정리하는 느낌

'''대회할 때'''

시간 분배
5시간 동안 12문제(문제 수는 변할 수 있습니다)

문제 푸는 순서
다 훑어보고 문제 분류하기 (이건 DP, 저건 그리디, 요건 네트워크 플로우…)
잘못 분류하면 뭐… 읽은 사람 탓
쉬운 것부터
초반에는 문제를 읽고 바로 코딩 가능한 것들이 있음. 이런 문제들을 찾아서 바로 풀고, 옆 사람은 종이에 손 코딩이라도 하면서 다른 문제를 풀거나 풀고 있는 문제들 테스트 케이스를 만듭시다.
테스트 케이스는 간단하게 통과 가능한 것 부터, 생각할 수 있는 에러들을 넣어가며 해보는 것이 바람직합니다.(ex> 전체 범위가 음수~양수이면, (음수~음수), (음수~양수), (양수~양수), (음수~0), (0~양수) 등등 가급적 여러 조합들을 다 해보는 것을 추천.)
C++ 같은 경우 ifdef를 사용해서 만들어 둔 테스트 케이스 txt 파일로 redirect 시키는 것도 좋아요.
어차피 올 솔브 못하니까 못 풀 것 같은 문제를 오래 붙잡는 것 보다 코딩 문제들 촤라락 풀고 한 문제에 대해 두 명 이상씩 붙어서 토의하면서 풀면 좋습니다.(페어 프로그래밍 하면 좋아요) 
클린 코드를 지향합시다. 다른 사람이 코드 보기도 더 수월하고, 디버깅도 더 수월하고 실수할 소지도 줄어듭니다.(STL 사용에 익숙해 집시다)

페어프로그래밍, 세 명이 한조

A: 이거… 이진 탐색인가?
B: 이러이러한 특정 구간을 이진 탐색으로 찾아보자.
A: 아니 그거 이진 탐색으로 안됨. inch worm으로 구해봐.
C: ㅇㅋ 그거 내가 코딩함 (실패)
C: 어... 입력이 음수일 때 특수 처리해야 해.
A: (옆에서 보다가) 님 그렇게 고치는 거 맞음?
최종 통과

모르면 아예 못 푸는 문제
convex hull이 뭔지 모르는데 해법을 생각해보니 convex hull이 필요 → convex hull 알고리즘을 30분 안에 생각해내서 풀기 가능?(실제로 convex hull을 열심히 외워 갔지만 convex hull로 풀리는 것인지 몰라서 손도 못 댔어요. 기본적인 알고리즘 베이스는 당연히 중요하고 어떻게 적용되고 응용되는지 많은 문제를 풀면서 감을 키워야 합니다)

아이디어가 필요한 문제
알고리즘도 알고 기막힌 아이디어도 필요한 문제

'''리눅스'''

저 비주얼 스튜디오만 써봤는데요?
리눅스 터미널에 익숙해지셈
평소에 우분투에서 코딩해보기 / 윈도우즈에서 putty로 vim 열고 코딩

'''공부할 때 도움될만한 사이트들'''
http://codeforces.com/		코드포스, 온라인 콘테스트도 자주 열리고, 다양한 문제들이 수록되어 있음. 문제가 영어임. 전세계의 실력자들이 콘테스트를 통해 풀었던 문제이므로 어느 정도 검증이 됨(이상한 테스트 케이스, 오해의 소지가 있는 문장 등이 적은편[SH의 주관]). 뿐만 아니라 틀렸을 때, 틀린 테스트 케이스를 볼 수 있고, 다른 사람의 코드도 볼 수 있다는 장점이 있음.

http://59.23.27.112/		더블릿, 유료 사이트지만 제로페이저라면 제로페이지 계정을 이용하여 풀 수 있음. 단계별로 정리가 되어 있음.

https://www.acmicpc.net/	백준, 국내 저지로 실력자들에게 질문하기 수월함. 게시판에 글을 쓰거나 slack을 활용하여 질문할 수 있음. 다만 검증되지 않은 문제가 가끔씩 좀 있고, 틀리면 맞추기 전에는 왜 틀렸는지 알 수 없음. 또한, 맞추기 전에는 다른 사람 코드를 볼 수가 없음.

https://algospot.com/		알고스팟, 백준과 성격이 비슷함.

https://www.codeground.org/main.do		코드그라운드(삼성, SCPC), 삼성에서 사용하는 저지, 풀어본 적은 없지만 SCPC에 참가하기 전에는 보는 것이 좋음. 다른 컨테스트와 룰이 조금 다름(개인적으로 하는 추측이지만, TL이 각 케이스 별로 돌지 않고 전체 케이스 합산인 것 같음.)

탑코더는 이용해본 적이 없지만, 다른 곳 보다 수준이 좀 더 높다고 알고 있음.
이외에도 구글 코드잼, 페이스북 해커컵, 삼성 SCPC, 코더스 하이, 코드 첼린지 등등 많은 대회가 있는데 참가해보는 것을 권장함.