올해 오프라인으로 진행된 2차 코딩 테스트 문제는 가상의 SNS 카카오팔로잉을 위한 팔로잉 추천 시스템을 구현하는 것이었습니다.

카카오팔로잉

카카오팔로잉은 팔로우 기반의 구독형 SNS로, 팔로잉(팔로우 중인 상대 사용자)의 글과 사진을 볼 수 있는 서비스입니다. 이 서비스는 다음과 같이 동작합니다.

사용자는 전화번호를 ID로 사용하여 가입합니다.
가입한 사용자의 전화번호부는 카카오팔로잉 서버에 등록됩니다.
사용자의 전화번호부는 시간이 지남에 따라 변경 될 수 있으며, 변경된 경우 즉시 서버에 동기화됩니다.
가입 시점 사용자는 팔로잉이 없습니다.
사용자가 팔로우 할 때 상대의 동의는 필요하지 않습니다.
사용자는 팔로잉 추천 시스템이 제공하는 추천 목록에서만 팔로우 할 상대를 고를 수 있습니다.

팔로잉 추천 시스템 구현

팔로잉 추천 시스템의 목표는 팔로잉 추천을 통해 카카오팔로잉 사용자들의 팔로잉이 각각 20명 이상이 되도록 하는 것입니다.

추천 시스템은 REST API로 카카오팔로잉 서버와 JSON 포맷의 데이터를 주고받으며, 다음과 같이 매일 1회 추천 작업을 수행합니다.

서버로부터 추천 로직에 필요한 데이터 다운로드
추천 로직 수행
서버로 추천 목록 업로드

추천 시뮬레이션

팔로잉 추천 시스템의 성능은 시뮬레이션을 통해 평가됩니다. 시뮬레이션 작업은 응시자마다 주어진 독립된 카카오팔로잉 서버에서 다음과 같은 가정하에 수행됩니다.

매회 시뮬레이션은 일 단위입니다. 즉, 매회 시뮬레이션이 완료될 때마다 하루가 지납니다.
매회 시뮬레이션은 해당 일의 추천 작업에 필요한 모든 내용들이 준비된 상태입니다.
매회 시뮬레이션은 서버에 업로드 된 해당 일의 추천 목록을 가지고 수행됩니다.
추천 작업과 시뮬레이션 작업은 목표를 달성할 때까지 번갈아 반복됩니다.

시뮬레이션 시나리오

시나리오 1
- 최초 가입 100명
- 추가 가입 및 전화번호부 변경 없음
시나리오 2
- 최초 가입 3000명
- 이후 30일동안 매일 신규 가입 및 전화번호부 변경 존재
공통 제약사항
- 하루 최대 R명 추천 가능 (R은 해당 일의 총 사용자 수)
- 사용자별 하루 최대 10명 추천 가능

팔로우 확률

시뮬레이션에서 어떤 사용자가 추천 목록에 있는 다른 사용자를 팔로우 할 확률은 다음의 기준들로 계산됩니다.

기준	조건	확률
1	내 전화번호부에 없는 사람을 추천 받은 경우	5%p 증가
2	내 전화번호부에 있는 사람을 추천 받은 경우	30%p 증가
3	내 전화번호부에 있는 사람이 팔로우 하는 사람을 추천 받은 경우	팔로우 하는 사람당 10%p 증가
4	내가 팔로우 하는 사람이 팔로우 하는 사람을 추천 받은 경우	팔로우 하는 사람당 10%p 증가

출제 의도

시뮬레이션 횟수를 추천 횟수라고 하면, 성능이 우수한 추천 시스템은 적은 추천 횟수로도 목표를 달성할 수 있습니다. 이를 위해 적합한 추천 방법을 선택할 필요가 있습니다. 하지만 이번 시험에서 최적의 알고리즘 여부와 관계없이 목표를 달성하는 것만으로도 적지 않은 점수를 얻을 수 있도록 평가 기준을 세웠습니다. 그 이유는 이번 시험이 알고리즘 활용 능력만이 아닌 종합적인 문제 해결 능력을 평가하고 있기 때문입니다.

시뮬레이션 시나리오는 난이도와 더불어 문제 해결 단계에 따라 나눴습니다. 시나리오 1은 문제에 대한 이해도를 높이고 API 연동을 하면서 문제에 익숙해질 수 있는 수준으로, 시나리오 2는 더 나아가 고도화 작업이 필요한 수준으로 설정되었습니다. 이렇게 함으로써 시스템 구현을 단계적으로 접근하고, 또한 시나리오 1 해결만으로도 점수를 얻을 수 있도록 했습니다.

실세계 SNS의 사용자 수는 수십만, 수백만, 혹은 수천만 규모일 수 있기 때문에 추천 로직을 설계함에 있어 수행 시간은 중요한 성능 요소입니다. 하지만 이번 시험에서 수행 시간은 직접적인 평가 요소로 반영되지 않았습니다. 왜냐하면 응시자마다 사용 언어와 컴퓨터 환경이 달라 같은 로직이라도 수행 시간이 크게 다를 수 있기 때문입니다. 따라서 시험 시간 내에 목표를 달성할 수 있는 선에서 로직을 구현하도록 의도했습니다.

다양한 접근 방법

팔로잉 추천 시스템 구현 문제는 다양한 접근 방법으로 해결 가능합니다. 그 중 일부 방법에 대해 간략히 살펴보겠습니다.

Simple

팔로우 가능한 사용자들 중에서 랜덤하게 선택하여 추천

문제의 특징을 이용하지 않기 때문에 목표를 달성하기까지 많은 횟수의 추천이 필요합니다.

Greedy

팔로우 가능한 사용자들 중에서 팔로우 확률이 높은 순서대로 선택하여 추천

