shaun.seon

B2C 서비스에서 대용량 트래픽에 대응하는 방법을 고민하고 있습니다.

2021-02-16
shaun.seon
career, coding, coding test, kakao, new-krew, recruitment, tech, test

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

지난 2020년 9월 26일(토)에 2021 카카오 신입 개발자 블라인드 채용 과정의 2차 코딩 테스트가 진행되었습니다.

이번 2차 코딩 테스트는 코로나19 위기감이 높아지는 시기에 치러짐에 따라 지원자분들의 안전을 위해 이전과 달리 오프라인 장소에 모여서 진행하지 않고 온라인 환경에서 비대면으로 진행하게 되었습니다. 이전 오프라인으로 코딩 테스트 진행 시에는 현장에서 다른 지원자와 함께 같은 공간에서 참여하게 되어 다소 긴장감을 느낄 수 있었으나, 이번에는 각자 편안한 장소와 익숙한 개발 환경에서 진행하게 되어 심리적으로 도움이 되지 않았을까 합니다.

특히나 제주도를 비롯하여 멀리 지방에 계신 지원자분들에게 테스트 장소로 이동하는 데 따른 시간적인 부담을 덜어드릴 수 있게 된 점도 긍정적으로 볼 수 있습니다. 다만 테스트를 진행해야 하는 저희 카카오 입장에서는 이번 테스트가 온라인으로 진행되면서 부정행위 방지를 위해 지원자분들을 화상으로 모니터링하는 시스템을 준비해야 했고, 처음 시도하는 방법이라 테스트 중에 문제가 있지 않을까 많은 걱정이 되었던 것이 사실입니다.

이를 위해 테스트 당일 테스트 감독관과 지원자분들이 혼란을 겪지 않도록 미리 화상 감독 환경을 설정해 보면서 네트워크 환경 등에 이슈가 없는지 사전 점검하고, 동시에 화상 감독 시스템이 많은 수의 지원자가 동시에 접속하는 트래픽을 잘 버틸 수 있는지 검증하기 위해 9월 21일(월)에 감독관과 지원자분들이 함께 참여하는 사전 예행연습 성격의 모의테스트를 진행하기도 하였습니다. 지원자분들은 테스트 당일 핸드폰 카메라로 자신의 모습이 감독관에게 잘 보이도록 세팅하고 신분증을 준비해서 본인이 맞는지 확인을 한 후 테스트를 시작하였습니다.

2차 코딩 테스트는 오후 12시 30분부터 오후 7시까지 총 6시간 30분에 걸쳐 CS 문제와 코딩 테스트가 다음과 같이 진행되었습니다.

CS 테스트

CS 테스트는 총 10개의 문제(단답형 주관식 1문제, 객관식 9문제)가 출제되었으며 15분의 풀이 시간이 주어졌습니다. 문제의 구성은 자료구조 3문제, 데이터베이스 2문제, 네트워크 2문제, 운영체제 2문제, 알고리즘 1문제로 영역을 골고루 배분하였습니다.

난이도는 CS 기초 지식을 검증하는 수준으로 대부분의 지원자분들이 어렵지 않게 커트라인을 통과할 수 있는 수준으로 출제하였습니다.

코딩 테스트

CS 테스트가 끝나고 15분의 휴식시간을 갖고 4시간 45분에 걸쳐 2차 코딩 테스트가 진행되었습니다.

2차 코딩 테스트는 1차 코딩 테스트 알고리즘 문제처럼 TC를 통과하면 되는 정답형 문제가 아니며, 탄탄한 기본기와 개발 경험을 바탕으로 문제의 요구 사항을 잘 이해하고, trade-off를 감안하여 로직을 설계하고 결과를 시뮬레이션을 통해 확인하면서 최선의 결과가 나오도록 점진적으로 로직을 개선해 나가는 역량을 검증하고자 하는 의도를 가지고 있습니다.

테스트 도중 지원자분들이 자신이 작성한 코드의 결과가 어느 정도 수준인 지 확인할 수 있도록 리더보드를 100위까지 제공하였습니다.

✔️ 코딩테스트 Tip

사전에 안내되었듯이 문제를 풀기 위해서는 REST API 호출이 필수이며 API 결과가 JSON 포맷이므로 지원자분들은 각자 자신 있는 개발 언어로 REST API 호출 처리 모듈과 JSON 파서를 사전에 준비해 두는 것이 중요합니다.

문제 지문을 이해하고 풀이 방법을 고민하는 데 시간이 꽤 필요하여 주어진 시간이 여유로운 상황이 아니므로 초반에 REST API 호출과 JSON 파서 때문에 시간을 많이 소비하게 된다면 시간이 부족할 수 있겠습니다.

카카오 T 바이크 관리 시뮬레이션

카카오 T 바이크는 카카오 모빌리티에서 제공하는 전기 자전거 대여 서비스입니다. 서비스의 문제점은 어떤 지역은 대여 수요는 많으나 반납되는 자전거가 없어 자전거가 부족하고, 반대로 어떤 지역은 반납되는 자전거는 많지만 대여 수요가 없어 자전거가 쌓이기만 한다는 것입니다. 이런 현상을 해결하기 위해 신입사원 죠르디에게는 트럭으로 자전거를 재배치하라는 업무가 주어졌습니다. 지원자는 죠르디를 도와 자전거가 많이 대여될 수 있도록 트럭을 운영해봅시다.

