2022 KAKAO BLIND RECRUITMENT 2차 코딩테스트

카카오 2차 코테를 보고 왔다.

2차 코테에 뭐가 나오는지 1도 모르는 상태에서 테스트를 치를뻔 했는데, 2차는 1차와 전혀 다르다는 말을 겨우겨우 주워듣고 나서야 관련한 정보를 조금 알아보게 되었다.

 

???

그렇다.. 카카오 2차 코딩테스트는 PS밖에 모르는 컴맹에게는 너무나도 가혹한 시험이었다.

나는 저기에서 REST API가 뭔지, JSON format이 정확히 뭔지 용어도 모르는 상태에서 스타트 하는것이다.

 

API가 무엇인지는 아주 약간이나마 알고 있었다. 서버에 뭔가 요청 보낸다음 원하는 정보 받아오는 것?

그럼 REST API는 뭘까? API의 한 종류인것 같은데 검색해봐도 잘 이해가 안가서 일단 덮어두기로 했다.

 

JSON format은 javascript를 쓸 때 딱 한번 다뤄본적이 있었다. parser 코드를 준비해 오라는건 API로 뭔가 받아오는 파일(?)이 json 형식이라는 말이고, 이를 본인이 쓰는 프로그래밍 언어로 쓸 수 있게 준비를 하라는 말로 이해할 수 있었다.

 

여기까지 생각해 보니 미리 준비해야 할 것이 대충 윤곽이 잡혔다.

1. 내가 아는 언어로 API 호출을 할 수 있는 모듈(?)을 구한다음 그 모듈의 사용방법을 익힌다. 

2. 그 결과가 json 형식이므로, 이를 바로 활용할 수 있는 parser을 구하거나 직접 작성한다.

코딩테스트 전날, 준비를 하기로 했다.

 

내가 가장 잘 쓰는 언어가 C++이니, C++로 이걸 준비하면 되지 않을까? 하는 생각이 가장 먼저 들어서, 주변 사람들한테 이렇게 말했다가 미친놈 소리를 들었다. 파이썬을 이용하는게 가장 일반적이고, 적어도 Java를 써야 편하게 준비할 수 있다는 말을 들었다.

하지만 자바로는 관련해서 뭔가 검색해도 나오는게 없었고, 있어도 내가 이해할 수가 없어서 결국 가장 정보가 많은 파이썬을 이용해야 했다.

 

 

파이썬은 신의 언어이다.

"import requests", "import json"

단 두 줄의 코드로 모든 걸 끝낼 수 있었다. API 호출도 함수 한줄로 해결할 수 있었고, json 파싱도 알아서 되는 걸 보고 감동했다.

아무튼 되는 걸 확인했고, 작년 문제가 열려 있길래 이걸 일단 정상적으로 1번 작동시키는 것을 목표로 모듈을 만들기 시작했다.

코드도 다 있으니 얼마 안걸리겠다고 생각했는데, 문제를 푸는 것도 아니고 단순히 "정상 작동" 시키는데 6시간이 걸렸다.

파이썬도 거의 처음이고, API 호출도 처음이라 어디에 문제가 있어도 내가 알아내기 힘들었기 때문이다.

함수에 인자를 잘못 주고 있는데, C++같으면 인자에 잘못된 데이터 타입이 들어간다고 미리 알려줬겠지만 파이썬은 그런거 없이 런타임에러만 냈다.

또 PUT method에 parameter를 줄 때는 "params="가 아니라 "data="를 이용했어야 하는데, 나는 이것도 몰라서 몇 시간동안 의미없는 디버깅만 해야만 했다.

 

코딩테스트 하는 당일날 이랬을걸 생각하니 정신이 아득해졌지만, 한편으로는 지금이라도 이걸 해서 다행이라고 생각했다. 결국 정상 작동까지 확인할 수 있었다.

---

코딩테스트 당일

코테 전 CS 테스트가 있는걸 잊고 있었다. 하지만 어자피 공부해도 결과가 딱히 달라졌을 것 같진 않았다.

절반은 알고리즘 관련, 나머지 절반은 OS/DB/네트워크 등등에서 나온 것 같았다. 알고리즘 관련된 문제들은 다 풀 수 있었고, 나머지는 절반 가량 풀지 못했다. 객관식은 나름대로 추측을 할 수 있었는데, 주관식에서 피눈물을 흘려야 했다.

 

CS 테스트가 끝나고 2차 코딩 테스트가 시작되었다. 다음은 대략적인 문제 설명과 내 풀이이다.

---

1:1 대결을 하는 게임이 있다.

각 유저들의 실력은 하나의 정수로 나타내어진다. 수가 클수록 실력이 높고, 작을수록 실력이 낮다. 전체적으로 이 수는 정규분포를 이룬다.

두 유저의 매칭이 성사되어 대결을 했을 때. 상대방에 비해 실력값이 높으면 높을수록 이길 확률이 높아지고, 낮으면 낮을수록 질 확률이 높아진다. 또, 두 유저의 실력차가 클 수록 게임이 빨리 끝나는 경향을 보인다.

 

이 게임을 하기 위해 유저들이 매칭 대기중이고, 이 유저들을 적절히 매칭시켜주어야 한다. 또, 모든 작업이 끝난 후에 각 유저들의 예상 실력 순위를 제출해야 한다.

 

점수는 다음과 같이 책정된다. (정확성 1 + 정확성 2) * 효율성

정확성 1 : 매칭된 유저들의 실력차가 작을수록 높아진다.

