지난 2021년 9월 25일(토), 2022 KAKAO BLIND RECRUITMENT 2차 코딩 테스트가 있었습니다.

이번 2차 코딩 테스트는 코로나19 사태가 장기화됨에 따라 온라인 환경에서 비대면으로 진행되어 각자 편안하게 느끼시는 장소에서 응시하도록 안내되었습니다. 작년과 마찬가지로 부정행위 방지를 위한 사전 준비 시간을 가지고 짧은 CS 테스트를 실시한 후, 4시간 45분에 걸쳐 진행되었습니다.

문제 내용과 테스트 환경은 코딩 테스트 플랫폼인 프로그래머스에서 제공되니 참고 부탁드립니다.

* 신입공채 2차 코딩 테스트 문제를 풀어볼 수 있는 환경

출제 의도

알고리즘 문제를 풀고 정답을 확인하는 1차 문제들과 달리 2차 코딩 테스트는 실제 업무에서 주어지는 개발문서와 흡사한 지문을 이해하고, 요구사항을 파악하는 종합적인 사고력을 필요 하는 문제를 출제하고자 했습니다.

또한 시험 도중에 본인의 등수를 리더보드로 제공하여 남은 시간과 등수에 따라 문제 풀이 방법을 전략적으로 선택해야 했습니다.

문제 접근 방법

게임 매칭 시간을 길게 잡으면 비슷한 실력의 유저가 나타날 확률이 높아져 정확성 점수는 높아지지만 효율성 점수는 떨어집니다. 반대로 매칭 시간이 짧으면 정확성 점수는 떨어지고 효율성 점수는 올라갑니다. 두 점수는 trade-off 관계를 가지기 때문에 둘 사이에서 높은 점수를 얻도록 튜닝하는 식으로 접근하도록 출제되었습니다.

실제 세계와 달리 시뮬레이션은 여러 번 반복이 가능하므로 가능한 한 많은 전략들을 시도해 보고 조합하면서 점수 변화를 확인하며 점수를 높일 수 있었고 대부분의 응시자들 또한 이러한 접근법을 사용하였습니다.

이외에도 다양한 접근 방법이 있지만, 비교적 유효한 방법 위주로 간략히 살펴보겠습니다.

단순한 전략 1

대기열에 2명 이상 들어오면 즉시 매칭을 시킵니다. 승자에게는 +1점 패자에게는 -1점을 부여합니다. 게임을 기다리는 시간이 최소가 되기 때문에, 효율성 점수가 가장 높아집니다. 대신 정확성 점수는 랜덤한 매칭에 의해 부여되므로 고득점을 노리기 힘든 방법입니다.

응시 초반에 API의 구현이 제대로 되었나 확인하고, 알고리즘을 튜닝해서 추후 이보다는 점수가 높아져야 한다는 대조를 위한 기준으로 삼기 위해 이용되는 전략이었습니다.

단순한 전략 2

대기열에서 유저를 최대한 오래 기다리게 하고 점수가 비슷한 상대끼리 매치합니다. 이전 전략과 마찬가지로 점수 부여는 단순하게 승자에게는 +1점 패자는 -1점을 부여합니다. 이 전략은 효율성 점수는 포기하고 정확성 점수를 높이는 전략입니다. 효율성 점수 비중이 정확성 점수 비중보다 낮다는 점을 이용한 방법입니다.

고득점을 노리는 분들에게는 이전 전략과 마찬가지로 알고리즘을 튜닝할 때 이보다 점수가 높아야 한다는 기준점으로 사용되었습니다.

일반적인 전략

유저의 실력에 대해 알 수 있는 유일한 단서는 매칭 결과로 나오는 게임 시간과 승패 여부입니다. 이 둘을 사용하는 수식을 만들어 유저 점수에 반영하는 방법입니다. 많은 응시자분들이 접근 한 방식이었습니다.