트럭 운영 목표

목표 : 트럭을 효율적으로 운영하여 대여소에 취소되는 대여 요청 수를 최대한 줄여야 합니다. 단, 트럭은 적게 움직이는 편이 좋습니다.

서비스 지역 및 제약 사항 설명

서비스 지역

자전거를 대여하고 반납할 수 있는 서비스 지역은 NxN 크기의 정방형 격자 모양으로 주어집니다. 각 칸의 한 변의 길이는 100m이며, 한 칸에는 자전거 대여소가 하나씩 있습니다. 자전거 대여소에는 0부터 (NxN) - 1까지의 ID가 지정되어 있습니다. ID 값은 격자의 좌하단부터 0에서 시작하여 하나씩 증가하는 일련번호입니다.

다음은 5X5 크기 서비스 지역의 예시입니다.

대여소 제약 사항

대여소에는 자전거를 무한대 보관할 수 있다고 가정합니다.

사용자 제약 사항

사용자는 트럭이 운영하는 시간 동안만 대여 요청을 할 수 있습니다.
사용자는 대여 요청을 할 때 다음 정보를 모두 알려줍니다.
- 자전거를 대여할 자전거 대여소 ID
- 자전거를 반납할 자전거 대여소 ID
- 자전거를 탈 시간(분 단위, 소수점 없음)
사용자는 정시 분(minute)에 대여 요청을 보냅니다.
- 즉, 12시 1분에 대여 요청을 할 수 있으나 12시 1분 30초에는 대여 요청을 하지 않습니다.
사용자가 요청을 보낸 시점에 자전거 대여소에 자전거가 부족하면 사용자가 보낸 요청은 자동으로 취소됩니다.
자전거를 대여한 사용자는 반드시 대여 시 약속한 시각과 장소에 자전거를 반납하는 것으로 가정합니다.
실제 카카오 T 바이크에서 사용자는 애플리케이션과 자동 잠금장치를 이용하여 아무 곳에서나 자전거를 대여하고 반납할 수 있으나, 이번 과제에서는 문제를 간단화하기 위하여 지정된 위치에서만 자전거를 대여하고 반납할 수 있다고 가정합니다.

트럭 제약 사항

트럭은 바둑판 모양의 길을 따라서 상하좌우로만 이동합니다. 즉, 대각선 방향으로는 이동할 수 없습니다.
- 단, 트럭은 서비스 지역을 벗어날 수 없습니다.
트럭은 매일 아침 오전 10시에 ID가 0인 자전거 대여소에 모여 있으며, 오후 10시까지만 운행합니다.
- 트럭은 아무 곳에서나 운행을 종료할 수 있으며, 도중에 멈춰 서는 것도 가능합니다.
트럭이 100m를 이동하는 데에는 6초가 걸립니다. 즉 트럭은 격자 한 칸을 6초 만에 이동할 수 있습니다.
트럭이 자전거 하나를 싣거나 내리는 데에는 6초가 걸립니다.
각 트럭은 자전거를 싣거나, 내리거나, 또는 길을 이동할 수 있습니다. 단, 한 번에 한 가지 일만 해야 합니다.
- 예를 들어, 12시 00분 00초에 자전거를 내리기 시작하면 12시 00분 6초부터 길을 달리거나 다른 자전거를 싣거나 내릴 수 있습니다. 12시 00분에 자전거 두 대를 동시에 내리거나, 길을 달림과 동시에 자전거를 내릴 수는 없습니다.
각 트럭은 자전거를 최대 20대 수용할 수 있습니다.

다음은 트럭이 이동 가능한 방향에 대한 예시입니다.

서버의 처리 순서

서버는 작업을 다음 순으로 처리합니다.

정시 분(minute)마다 사용자가 대여 요청을 할 때 받은 정보를 이용해, 사용 시간이 다 된 자전거를 반납 처리합니다.
정시 분(minute)마다 사용자가 보낸 새로운 대여 요청을 순서대로 처리합니다.
· 예를 들어 자전거가 1대 있는 자전거 대여소에 대여 요청이 2개 들어온 경우 json array(하단의 과거 대여 요청 기록 참고)의 앞쪽에 위치한 대여 요청에게 자전거를 빌려주고, 뒤에 있는 대여 요청은 취소합니다.
죠르디의 지시에 따라 트럭을 운행합니다.

시나리오

본 시험에는 시나리오 2개가 주어집니다.

시나리오 1(problem = 1)

서비스 지역의 크기: 5X5
자전거 대여 요청 빈도: 분당 요청 수 평균 2건
자전거 수: 100대. 각 자전거 대여소에는 초기에 자전거가 4대씩 있음
트럭 수: 5대

시나리오 2(problem = 2)