팔로우 확률을 고려하여 추천하기 때문에 적은 횟수의 추천으로도 목표를 달성할 수 있습니다. 다만 정렬이 필요하기 때문에 추천 로직 수행에 긴 시간이 필요하다는 단점이 존재합니다. 문제 풀이 환경에 따른 차이가 있겠지만, 시뮬레이션 시나리오 2의 경우 목표 달성까지 수십 분 이상 소요될 수 있습니다. 디버깅 및 개선 작업을 포함한 구현 시간을 고려할 때, 시험 시간 내에 목표를 달성하기 어려울 수 있습니다.

Heuristic

팔로우 확률 계산 기준 2, 3, 4를 만족하는 사용자들 중에서 팔로우 확률이 높은 순서대로 선택하여 추천

위 Greedy 방법에서 정렬 대상을 줄여 수행 시간을 줄인 방법입니다. 기준 2, 3, 4를 만족하는 사용자들을 대상으로 우선 선택하고 기준 1만 만족하는 사용자들로 나머지 추천 가능한 수를 채우면 실상 Greedy 방법과 같은 방법입니다. 기준 1만 만족하는 사용자들은 우선순위가 가장 낮기 때문입니다. 따라서 Greedy 방법과 비슷한 추천 횟수로 목표를 달성할 수 있습니다.

No-sort

팔로우 확률 계산 기준 2, 3, 4를 만족하는 사용자들 중에서 선택하여 추천

위 Heuristic 방법에서 정렬 과정을 뺀 방법으로 그만큼 수행 시간에서 이득을 볼 수 있습니다. 비록 Simple 방법보다 적은 추천 횟수로 목표를 달성할 수 있지만, Greedy/Heuristic 방법보다 많은 추천 횟수가 필요할 수 있습니다.

Smallest

팔로우 가능한 사용자들 중에서 전체 사용자 목록 순서대로 선택하여 추천

모든 사용자들의 팔로우 순서를 동일하게 만들면 팔로우 확률 계산 기준 3, 4에 따라 팔로우 확률이 점차 커지도록 소셜 네트워크를 만들 수 있습니다. 따라서 시간이 지남에 따라 자연스럽게 팔로우 확률이 큰 사용자를 추천하기 때문에 Greedy/Heuristic 방법 만큼 적은 추천 횟수로 목표 달성을 기대할 수 있습니다. 여기에 더해, 확률 계산 및 정렬 과정이 없기 때문에 수행 시간이 아주 짧다는 이점도 있습니다.

시험 진행 결과

프로그래밍 언어별 응시자 수

언어	응시자 수
Python	277
Java	66
JavaScript	20
C++	13
C#	8
Go	2

총 응시자 수는 349명으로, 사용 언어를 바꿔 문제를 푼 일부 응시자의 경우 위 표에서 중복으로 집계되었습니다. Python이 가장 많이 사용되었습니다.

시뮬레이션 시나리오별 요약

시나리오 1

시간대	목표 달성 횟수	최초 목표 달성자 수
14:00-15:00	17	9
15:00-16:00	151	44
16:00-17:00	413	95
17:00-18:00	561	69

시나리오 1을 해결하기 위해 총 2,521번 시도(시뮬레이션 시나리오를 새로 시작)가 있었으며, 이 중 목표 달성한 횟수는 1,142건(약 45%)이었습니다. 목표 달성 시도들 중 약 85%가 시험 시작 2시간 경과 후에 발생했습니다. 가장 적은 추천 횟수로 목표 달성한 경우 38회였습니다. 시나리오 1을 해결한 응시자 수는 전체 응시자들 중 약 62%인 217명이었습니다.

시나리오 2

시간대	목표 달성 횟수	최초 목표 달성자 수
14:00-15:00	-	-
15:00-16:00	-	-
16:00-17:00	21	11
17:00-18:00	73	29

시나리오 2를 해결하기 위한 시도는 총 2,514번으로 시나리오 1과 비슷한 수준이었지만, 이 중 목표 달성으로 이어진 경우는 94건(약 4%)에 그쳤습니다. 최초 목표 달성은 시험 시작 2시간 경과 후 발생했습니다. 목표 달성한 시도들 중 추천 횟수가 가장 적은 경우 33회였습니다. 시나리오 2의 총 목표 달성자 수는 전체 응시자들 중 약 4%인 40명이었습니다.

기타

코딩 테스트 플랫폼인 프로그래머스의 사정으로 API 제공이 불가능하여 시뮬레이션을 직접 해볼 수 없는 점 양해 부탁드립니다.

마치며

이렇게 오프라인 코딩 테스트는 마무리되었지만 개인적인 호기심은 여전히 남아있습니다. Smallest 방법에서 모든 사용자들에게 동일하게 적용할 팔로우 순서는 어떻게 정하면 좋을까요? Smallest 방법과 Greedy/Heuristic 방법을 조합해서 더 좋게 만들 수는 없을까요? 그리고 각 사용자별로 몇 명을 추천해야 할까요? 앞서 언급한 방법들 외 또 다른 접근 방법은 없을까요? 이 글을 읽고 계신 여러분들 중에 좋은 아이디어가 있다면 한번 들어보고 싶습니다. 아래 이메일 주소를 남겨 놓고 설레는 마음으로 기다리고 있겠습니다 :)

시험을 치룬 모든 분들에게 좋은 경험으로 기억되길 바라며, 또한 여러분의 한 걸음을 밝히는 작은 불씨가 되었으면 좋겠습니다.

지금까지 읽어주셔서 감사합니다.

2020 카카오 블라인드 공채 2차 오프라인 코딩 테스트 문제 해설