티스토리 뷰

etc.

ACM ICPC Daejeon / 한국 대학생 프로그래밍 경시대회 후기

킹갓제네럴충무공 박트리 2017.11.13 01:05

1년을 마무리하는 마지막 대회 한국 대학생 프로그래밍 경시대회 본선에 참가했다.

11.10 - 11.11 이틀에 거쳐서 카이스트 문지캠퍼스에서 진행 되었다.


올해는 같은 산업공학과 학부생인 동기들과 함께 나갔다.  DDiyoooooong [baactreew3109ww, grands]

PS분야를 많이 공부한 친구들은 아니지만 기본적인 코딩능력이 뛰어나고, 창의적인 생각이나

아이디어를 도출하는 부분도 뛰어난 친구들이다. 

3명 모두 삼성 S/W 역량평가 B형까지 통과하였다.


10일날 오전에 광주버스터미널에서 모여서 버스를 타고 대전청사로 갔다.

홈플러스에서 찜닭을 먹었는데 옆자리가 NCTU 팀이었다. ㅋㅋㅋ

점심먹고 카이스트로 출발했다.


등록을 마치고 잠시 대기했다가 연습세션이 시작되었다.

작년에도 icpc를 했던 경험이 있던 내가 이제 대회가 시작되었을 때 이미지 트레이닝 같은걸 팀원들에게 해줬다.

do not touch anything 100번은 들을것이고 시작하면 모니터랑 키보드를 오른쪽으로 옮기고 IDE 환경 세팅이랑

대회 사이트 로그인 후 스코어보드를 열어 놓으라는 등등의 스케치를 그려줬다.

우분투 환경에서 서브라임 사용법이랑 터미널 사용법 간단한 것들 설명해주고 출력하는 법 등등도 설명해줬다.


예비소집을 끝내고 숙소로 돌아와서 저녁은 불고기와 곱창을 야무지게 구워먹었다.

숙소에서 과자와 캔맥주를 마시면서 화이팅을 외치고 다시보기로 영화 앤트맨을 보고 일찍 잤다.


드디어 icpc 당일! 등록하고 대회장으로 입장했다.

do not touch anything 100번쯤 들을 것 같았는데 생각보다 몇 번 안하시더라...

대회는 5분 지연되어 10:05분에 시작되었다.


징이 울리고 대회가 시작되었다.

나는 H,I,J,K,L 문제를 가지고 있었고 대충 그림들을 보면서 뭘 읽을까 하다가 K가 왠지 작년 로봇 문제처럼

단순 시뮬레이션같아서 먼저 읽었다. 읽고나니 그런 문제가 아님을 깨달았고, 그 후 H를 읽었다. 

H 문제를 보고 그냥 생긴게 FFT같이 생겼었다. 하지만 R,S,P를 각각 어떤 정수에 대해 매칭해야될지 바로 떠오르지 않았고

좀 더 고민하다가 문자열 매칭으로 될거 같다는 생각이 들어 KMP를 구현했다.

하지만 이게 매칭이 앞부터 순서대로 다 맞아야 하는게 아니라

그냥 이긴 횟수를 세는 문제라 접근이 틀렸음을 깨달았고, 접은 다음에 스코어보드를 보니 D가 엄청나게 풀려있었다.


D문제를 팀원에게 받아서 호다닥 읽어보니 단순하게 사이클체크를 하는 문제였고 구현하고 AC를 받았다. [12분 AC]

다시 스코어보드를 보니 C가 풀려 있었고 C를 읽었다. 정말 읽기 싫게 생긴 문제 형태였는데 꼼꼼히 읽어보니 DAG가 성립했고 

따라서 동적계획법으로 해결할 수 있었다. [42분 AC]

다음으로 잡은 문제는 F였다. 팀원이 읽고 있던 문제여서 문제 설명을 듣고 단순하게 재귀함수로 해결가능 할 것 같았는데

구현을 어떻게 단순하게 해야 할지 감이 잘 안잡혔다.

그래서 그냥 16가지 경우에 대해서 하드코딩했고 AC를 받았다. [74분 AC]


이후 H를 더 고민하는데 가지수가 2개만 있으면 0과 1로 치환하면 되는데 3가지라 어떻게 하지 고민하다가

팀원이 그럼 3번해보면 되지 않냐고 했고 코딩하는데 뜬금없이 스코어보드가 프리징 됐다ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

대회 시작 2시간만에 스코어보드 프리징이라니 저어어엉말 놀랍다ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

몰라몰라가 11솔브 acg가 10솔브 어마어마 했다ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ


당황하지 않고 h를 코딩을 마쳤는데 이게 끝내는 것을 딱 맞게 안 끝내도 되는거 였는데 그걸 캐치하는데 좀 걸려서

10-20분 정도 시간을 허비했다. 이후 고치고 AC를 받았다. [127분 AC]

 

이제 쉬운문제는 다 해결되었다고 생각했고 어떤걸 풀어볼까 고민하면서 팀원들과 읽은 문제들을 체크하고 공유하였다.

A, B, G, I를 읽었고 A, B는 심플하지만 해결한 팀이 많이 없는걸로 봐서 일단 미뤘고 G와 I를 해결하고자 했다.