서비스 지역의 크기: 60X60
자전거 대여 요청 빈도: 분당 요청 수 평균 15건
자전거 수: 10,800대. 각 자전거 대여소에는 초기에 자전거가 3대씩 있음
트럭 수: 10대

[주의] 시나리오 2의 HotPlace 안내

시나리오 2에는 대여 요청이 가장 많이 일어나는 대여소와 반납이 가장 많이 일어나는 선호 대여소가 각각 1개씩 정해져 있습니다. 이 선호 패턴은 4시간(=240분)마다 변경되므로, 즉 12시간(=720분) 동안 서로 다른 패턴 3개를 볼 수 있습니다.

선호도가 가장 높은 대여소와 선호도가 가장 낮은 대여소의 대여 요청/반납 건수는 약 60배 차이를 보입니다.

선호도는 최근 3일 동안의 대여 요청을 기준으로 결정되며 선호도를 알아내려면 아래 과거 대여 요청 기록을 참고해 주세요.

과거 대여 요청 기록

아래의 파일에는 하루 전, 이틀 전, 사흘 전에 들어온 대여 요청을 시각(분) 별로 기록한 것입니다. 각 파일은 다음과 같은 json format으로 되어있습니다.

json	설명
Key	사용자의 요청이 들어온 시각
Value	해당 시각에 들어온 사용자의 요청 배열
Value 배열의 각 원소	[자전거를 대여할 자전거 대여소 ID, 자전거를 반납할 자전거 대여소 ID, 자전거를 탈 시간(분)]

Example

{
  "0":[[13, 14, 51], [2, 14, 34], [8, 13, 31], [10, 20, 38]],
  "2":[[19, 16, 7]], // 카카오 T 바이크 서비스 시작 2분 후에 ID가 19인 자전거 대여소에서 자전거를 빌리고 7분 뒤 ID가 16인 자전거 대여소에 반납
  "3":[[15, 21, 51]],
  …(이하 생략)
}

시나리오 1(HotPlace 없음)
- 1일 전: 다운로드
- 2일 전: 다운로드
- 3일 전: 다운로드
시나리오 2
- 1일 전: 다운로드
- 2일 전: 다운로드
- 3일 전: 다운로드

점수

점수는 시나리오별로 다음과 같이 계산됩니다.

구분	공식
달성률 점수	`(성공한 요청 수 - S’) / (S - S’) x 100`
효율성 점수	`(효율성 점수: (T - t) / T x 100`
총점	`(달성률 점수) X 0.95 + (효율성 점수) X 0.05`와 `0` 중 더 큰 값

※ S = (사용자의 총 대여 요청 수)
※ S’ = (트럭이 아무것도 안 했을 때 시나리오에서 성공하는 요청 수)
※ T = (모든 트럭이 쉬지 않고 계속 달린다고 가정할 때 모든 트럭이 달린 거리의 합)
※ t = (지원자의 시뮬레이션에서 모든 트럭이 달린 거리의 합)

구분	시나리오 1	시나리오 2
`S`	1428	10829
`S’`	1077	9142
`T`	3600(km)	7200(km)

참고

완료 후 작성한 코드를 업로드해야 합니다. 여러 파일일 경우 zip으로 압축하여 업로드한다. 시험 시간 내에 코드를 제출하지 않으면 획득한 점수는 무시됩니다.
각 시나리오의 총점은 모든 시도 중 최고 점수로 반영됩니다.
총점은 시뮬레이션에서 카카오 T 바이크 서버의 상태가 finished가 될 때 산출됩니다.
최종 점수는 (시나리오 1에서 획득한 총점) x (시나리오 1의 배점 가중치) + (시나리오 2에서 획득한 총점) x (시나리오 2의 배점 가중치)로 부여됩니다. 단, 배점 가중치는 지원자에게 공개하지 않습니다.
리더보드에 나오는 점수는 시나리오별 배점 가중치가 고려되지 않은 점수입니다. 즉, 리더보드의 점수는 (시나리오 1에서 획득한 총점) + (시나리오 2에서 획득한 총점)과 같습니다.

예시

서비스 지역

2X2 크기의 서비스 지역이 주어질 때, 각 자전거 대여소가 초기에 보유한 자전거 대수가 다음과 같다고 합시다. 자전거 대수는 자전거 대여소의 ID 순으로 나열하였습니다.

[2, 1, 1, 0]

※ 실제 주어지는 데이터에서는 모든 자전거 대여소가 초기에 같은 수의 자전거를 갖고 있으나, 본 예시에서는 이해를 돕기 위해 변형을 주었습니다.

이를 그림으로 표현하면 다음과 같습니다.

사용자의 요청

사용자의 요청이 다음과 같이 주어진다고 합시다.

10시 00분: [[3, 0, 10]]
10시 01분: [[1, 3, 1], [1, 4, 15]]
10시 02분: [[0, 3, 2], [3, 1, 4], [0, 3, 1]]
10시 03분: [[1, 3, 5]]

