카카오 2020 공채 코딩 테스트 해설: 팔로잉 추천 시스템 구현

카카오가 2020년 오프라인 코딩 테스트 2차 문제인 '카카오팔로잉' 팔로잉 추천 시스템 구현에 대한 해설을 공개했다. 이 문제는 가상의 SNS 서비스에서 사용자의 팔로잉 수를 20명 이상으로 만드는 것이 목표이며, REST API를 통해 서버와 데이터를 주고받으며 매일 추천 작업을 수행하는 로직을 설계해야 했다.

추천 확률 계산 기준

추천 시스템의 성능은 시뮬레이션을 통해 평가되며, 사용자가 추천 목록의 타인을 팔로우할 확률은 다음과 같다.

• 전화번호부 미등록자 추천: 5%p 증가
• 전화번호부 등록자 추천: 30%p 증가
• 전화번호부 등록자가 팔로우하는 사람 추천: 팔로우하는 사람당 10%p 증가
• 내가 팔로우하는 사람이 팔로우하는 사람 추천: 팔로우하는 사람당 10%p 증가

다양한 접근 방법

• Simple: 랜덤 추천으로 많은 횟수 필요.
• Greedy: 확률 높은 순서대로 추천하되 정렬로 인해 수행 시간이 길어 시험 시간 내 달성 어려울 수 있음.
• Heuristic: Greedy의 정렬 대상을 줄여 수행 시간을 단축.
• No-sort: 정렬 과정을 제거하여 수행 시간 이득을 보지만 Greedy보다 추천 횟수가 많을 수 있음.
• Smallest: 전체 사용자 목록 순서대로 추천하여 자연스러운 확률 증가를 유도하며, 확률 계산 및 정렬이 없어 수행 시간이 짧음.

시험 결과 분석

총 응시자 349명 중 Python 사용이 277명으로 가장 많았다.

• 시나리오 1 (100명 고정): 총 2,521번 시도 중 1,142번(약 45%) 성공. 응시자 기준 약 62%(217명)가 해결.
• 시나리오 2 (3,000명 및 동적 변화): 총 2,514번 시도 중 94번(약 4%) 성공. 응시자 기준 약 4%(40명)가 해결.