게임 시간이 짧을수록 실력 차이는 큰 것을 의미하므로, (40 - 게임시간) * (가중치) 와 같은 수식을 만들어 이긴 사람의 점수는 더하고 진 사람에게는 빼는 방법을 취할 수 있었습니다.
게임에 참여한 두 유저의 점수 차이도 고려하여 점수를 부여할 수 있습니다.
게임 횟수가 많은 유저일수록 점수가 정확할 확률이 높으므로 이를 활용하여 매칭 시킵니다.

이 전략을 적용해서 고득점을 획득한 경우가 다수 있었습니다. 응시자가 직접 생각해야 하는 부분이 적지 않음으로 알고리즘을 튜닝할 부분이 많이 있었습니다.

ELO 평점 시스템

세계 체스연맹 등 다양한 곳에서 쓰이는 ELO 시스템을 활용하는 방법입니다. 실제로 많이 이용되는 방법이고 정확도가 높게 나왔습니다.

모든 유저의 점수를 일정 값으로 초기화합니다.
점수가 비슷 상대끼리 매칭합니다.
(가중치) * (경기 결과 - 이길 확률) 만큼 점수 변화를 줍니다.
(경기 결과)는 이겼을 경우 1, 무승부 경우 0.5, 졌을 경우 0으로 설정합니다.
유저 A가 (이길 확률)은 1 / (1 + 10^(B의 점수 - A의 점수) / 400)으로 계산합니다.

* ELO 평점 시스템 위키 보러가기

어뷰저 처리 방법

시나리오 2 에서는 실력과 무관하게 게임에서 고의 패배를 하는 어뷰저가 있었습니다. 어뷰저를 잘 처리하는 것으로 점수를 노릴 수 있었고, 시험에서는 주로 두 가지 방법이 많이 사용되었습니다.

어뷰저의 비율이 5% 수준이므로 무시하고 진행하는 방법
어뷰저가 고의 패배 하는 경우 게임 시간이 10분 이하이므로 10분 이하 결과만 무시하는 방법

더 복잡한 처리를 해서 고득점을 노리는 경우는 아래와 같았습니다. 특히 어뷰저에 복잡한 처리를 한 응시자의 경우 고득점인 경우가 많았습니다.

시뮬레이션이 끝날 때 매칭 기록을 통해 어뷰저를 색출하고 10분이 넘어가는 게임 기록만 적용하도록 조정
10분 보다 짧은 게임 기록은 카운팅 하고 블랙리스트에 올림
어뷰저로 의심되는 유저는 매칭을 막거나, 점수가 높은 유저와만 매칭 시킴

최적화 방법

최대한 많은 솔루션을 시도해 보려면 시뮬레이션이 돌아가는 시간이 짧을수록 유리합니다. 유저에게 점수를 부여하는 방식이 매번 호출될 필요가 없다는 것을 문제 조건에서 눈치챘다면 시뮬레이션 시간을 단축하는 것이 가능했습니다.

ChangeGrade API는 PUT Method 이므로 GET Method 에 비해 호출시간이 긴 API 입니다. 매치가 있을 때마다 ChangeGrade API를 호출하는 것이 아닌 시뮬레이션이 끝나기 직전 한 번만 호출하는 것으로 PUT Method 호출을 최소화할 수 있었습니다.

마치며

이번 2차 코딩테스트는 일상의 경험과 밀접하게 연관되어 재미있게 느껴졌던 문제였습니다. 저는 온라인 게임을 할 때 게임의 매칭 시스템이 너무 오래 걸리면 불만을 표시하곤 했는데요, 이번 문제를 살펴보며 매칭 시스템을 구현하는 것이 얼마나 어려운지 생각해 보게 되었고, 매칭 시스템 개발자분들에게 감사하다는 생각을 가지게 되었습니다.

지금까지 2022 KAKAO BLIND RECRUITMENT 2차 코딩 테스트 문제의 접근법에 대해 알아보았습니다. 테스트에 응시해 주신 분들께 즐거운 추억으로 기억되길 바라며, 읽어주셔서 감사합니다.

✔️ 카카오 온라인 코딩 테스트 문제해설 바로가기

2022 카카오 신입 공채 2차 온라인 코딩 테스트 for Tech developers 문제해설