각 원소는 각 사용자가 보낸 요청으로, [자전거를 대여할 자전거 대여소 ID, 자전거를 반납할 자전거 대여소 ID, 자전거를 탈 시간(분 단위)]를 뜻합니다. 예를 들어 [3, 0, 10]은 ID가 3인 자전거 대여소에서 자전거를 대여하여, 10분 동안 자전거를 탄 후 ID가 0인 자전거 대여소에 자전거를 보관하겠다는 의미입니다.

예시 1 – 죠르디가 아무 일도 하지 않음

죠르디가 아무 일도 하지 않으면(즉, 트럭이 아무 일도 하지 않으면) 결과는 다음과 같습니다.

10시 00분

각 자전거 대여소에 있는 자전거 수: [2, 1, 1, 0]

자전거 반납: 반납된 자전거가 없습니다.
자전거 대여:
· 요청 1 [3, 0, 10]: ID 3인 자전거 대여소에는 자전거가 없으므로, 이 요청은 취소됩니다.
트럭 운행: 트럭은 아무 일도 하지 않습니다.

취소된 요청 수: 1
트럭이 움직인 거리: 0m
대여 중인 자전거: 없음

10시 01분

각 자전거 대여소에 있는 자전거 수: [2, 1, 1, 0]

자전거 반납: 반납된 자전거가 없습니다.
자전거 대여:
· 요청 2 [1, 3, 1]: ID 1인 자전거 대여소는 자전거가 1대 있으므로, 이 요청은 수락됩니다.
· 요청 3 [1, 4, 15]: 요청 2에 의해 ID 1인 자전거 대여소에는 자전거가 없으므로, 이 요청은 취소됩니다.
트럭 운행: 트럭은 아무 일도 하지 않습니다.

취소된 요청 수: 2
트럭이 움직인 거리: 0m
대여 중인 자전거:
    * 요청 2, 10시 02분에 ID 3인 자전거 대여소에 반납 예정

10시 02분

각 자전거 대여소에 있는 자전거 수: [2, 0, 1, 0]

자전거 반납:
· 요청 2의 자전거가 ID가 3인 자전거 대여소로 반납됩니다.
자전거 대여:
· 요청 4 [0, 3, 2]: ID 0인 대여소에는 자전거가 2대 있으므로, 이 요청은 수락됩니다.
· 요청 5 [3, 1, 4]: 반납에 의해 ID 3인 대여소에는 자전거가 1대 생겼으므로, 이 요청은 수락됩니다.
· 요청 6 [0, 3, 1]: ID 0인 대여소에는 자전거가 1대 있으므로, 이 요청은 수락됩니다.
트럭 운행: 트럭은 아무 일도 하지 않습니다.

취소된 요청 수: 2
트럭이 움직인 거리: 0m
대여 중인 자전거:
    * 요청 4, 10시 04분에 ID 3인 자전거 대여소에 반납 예정
    * 요청 5, 10시 06분에 ID 1인 자전거 대여소에 반납 예정
    * 요청 6, 10시 03분에 ID 3인 자전거 대여소에 반납 예정

10시 03분

각 자전거 대여소에 있는 자전거 수: [0, 0, 1, 0]

자전거 반납:
· 요청 6의 자전거가 ID가 3인 자전거 대여소로 반납됩니다.
자전거 대여:
· 요청 7 [1, 3, 5]: ID 1인 자전거 대여소에는 자전거가 없으므로, 이 요청은 취소됩니다.
트럭 운행: 트럭은 아무 일도 하지 않습니다.

취소된 요청 수: 3
트럭이 움직인 거리: 0m
대여 중인 자전거:
    * 요청 4, 10시 04분에 ID 3인 자전거 대여소에 반납 예정
    * 요청 5, 10시 06분에 ID 1인 자전거 대여소에 반납 예정

예시 2 – 죠르디가 트럭을 운행함

죠르디가 10:00부터 트럭을 운행해, 트럭이 ID가 2인 자전거 대여소에 있는 자전거 한 대를 ID가 1인 자전거 대여소로 이송하면 결과는 다음과 같습니다.

10시 00분

각 자전거 대여소에 있는 자전거 수: [2, 1, 1, 0]

자전거 반납: 반납된 자전거가 없습니다.
자전거 대여:
· 요청 1 [3, 0, 10]: ID 3인 자전거 대여소에는 자전거가 없으므로, 이 요청은 취소됩니다.
트럭 운행:
· 10시 00분 00초 ~ 10시 00분 06초: ID 0 자전거 대여소에서 ID 2 자전거 대여소로 이동합니다.
· 10시 00분 06초 ~ 10시 00분 12초: ID 2 자전거 대여소에서 자전거를 한 대 싣습니다.
· 10시 00분 12초 ~ 10시 00분 24초: ID 2 자전거 대여소에서 ID 1 자전거 대여소로 이동합니다.
· 10시 00분 24초 ~ 10시 00분 30초: ID 1 자전거 대여소에 자전거를 한 대 내립니다.

취소된 요청 수: 1
트럭이 움직인 거리: 300m
대여 중인 자전거: 없음

10시 01분

각 자전거 대여소에 있는 자전거 수: [2, 2, 0, 0]

