2021년 상반기에 참가한 알고리즘 대회

항상 대회가 끝나면 블로그에 후기글을 올려야겠다고 다짐하지만, 요즘 학교 과제와 동아리 일 등으로 바쁘다 보니 장문의 후기글을 쓰는 것이 부담스럽게 다가옵니다. 그래서 우선 참가한 대회 목록이라도 짤막하게 정리해 보려고 합니다. 매년 상반기보다는 하반기에 대회가 더 많이 열리기 때문에, 참가한 대회가 많지는 않습니다.

Google Code Jam

Qualification Round

라운드 보기

문제를 전부 풀고 562등을 달성했다.

5번 Cheating Detection 문제가 독특했는데, 치팅한 사람을 잡아내는 휴리스틱을 구현하는 문제였다. 각 사람마다 질문에 올바른 답을 낼 확률이 로지스틱 함수로 주어졌기 때문에 로지스틱 회귀를 적용하면 좋을 것 같다는 발상을 했다. 치팅을 하지 않은 사람은 로지스틱 회귀를 돌렸을 때 질문의 난이도에 곱해지는 계수가 1에 가깝게 나오겠지만, 치팅을 한 사람은 커브가 완만해지므로 계수가 1보다 작게 나올거라는 아이디어를 떠올렸고, 직접 로지스틱 회귀를 구현하여 가장 계수가 작은 사람을 찾는 방식으로 문제를 푸는 데 성공했다.

끝나고 풀이를 보니 훨씬 간단한 풀이들이 있었다. 그래도 공개된 테스트 데이터를 직접 넣어 보니 문제에서 요구한 성공률 86%를 훨씬 넘은 98%를 달성해서 (50개의 데이터 중 Case #8 단 하나만 틀렸다) 의미 있는 시도였다고 생각한다.

Round 1B

라운드 보기

1라운드는 1A, 1B, 1C 중 1B에만 참가했다. 1번부터 구현이 빡센 문제가 나와서 푸는 데 70분이 걸렸고, 그래서 이번 라운드를 통과하지 못할까봐 걱정했는데 2, 3번을 생각보다 빠르게 풀어버려서 대회 시간 안에 올솔브를 했다. 예상보다 높은 135등을 달성했다.

2번 Subtransmutation 문제를 풀 때 Frobenius coin problem을 알고 있던 것이 도움이 됐다. (n=2일 때의 해를 Sylvester's theorem이라는 이름으로 배운 적이 있다.) 뒤에서도 언급하겠지만, Round 1B 이전에 프로그래머스 월간 코딩 챌린지에 참가했었는데 거기에도 이 Frobenius coin problem을 알면 도움이 되는 문제가 나왔었다. 신기한 우연의 일치라고 생각했다.

Round 2

라운드 보기

815등을 달성해서 올해 처음으로 Round 3에 진출한다! 코드 잼 티셔츠도 처음 받는데 기대된다.

1, 2, 3번 만점을 받았다. 4번은 대회가 끝나기 직전에 테스트 셋 1을 풀었지만 아쉽게도 제출하지 못했다. 3솔브 했는데 아슬아슬하게 통과한 걸 보고 라운드 2가 생각보다 빡세다는 걸 체감했다.

3번 문제 Hidden Pancakes가 재미있었다. 나는 재귀적인 발상의 계산식을 먼저 떠올리고 스택을 사용해서 최적화하는 방법으로 풀었는데, 공개된 풀이를 보니 대소 관계를 트리 형태로 나타내는 풀이도 있었다. 둘 다 흥미로운 풀이라고 생각한다.

Round 3

아직 라운드 시작 전이다. 대회를 치고 나면 글을 업데이트할 예정이다.

프로그래머스 월간 코딩 챌린지 시즌 2

대회 정보 및 문제

작년에 이어 올해 두 번째로 열리는 월간 코딩 챌린지이다. 5월 대회 때는 바빴기 때문에 4월 대회에만 참가했다. 총 세 시간동안 진행되는 대회였지만 한시간 반만에 모든 문제를 풀고 4등을 달성했다! 아쉽게도 상은 1등만 준다.

4번 RPG와 쿼리 문제가 앞에서 언급한 것처럼 Frobenius coin problem을 연상시켰고, 덕분에 금방 풀이를 떠올릴 수 있었다.

2021 카카오 채용연계형 인턴십 코딩 테스트

모집 공고

총 5문제가 출제되었고, 모든 문제를 풀어서 코딩 테스트에 통과했다. 하지만 미리 써 둔 지원서도 없었고 졸업예정일도 불확실해서 면접은 가지 않기로 했다.

문제 내용을 유출하면 안 되기 때문에 아직 자세한 후기를 적을 수는 없지만, 3~5번이 생각보다 난이도 있었다. 작년에는 7월쯤에 공식 블로그를 통해 문제와 해설이 공개되었으니, 올해 문제가 공개되고 나면 글을 업데이트해야겠다.