정확성 2 : 마지막에 제출한 예상 실력 순위가 정확할수록 높아진다.

효율성 : 유저들이 매칭이 성사되기까지 대기한 시간이 짧을수록 높아진다.

 

문제는 2개의 테스트 케이스를 가진다.

1번 테스트 케이스 : 30명

2번 테스트 케이스 : 1000+명

 

2번 테스트 케이스에는 패작을 하는 사람이 존재한다.

패작을 하는 사람은 자신보다 실력이 낮은 사람을 만나면 높은 확률로 무조건 진다. 대결 시간도 매우 짧아진다.

 

 

정확성 1에 대해 생각해보자. 매칭된 유저들의 실력차가 작을수록 점수가 높다는 말은, 높은 점수를 얻기 위해서는 실시간으로 유저들의 실력을 예측하여 최대한 비슷한 실력의 사람끼리 매칭을 해 주어야 함을 뜻한다. 즉, MMR 시스템을 구현해야 한다.

정확성 2는 이 최종 MMR이 높은 순으로 순위를 매겨주면 된다.

효율성의 경우, 너무 빠른 매칭만 추구하다보면 실력차가 큰 유저끼리 매칭이 될 가능성이 높아진다. 반대로 비슷한 유저가 올 때까지 무작정 기다리기만 하면 매칭이 너무 느려지게 된다. 최적이 되는 방식을 잘 찾아야 한다.

 

유저들의 대결이 끝날 때마다 승패여부, 대결에 걸린 시간에 대한 정보를 얻을 수 있으므로, 이를 통해 MMR을 조정해 보자.

초기 MMR은 모두 같은 값으로 설정했다.

A와 B의 대결로 A가 승리 했다고 가정하자. 실제 실력은 A가 B보다 높을 확률이 높으므로, A의 MMR은 높히고, B의 MMR은 낮춰야 한다. 동시에, (A의 원래 MMR - B의 원래 MMR)이 작을수록 더 변동이 크도록 했다. 더 실력이 높은 상대일수록 이를 이긴 유저의 MMR은 높을 가능성이 크고, 반대로 실력이 낮은 상대일수록 이에 진 유저의 MMR은 낮을 가능성이 크기 때문이다.

또, 진행된 게임 시간이 짧을수록 이 변동폭이 더 커지도록 조절했다. 게임 시간이 짧을수록 두 유저의 실력차가 클 가능성이 크기 때문이다.

너무 빠르게 끝난 대결은 그냥 MMR 변동 없이 무시했다. 패작을 걸러내기 위함인데, 매칭 시스템이 제대로 작동하고 있다면 그 정도로 큰 실력차를 가진 두 사람은 매칭이 안 될 가능성이 더 크다고 생각했기 때문이다.

매칭이 너무 오랫동안 잡히지 않는 것을 방지하기 위해, 오래 기다린 유저일 수록 더 큰 실력차를 가진 상대를 만날 가능성이 높아지도록 했다. 또, 오래 기다린 유저일수록 매칭 우선순위를 높혔다.

 

 

지금까지의 풀이를 대략적으로 구현만 해도 2번 테스트 케이스의 경우 최상위권의 점수를 받을 수 있다.

그런데 1번 테스트 케이스의 경우 중하위의 점수에 그쳐서, 그 원인을 알아보았다.

 

스코어보드의 1번 테스트 케이스를 푼 대부분의 사람들이 거의 만점에 가까운 효율성을 보여주었다.

이는 유저가 매칭요청을 하면 기다림없이 즉시 매칭을 시켜주었다는 것을 의미한다. 실제로 총 유저가 30명 정도밖에 되지 않으므로, 안그래도 매칭을 할 수 있는 인원이 적은데 굳이 비슷한 실력의 유저를 찾을 필요가 없다. 이를 고쳐서 중상위권의 점수까지 올렸다.

---

그렇게 총 450점 정도의 점수로, 스코어보드 상에서 100등 후반의 등수로 마무리했다.

아쉬웠던 점은 다음과 같았다.

 

1. 파이썬은 느린 언어이고, API 통신도 많이 느린데 이를 간과했다.

나는 하던대로 C++을 생각하고, 원하는만큼 제출하면서 내 코드의 각 파라미터를 파인 튜닝할수 있을 것이라고 생각했다.

하지만 프로그램이 한 번 동작하는데 아무것도 안해도 5분, 뭔가 느린 코드가 있을 때는 최대 20분까지 걸렸다.

총 5시간의 코딩테스트 시간동안 뭔가 코딩하는 시간보다는 멍하니 실행되는 코드를 바라보는 시간이 더 많았다. 더 Pythonic한 코드를 짰다거나, 설계를 더 꼼꼼히 했으면 하는 아쉬움이 있었다.

 

2. 1번 테스트 케이스의 경우, "완전 탐색"으로 답을 찾아낼만 했다.

애초에 유저가 30명 밖에 되지 않으므로, 1번 테스트 케이스에 조금만 더 시간을 썼더라면 완전 탐색에 적절한 커팅으로 완벽한 답을 찾았을 수도 있었을 거라 생각한다. 이를 대회 중에 생각하지 못한건 아쉬운 부분이었다.

 

아무튼 이 등수대면 무난하게 합격할 것이라는 주변사람들의 카더라 통신이 있어서, 큰 긴장하지 않고 기다렸더니 곧 좋은 소식이 날아왔다.

 

 

면접은 어떤 느낌으로 진행될지 참 기대된다.