자전거 반납: 반납된 자전거가 없습니다.
자전거 대여:
· 요청 2 [1, 3, 1]: ID 1인 자전거 대여소는 자전거가 2대 있으므로, 이 요청은 수락됩니다.
· 요청 3 [1, 4, 15]: ID 1인 자전거 대여소에는 자전거가 1대 있으므로, 이 요청은 수락됩니다.
트럭 운행: 트럭은 아무 일도 하지 않습니다.

취소된 요청 수: 1
트럭이 움직인 거리: 300m
대여 중인 자전거:
    * 요청 2, 10시 02분에 ID 3인 자전거 대여소에 반납 예정
    * 요청 3, 10시 16분에 ID 4인 자전거 대여소에 반납 예정

10시 02분

각 자전거 대여소에 있는 자전거 수: [2, 0, 0, 0]

자전거 반납:
· 요청 2의 자전거가 ID가 3인 자전거 대여소로 반납됩니다.
자전거 대여:
· 요청 4 [0, 3, 2]: ID 0인 자전거 대여소에는 자전거가 2대 있으므로, 이 요청은 수락됩니다.
· 요청 5 [3, 1, 4]: 반납에 의해 ID 3인 자전거 대여소에는 자전거가 1대 생겼으므로, 이 요청은 수락됩니다.
· 요청 6 [0, 3, 1]: ID 0인 대여소에는 자전거가 1대 있으므로, 이 요청은 수락됩니다.
트럭 운행: 트럭은 아무 일도 하지 않습니다.

취소된 요청 수: 1
트럭이 움직인 거리: 300m
대여 중인 자전거:
    * 요청 3, 10시 16분에 ID 4인 자전거 대여소에 반납 예정
    * 요청 4, 10시 04분에 ID 3인 자전거 대여소에 반납 예정
    * 요청 5, 10시 06분에 ID 1인 자전거 대여소에 반납 예정
    * 요청 6, 10시 03분에 ID 3인 자전거 대여소에 반납 예정

10시 03분

각 자전거 대여소에 있는 자전거 수: [0, 0, 0, 0]

자전거 반납:
· 요청 6의 자전거가 ID가 3인 자전거 대여소로 반납됩니다.
자전거 대여:
· 요청 7 [1, 3, 5]: ID 1인 자전거 대여소에는 자전거가 없으므로, 이 요청은 취소됩니다.
트럭 운행: 트럭은 아무 일도 하지 않습니다.

취소된 요청 수: 2
트럭이 움직인 거리: 300m
대여 중인 자전거:
    * 요청 3, 10시 16분에 ID 4인 자전거 대여소에 반납 예정
    * 요청 4, 10시 04분에 ID 3인 자전거 대여소에 반납 예정
    * 요청 5, 10시 06분에 ID 1인 자전거 대여소에 반납 예정

API REFERENCE

HTTPS로 통신합니다.

초당 10회가 넘는 API 호출은 서버가 응답하지 않을 수 있습니다.
BASE URL: 테스트가 종료되어 현재는 제공되지 않으며 추후 준비되면 제공 예정입니다.
리더보드 URL: 테스트가 종료되어 현재는 제공되지 않습니다.

  주어진 X-Auth-Token 앞 6자리로 점수를 확인할 수 있다.
  리더보드는 Chrome 브라우저에 최적화되어 있다.

Response Codes

API를 성공적으로 호출할 경우 200 코드를 반환하고, 그 외의 경우에는 아래의 코드를 반환합니다.

Response Code	Description
200 OK	성공
400 Bad Request	Parameter가 잘못됨 (범위, 값 등)
401 Unauthorized	인증을 위한 Header가 잘못됨
500 Internal Server Error	서버 에러, 채팅으로 문의 요망

Start API

문제를 풀기 위한 key를 발급합니다. Start API를 실행하면 파라미터로 전달한 문제 번호에 맞게 각 자전거 대여소 및 트럭에 대한 정보를 초기화합니다.

Request

POST /start
X-Auth-Token: {X-Auth-Token}
Content-Type: application/json

Header

Name	Description
X-Auth-Token	문제에서 발급되는 응시자 식별 토큰 값

Parameter

Name	Type	Description
problem	Integer	시나리오 번호 (1 <= problem <= 2)

Example

curl -X POST {BASE_URL}/start \
     -H 'X-Auth-Token: {X_AUTH_TOKEN}' \
     -H 'Content-Type: application/json' \
     -d '{
         "problem": 1
     }'

Response

Key

Key	Type	Description
auth_key	String	Start API 를 통해 발급받은 key, 이후 문제 풀이에 진행되는 모든 API에 이 key를 사용
problem	Integer	선택한 시나리오 번호
time	Integer	현재 카카오 T 바이크 서비스에서의 시각 (0부터 시작)

Example

{
  "auth_key": "1fd74321-d314-4885-b5ae-3e72126e75cc",
  "problem": 1,
  "time": 0
}

Locations API

현재 카카오 T 바이크 서비스 시각에 각 자전거 대여소가 보유한 자전거 수를 반환합니다.

Request

GET /locations
Authorization: {auth_key}
Content-Type: application/json

Header