일단 팀원이 B를 백트래킹으로 비비면 될 것 같다고 해서 컴퓨터를 넘겨 줬고 나는 I를 고민했다.

사실 F를 코딩하면서 I의 설명을 들었을 때는 사이클 찾는 문제여서 토끼와 거북이 알고리즘을 사용하는건가?

라고 생각했었는데 다시 생각해보니 아니었고 pi함수를 이용해서 풀 수 있을 것 같았다

팀원은 B의 코딩을 끝냈지만 예제가 나오지 않았고 코드를 출력한 뒤 내가 컴퓨터를 잡았다..

주어진 문자열을 뒤집고 pi함수를 만들어서 각 인덱스당 최소 반복 길이를 구하면 됐었는데 처음에 반복 구간을

찾은 다음에 이 구간을 줄이기 위해서 다시 반복 구간을 찾을 때 약수에 대해서만 찾았어야 했는데, 이걸 빠르게

생각하지 못해서 5번 WA를 맞은 후 AC를 받았다. [238분 AC]
 

다음으로 K에 대해서 계속 정리해 둔 걸 바탕으로 현재까지 만든 bounding box 보다 더 크게 길이를 설정하면

항상 주어진 조건을 만족 시킬 수 있고 길이도 n을 넘지 않는다는걸 깨달았고 그대로 구현하고 AC를 받았다. [253분 AC]


이제 대회가 1시간 가량 남아있는 상황에서 솔루션이 뚜렷하게 보이는건 G와 B였고, 현재 6문제를 해결한 상황이었다.

내가 B를 생각하고 G를 팀원에게 플레인 스위핑 + a 일 것 같다라고 한 뒤 다시 고민했다.

B를 3진법으로 비트마스크하는 dp라고 생각했고, 구현했는데 답이 안 나왔다. 30분쯤 남은 상황에서 팀원에게

컴퓨터를 넘겨주고 디버깅을 했다. 

하지만 틀린 부분을 못 찾았고, G도 남은 시간내에 완성을 못하고 대회가 종료되었다. 



최종적으로 6문제를 해결하였고 시상식 결과 학교순위 9등으로 동상을 수상하였다. 와~와~


개인적인 이번 icpc 성과를 분석해보자면 처음 쉬운 문제를 찾는데 약간 선택이 어긋났었고, F를 좀더 깔금한 구현법이

있을 것 같은데 떠올리지 못해서 코딩시간을 쓴 게 아쉽다.

그리고 H를 맞추고 I를 맞출 때까지 2시간 정도가 걸렸는데 사실 I문제가 풀어봤었던 유형이었는데 그걸 빠르게 생각하지

못하고 5번이나 WA를 맞은게 너무 컷던것 같다.

처음에 토끼와 거북이 알고리즘이라고 생각을 거의 확정시켜버려서 그 알고리즘을 기억하는데 시간을 좀 투자했는데

뚜렷한 솔루션이 안보일 때에는 계속 다른 방향의 접근 방법을 생각하는 습관을 가져야 할 것 같다.

여기서 한시간 반정도만 단축시켰어도 9 - 10 솔브는 할 수 있지 않았을까 싶다.


B는 내가 생각한 알고리즘이 잘못 됐었고 백트래킹이 맞았었다. 그냥 백트래킹으로 구현했다면 좋았을 텐데 시간의 압박에

알고리즘의 정당성을 명확하게 파악하지 않고 코딩한게 실수 였던것 같다.

G같은 경우도 코딩량이 꽤 있어야해서 컴퓨터를 놀리지 않고 꾸준히 돌렸어야 했는데

팀원들중 구현력이 되는사람이 나밖에 없어서 그것도 너무 아쉬웠다.


이번 대회에서 AC를 맞은 6문제 전부다 내가 코딩하게 되었는데 아무래도 구현을 내가하게 되니 내가 생각하는 시간도

부족해지고 디버깅하는데도 시간을 투자해야되서 문제 순환이 제대로 이루어지지 않았던 것 같다.


아직 내년대회도 또 참가할지 안할지는 미지수이지만 다시 참가하게 된다면 2명정도는 구현력을 충분히 늘리고

많은 문제를 읽고 서로 심플하게 설명해주면서 계속 문제를 돌리고 아이디어 정리하고 빠르게 구현하는 식으로하면

좋은 성적을 낼 수 있을 것 같다.


올해 대회 재미있게 잘 치뤘고 5시간 내내 즐기면서 했던거 같다. 팀명만 20번은 외친거같다. ㅋㅋㅋㅋㅋㅋㅋㅋ

목표는 은상이었지만 그래도 동상 턱걸이로 걸쳐서 기분이 좋고

스코어보드 공개 전까지는 동상도 못 받을것 같았는데 다행이다ㅋㅋㅋㅋㅋ


PS를 시작하고 나서 받는 첫 수상이어서 너무 기분이 좋고 왠지 이 분야를 더 해보고 싶은 생각이 들었다.

외쳐어어 띠요오오오오오오오옹~

댓글
댓글쓰기 폼