다섯 번째 Event - SRM 584 DIV 2

SRM이 오랫동안 열리지 않아서 아쉬웠는데, 어제 7월 들어 처음으로 SRM이 열렸다.

사실 더 자주 열었으면 좋..........겠지만, 그러면 실력이 그대로이니 레이팅이 급하게 올라가진 않겠지.

롤(LOL)에서 볼 수 있듯이, 실력이 그대로인 상태로 랭겜만 계속 해봐야 레이팅은 오르지 않는다.

2주 동안 갈고 닦아서 시험보는 게 내게 더 도움이 될 것이다.

 

 

[결과]

즐겁고 스릴넘치고 재밌는 경험이었다.

- 이지는 살짝 늦게 낸 감이 있었고, 이번엔 처음으로 Hard를 풀었다!

   - 이지 : 237.11 / 250   (6분 41초)

   - 하드 : 490.03 / 1000 (38분 43초)

- 이번엔 챌린지를 하지 않았다. 확실히 틀렸다고 집기가 어려웠기 때문.

- 결과적으로, 등수는 30 / 800 (DIV 2), 레이팅은 1040 -> 1197 으로 +157 이다.

    -> 이번 성적 상승이 지금까지 중 최고 폭이라 기쁘다~!

 

 

[과정]

이번 SRM은 시간을 잘못 봐서, 집 대신 학교에서 보게 되었다. (결과적으로는 오히려 더 잘 된 듯 하다.)

SRM 보기 전에, 저번에 써 놓았던 SRM 팁들을 미리 두세 번씩 살펴보고, 풀 계획을 준비해놓았다.

그 팁들 중에 대부분을 실천해서 좋은 결과를 거두었다.

 

지난 번에 느낀 점 대로, 이지를 풀고 나서 하드를 본 뒤, 풀만하면 풀고 아니면 미드로 넘어가는 방식을 쓰려 했다.

이지를 푸는데, 살짝 늦게 풀었다. 그 이유는, 내가 문제만 읽고 성급하게 코드를 짰는데 알고 보니 잘못 풀었다.

Example을 손으로 테스트만 해 봐도 제대로 볼 수 있는 문제였는데, 너무 성급했다.

그래서 수정하여 제대로 내고 나니 7분이나 걸렸다.

 

이후 (소스 코드를 복사해놓는 것을 깜빡하고) 이지를 닫은 뒤에, 계획대로 하드를 열었다.

하드 문제를 천천히 읽어보는데, 생각보다 어렵지 않은 것이다.

예상 외로 빠르게 해결책이 보였고, 하드를 먼저 짜기로 했다.

30분 남을 때까지 하드를 도전해서, 안 되면 미드로 갈아타기로 계획을 잡았다.

 

이항 계수(binomial coeff~)를 활용하는 문제였는데, 예전에 만들어 놓은 코드가 생각나서 활용했다.

(그런데 처음에 코드가 잘 작동하지 않아서 수정하느라 시간좀 썼다 ㅠㅠ 노트 / 라이브러리를 만들자.)

풀다 보니 저번에 ACM live archive에서 풀었던 문제와 비슷한 부분이 있어서 도움이 많이 되었다.

그렇게 풀고 테스트 해 보니 답은 잘 나오는데, 시간 제한이 걱정되었다.

최대 시간이 나올 만한 input을 걸어보니, 역시나 Fail이 떴고,

그래서 완전 탐색에 memoization을 추가하여 DP로 만들었더니 성공하였다.

 

38분이나 썼으므로, 미드 풀 시간이 얼마 남지 않아서, 테스트를 마치는 대로 급하게 submit 하긴 했지만,

급하게 푼 만큼 뭔가 맞을 것이라는 확신이 잘 들지 않았다. '제발 맞아라....' 정도의 느낌이랄까.

또 복사하는 것을 깜빡하고 Hard를 닫고, 미드를 열었다.

 

금방 풀릴 거라 생각했던 미드는, 생각보다 어려웠다.

나한테만 어려웠던 것인지, 우리 방의 많은 사람들이 풀었음에도 불구하고,

나는 알고리즘이 떠오르지를 않아서 풀지 못했다.

뭔가 그래프와 관련되어 보이긴 했으나, 그에 대한 적절한 알고리즘이 떠오르지 않았고,

또 그래프를 한 지 너무 오래되어 알고리즘들이 잘 기억나지 않는다는 것을 깨달았다. (2권 복습이 먼저일 듯)

 

그렇게 고민하다가 시간이 8분 정도 남자, 더 이상 미드를 풀 수 없다는 것을 알고

포기하고서 Hard 코드를 VS에 복사했다. 챌린지용 세트를 만들기 위해서였다.

그런데 생각보다 챌린지 셋을 만들기 어려운 문제였다. 좀 까다롭달까.

그리고 DOS모드에서 input을 100개씩 넣으려나 생각보다 시간도 걸렸다.

 

5분의 쉬는시간을 챌린지 모드 만드는데 썼지만,

챌린지 15분 동안 남의 코드들을 다 뒤적거렸음에도 챌린지 할 만한 거리를 찾지 못했다.

이지는 쉬워서인지 다들 맞게 풀었고, 하드는 나 포함 3명밖에 못 풀었으며 남의 코드 분석이 힘들었다.

미드는 내가 풀지를 못해서 챌린지 할 수가 없었다.

 

결과적으로는 미드에서 System Test Fail이 가장 많이 나왔다. 5명이 Fail.

System Test로 넘어갔는데, 테스트는 약 20분 정도 걸리니 끝났다. 제발 맞았기를 바라면서 하드를 봤더니, 통과!!!

그 때 정말 너무 기뻤다. 레이팅도 약 150이나 올랐고, DIV 2 30등을 했으니 매우 기분이 좋았다.

 

이제 DIV 2 끝자락이니, 여기서 DIV 1로 넘어갈 때 크게 '확' 뛰어올라야 높은 점수대에서 시작할 수 있다.

잘 해봐야겠다.

 

[배운 점]

- SRM 시작 전에, 꼭 이전 Tip 들을 읽자.

- SRM이 시작하기 훨씬 전에, 메모장으로 Easy, Mid, Hard 파일을 만들어두자.

   각 문제를 제출하고 난 뒤에, 문제를 닫기 전에 메모장에 복사하자. 나중에 VS에서 챌린지 셋을 만들기 위함이다.

- 이지를 풀 때, 문제만 읽고 성급하게 코딩하려하지 말고, 1~2개 Example들을 손으로 테스트해보면서

   내가 맞게 이해했는지를 확인해보자.

- 이번처럼 확실히 챌린지 할 만한 코드가 아니면 승부를 걸지 말자.

- 어느 정도 맞았다는 생각이 들 정도로 테스트가 되었으면, 먼저 제출하는 것도 좋은 선택이다.

- 유용한 코드를 라이브러리처럼 만들어 두자. 여러 후보를 생각해보고, 미리 텍스트 / 워드 등으로 만들어 두자.

   (ex. toString() : float, int, ...,  /   Binomial coefficient  /   그래프 이론, 비트마스크 등)

- SRM이 끝나면, 다음날 쯤 꼭 그 문제를 Practice Room에서 풀어보자.