Name	Description
Authorization	Start API 에서 발급받은 auth_key

Example

curl -X GET {BASE_URL}/locations \
     -H 'Authorization: {AUTH_KEY}' \
     -H 'Content-Type: application/json'

Response

Key

Key	Type	Description
locations	Array of Location	각 자전거 대여소의 ID, 보유하고 있는 자전거 수에 대한 정보를 담은 배열

Example

{
  "locations": [
    { "id": 0, "located_bikes_count": 3 },
    { "id": 1, "located_bikes_count": 3 },
    ...
  ]
}

Trucks API

현재 카카오 T 바이크 서비스 시각에 각 트럭의 위치와 싣고 있는 자전거 수를 반환합니다.

Request

GET /trucks
Authorization: {auth_key}
Content-Type: application/json

Header

Name	Description
Authorization	Start API 에서 발급받은 auth_key

Example

curl -X GET {BASE_URL}/trucks \
     -H 'Authorization: {AUTH_KEY}' \
     -H 'Content-Type: application/json'

Response

Key

Key	Type	Description
trucks	Array of Truck	각 트럭의 ID, 현재 위치, 싣고 있는 자전거 수에 대한 정보를 담은 배열

Example

{
    "trucks": [
        { "id": 0, "location_id": 0, "loaded_bikes_count": 0 },
        { "id": 1, "location_id": 0, "loaded_bikes_count": 0 },
        ...
    ]
}

Simulate API

현재 시각 ~ 현재 시각 + 1분까지 각 트럭이 행할 명령을 담아 서버에 전달합니다. 호출 시 서버에서는 다음과 같은 일이 진행됩니다.

카카오 T 바이크 서버의 상태가 in_progress로 변경됩니다.
서버 내부에 기록된 returns(자전거 반납 예정 Hash)를 확인하여 각 자전거 대여소가 가진 자전거 수를 늘립니다.
서버 내부에 기록된 requests(자전거 대여 예정 Hash)를 확인하여 각 자전거 대여소가 가진 자전거 수를 줄입니다.
자전거 대여 요청이 취소될 경우 요청 취소수를 1 증가시켜 서버에 저장합니다.
자전거 대여 요청이 성공할 경우 현재 시각 + 대여 시간을 key, 반납할 자전거 대여소 ID를 value로 하여 returns에 저장합니다.
매개 변수로 받은 트럭의 명령들을 수행합니다. 이때 ID가 낮은 트럭의 명령부터 순서대로 처리합니다.
· 명령이 자전거 상차 또는 자전거 하차일 경우 트럭이 가진 자전거 수를 증가 또는 감소시킵니다.
– 자전거가 없는 대여소에서 상차를 하거나, 트럭에 자전거가 없는데 하차를 하
려는 명령은 무시됩니다. 이때 명령은 무시되지만 시간은 정상적으로 각기 6초
가 소비됩니다.
· 명령이 상, 하, 좌, 우 이동일 경우 트럭의 이동 거리를 100m 증가시키고, 트럭의 위치를 기록합니다.
– 서비스 지역을 벗어나는 이동 명령은 무시됩니다. 이때 명령은 무시되지만 시간
은 정상적으로 각기 6초가 소비됩니다.
· 매개 변수로 받은 명령 중 1분 내에 할 수 있는 명령까지만 수행합니다. 즉, 한 번의 simulate 요청 안에서 각 트럭에게 내릴 수 있는 명령 수는 최대 10개이고, 그 이상의 명령은 실행되지 않습니다.
Simulate 요청이 성공하면 카카오 T 바이크 서버의 상태가 ready로 변경되고, 현재 시각이 1분 증가합니다.
· 한 시나리오에서 Simulate 요청이 720번 성공되면 카카오 T 바이크 서버의 상태는 ready가 아닌 finished로 변경되며, 더 이상 이 시나리오에서는 Simulate API를 호출할 수 없습니다. 다시 같은 시나리오를 Simulate 하고 싶다면 Start API를 이용해 새로운 AUTH_KEY를 발급받아야 합니다.

Request

PUT /simulate
Authorization: {auth_key}
Content-Type: application/json

Header

Name	Description
Authorization	Start API 에서 발급받은 auth_key

Parameter

Name	Type	Description
commands	Array of Command	각 트럭이 `현재 시각 ~ 현재 시각 + 1분` 까지 수행할 명령

※ 트럭의 명령

0: 6초간 아무것도 하지 않음
1: 위로 한 칸 이동
2: 오른쪽으로 한 칸 이동
3: 아래로 한 칸 이동
4: 왼쪽으로 한 칸 이동
5: 자전거 상차
6: 자전거 하차

예를 들어, `{ "truck_id": 0, "command": [2, 5, 4, 1, 6] }`으로 명령을 하면 ID가 0인 트럭은 아래와 같이 운행한다.
1) 오른쪽으로 한 칸 이동
2) 자전거 1대 상차
3) 왼쪽으로 한 칸 이동
4) 위로 한 칸 이동
5) 자전거 1대 하차

Example

