ACM_ICPC 2016 후기
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의 주관). 뿐만 아니라 틀렸을 때, 틀린 테스트 케이스를 볼 수 있고, 다른 사람의 코드도 볼 수 있다는 장점이 있음.
https://www.acmicpc.net/ 백준, 국내 저지로 실력자들에게 질문하기 수월함. 게시판에 글을 쓰거나 slack을 활용하여 질문할 수 있음. 다만 검증되지 않은 문제가 가끔씩 좀 있고, 틀리면 맞추기 전에는 왜 틀렸는지 알 수 없음. 또한, 맞추기 전에는 다른 사람 코드를 볼 수가 없음.
https://www.codeground.org/main.do 코드그라운드(삼성, SCPC), 삼성에서 사용하는 저지, 풀어본 적은 없지만 SCPC에 참가하기 전에는 보는 것이 좋음. 다른 컨테스트와 룰이 조금 다름(개인적으로 하는 추측이지만, TL이 각 케이스 별로 돌지 않고 전체 케이스 합산인 것 같음.)
탑코더는 이용해본 적이 없지만, 다른 곳 보다 수준이 좀 더 높다고 알고 있음.
이외에도 구글 코드잼, 페이스북 해커컵, 삼성 SCPC, 코더스 하이, 코드 첼린지 등등 많은 대회가 있는데 참가해보는 것을 권장함.