queuedlab

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

Problem Solving
올해 처음으로 Google Code Jam Round 3에 진출했고, 프로그래머스 월간 코딩 챌린지와 카카오 인턴십 코딩 테스트에 참가했습니다.

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


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월쯤에 공식 블로그를 통해 문제와 해설이 공개되었으니, 올해 문제가 공개되고 나면 글을 업데이트해야겠다.