curl -X PUT {BASE_URL}/simulate \
     -H 'Authorization: {AUTH_KEY}' \
         -H 'Content-Type: application/json' \
     -d '{
       "commands": [
         { "truck_id": 0, "command": [2, 5, 4, 1, 6] }
         ...
       ]
     }'

Response

Key

Key	Type	Description
status	String	현재 카카오 T 서버의 상태
time	Integer	현재 시각 (요청 시각에서 1분 경과)
failed_requests_count	Integer	실패한 요청 수
distance	Float	모든 트럭이 현재까지 이동한 거리의 총합(km 단위)

Example

{
  "status": "ready",
  "time": 1,
  "failed_requests_count": 5,
  "distance": 1.2,
}

Score API

해당 Auth key로 획득한 점수를 반환합니다. 점수는 높을수록 좋습니다. 카카오 T 바이크서버의 상태가 finished가 아닐 때 본 API를 호출하면 response의 score는 무조건 0.0입니다.

Request

GET /score
Authorization: {auth_key}
Content-Type: application/json

Header

Name	Description
Authorization	Start API 에서 발급받은 auth_key

Example

curl -X GET {BASE_URL}/score \
     -H 'Authorization: {AUTH_KEY}' \
     -H 'Content-Type: application/json'

Response

Key

Key	Type	Description
score	Float	획득한 점수

Example

{
  "score": 75.7
}

문제 접근 방법

문제는 난이도에 따라 두 가지의 시나리오가 제시되었으며 지문에 제시된 점수 산출 공식을 통해 점수가 달성률과 효율성으로 구분되고, 달성률을 높이려면 자전거 대여 성공 건수를 늘려야 하고 효율성을 높이려면 트럭의 이동거리를 줄여야 한다는 문제 풀이의 핵심을 빠르게 파악하는 것이 중요합니다.

또한 달성률과 효율성의 점수 가중치가 95 : 5이므로 트럭의 이동거리를 줄이는 것보다는 대여 성공 건수를 늘리는 데 더 신경을 써야 한다는 점을 이해해야 합니다. 그리고 달성률의 목표가 최소한 트럭을 아무것도 이동하지 않았을 때보다 더 높은 대여 성공 건수를 보여야 점수를 획득할 수 있다는 점을 파악한 로직을 구현한 후 수시로 simulate API 호출을 통해 원하는 성공 건수를 달성했는지 점검하면서 로직을 튜닝해 나가는 식으로 진행해야 합니다.

추가로 어느 정도 로직의 완성도가 높아지는 시점에서는 수시로 리더보드의 점수를 확인하면서 자신의 로직의 완성도가 어느 정도인 지를 확인해 보는 것도 필요합니다.

시나리오 1은 서비스 지역을 5×5 크기로 작게 제한하고 트럭은 5개, 자전거는 100대로 제한하였고 사용자의 선호 대여소를 고려하지 않고 어렵지 않은 접근 방법으로도 어느 정도 자전거 대여 성공 건수를 늘릴 수 있도록 환경을 제시하였으며 목표 자전거 대여 건수는 최소 1,077 건보다는 많아야 합니다.

합격자 기준 자전거 대여 성공 건수는 다음과 같았습니다.

최소 대여 성공 건수 – 1,077건
최대 대여 성공 건수 – 1,384건
평균 대여 성공 건수 – 1,268건

시나리오 2는 서비스 지역을 60×60 크기로 늘리고 트럭은 10대, 자전거는 10,800대로 늘렸고 더불어 과거 대여 히스토리 데이터를 통해 사용자의 선호 대여소를 고려하여 효율적인 로직을 설계해야 점수를 받을 수 있도록 환경을 제시하였으며 목표 자전거 대여 건수는 최소 9,142 건보다는 많아야 합니다.
합격자 기준 자전거 대여 성공 건수는 다음과 같았습니다.

최소 대여 성공 건수 – 9,057건
최대 대여 성공 건수 – 10,784건
평균 대여 성공 건수 – 9,652건

합격자 중 시나리오 1 문제 합격자 중 54.4%의 지원자가 시나리오 2에서 유의미한 점수를 획득하였습니다.

다양한 문제 풀이 방법

카카오 T 바이크 관리 시뮬레이션 문제는 다음과 같이 다양한 방법으로 접근할 수 있습니다.

Nothing

트럭에 대해 아무런 작업 요청도 부과하지 않는 방법
트럭을 움직이지 않고 바이크 대여 요청으로만 카카오 T 바이크 시스템을 운영합니다. 4 시간마다 선호도 분포가 바뀌기 때문에 각 위치에 바이크들이 어느 정도 재배치되는 현상이 발생할 것으로 예상됩니다.

Most-to-least

가장 많은 수의 바이크를 가진 위치에서 가장 적은 수의 바이크를 가진 위치로 바이크를 옮기는 방법
사용자 대여 요청이 없을수록 바이크가 많이 쌓여 있습니다. 그러므로 바이크가 가장 많이 쌓여 있는 위치의 바이크를 바이크가 가장 적은 위치 즉, 사용자 대여 요청이 많이 들어오는 위치로 옮기는 방법이 좋을 것으로 판단됩니다. 하지만, 이 방법은 트럭의 불필요한 이동이 많이 생깁니다.

Nearby-one

가장 적은 수의 바이크를 가진 위치로 주변의 남는 바이크를 1개 이동하는 방법
위 Most-to-least 방법은 트럭의 이동시간은 고려하지 않는 방법입니다. 트럭의 이동에는 시간이 소요되기 때문에 트럭은 가능한 짧은 거리를 움직이는 것이 좋습니다. 그러므로 가장 적은 수의 바이크를 가진 위치(바이크 수요가 많은 위치) 주위에서 남는 바이크 하나를 가져오는 방법이 좋을 것으로 판단됩니다. 하지만 이 방법은 충분한 수의 바이크를 공급하지 못할 수 있습니다.

Nearby-some

가장 적은 수의 바이크를 가진 위치로 주변의 남는 바이크를 여러 개(바이크 수의 1/2) 이동하는 방법
위 방법에서 옮길 바이크의 개수만 증가시킨 방법입니다. 바이크가 여유 있는 경우에는 1대보다 더 많은 바이크를 옮기면 더 효율적인 운영이 가능할 것으로 판단됩니다. 이 방법은 트럭에 바이크가 많으면 서비스에 사용되는 바이크 수가 부족할 수도 있습니다. 하지만 트럭의 이동을 효율적으로 함과 동시에 적절한 수의 바이크를 옮길 수 있어, 좋은 방안으로 생각됩니다.

On-the-way

바이크가 대여된 순간, 트럭을 하나 선정하여 대여 위치로 이동하면서 남는 바이크를 대여된 위치로 이동시키는 방법
이 방법은 다른 방법들과는 다르게 바로 목적지로 트럭이 움직인다는 장점이 있습니다. 랜덤한 트럭을 선택하여 트럭의 위치에서 대여 위치로 최단 경로로 이동하면서 3개 이상의 바이크를 가진 위치를 만나면 그 바이크의 1/2를 트럭에 싣고, 바이크의 개수가 0인 위치를 만나면 1개를 내려놓고 최종적으로 트럭에 남은 모든 바이크를 대여 위치에 내려놓습니다. 이 방법은 트럭의 불필요한 이동을 최소화하고, 이동하면서 바이크가 없는 곳에 바이크를 공급하는 장점이 있습니다.
하지만 이 방법은 랜덤으로 트럭을 고른다는 점과 이동 중에 바이크를 모두 내려놓는다면, 대여 위치에 바이크를 보충 못하는 상황이 발생할 수 있습니다.

Others

각 트럭이 영역을 나눠서 해당 영역 내를 주기적으로 순회하면서 남는 바이크를 부족한 위치로 이동시키는 방법
트럭을 항상 가장 선호도가 높은 상위 10개 지점에 배치하는 방법
바이크의 부족 여부를 남은 절대 바이크 수로 판단하지 않고, 과거 히스토리를 바탕으로 판단하는 방법

마치며

이번 테스트를 위해 제작되었던 API 서버는 테스트 종료와 함께 비공개로 전환되어 공개되지 않습니다. 코딩 테스트 플랫폼인 프로그래머스에서 테스트 가능한 환경을 제공하오니 참고 부탁 드립니다.

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

온라인 감독 환경에서 처음으로 실시된 이번 코딩 테스트가 걱정과 달리 별다른 문제 없이 잘 마무리되어 다행으로 생각합니다.

테스트에 참여하신 모든 지원자분들께 유익하고 재미있는 문제가 되었기를 희망하며 감사의 말씀 전합니다.

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

career, coding, coding test, kakao, new-krew, recruitment, tech, test

shaun.seon

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

CS 테스트

코딩 테스트

✔️ 코딩테스트 Tip

카카오 T 바이크 관리 시뮬레이션

트럭 운영 목표

서비스 지역 및 제약 사항 설명

시나리오

점수

예시

API REFERENCE

Response Codes

Start API

Locations API

Trucks API

Simulate API

Score API

문제 접근 방법

다양한 문제 풀이 방법

마치며

Latest Posts

제5회 Kakao Tech Meet에 초대합니다!

테크밋 다시 달릴 준비!

OROR Forge: Figma to Code 도구 제작기 (2) 실전용으로 만들기

Connect with Kakao Tech

About Tech

About Channels

Family Sites

Copyright © Kakao Corp. All rights reserved.

shaun.seon

태그

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

CS 테스트

코딩 테스트

✔️ 코딩테스트 Tip

카카오 T 바이크 관리 시뮬레이션

트럭 운영 목표

서비스 지역 및 제약 사항 설명

시나리오

점수

예시

API REFERENCE

Response Codes

Start API

Locations API

Trucks API

Simulate API

Score API

문제 접근 방법

다양한 문제 풀이 방법

마치며

Latest Posts

제5회 Kakao Tech Meet에 초대합니다!

테크밋 다시 달릴 준비!

OROR Forge: Figma to Code 도구 제작기 (2) 실전용으로 만들기

Connect with Kakao Tech

About Tech

About Channels

Family Sites