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

KENNETH

6년 ago

지난 10월 6일(토) 2019 블라인드 공채 오프라인 2차 코딩테스트가 진행되었습니다. 작년에는 8시간 동안 온라인으로 진행한 것과는 달리 오프라인으로 5시간 동안 치러졌는데요, 어떤 의도로 출제하였는지 살펴보겠습니다.

작년 2차 코딩테스트 회고

작년 문제 출제 의도를 기억하시는지요?

온라인 2차 코딩 테스트 문제 출제 위원회에서는,
- 탄탄한 기본기를 바탕으로 새로운 것을 빠르게 습득하는 역량
- 요구사항을 꼼꼼하게 분석하고, 트레이드오프를 고려하여 디자인하여 구현하는 역량
- 결과를 모니터링하며 점진적으로 개선해나가는 역량
을 테스트할 수 있도록 2차 문제에 녹여내고자 하였습니다.

작년 문제에는 매우 많은 장치가 숨겨져 있었으나 정작 요구사항을 그대로 구현하기만 해도 합격선인 8만 점을 얻기에는 충분했었습니다.

그리하여 올해는 시스템 디자인 역량을 좀 더 중점적으로 평가하고자 하였습니다.

엘리베이터 시뮬레이션

올해 오프라인 2차 테스트 문제는 다수의 엘리베이터(1대~4대)를 제어하는 시스템을 구현하는 것입니다. 핵심 구현에 집중할 수 있도록 엘리베이터 동작 및 상태는 서버에서 관리하고, 서버와 통신은 작년과 같이 REST API 및 JSON 포맷으로 주고받도록 하였습니다.

지원자는 주어진 빌딩별 승객 트래픽을 분석하여 가정 적합한 엘리베이터 제어 알고리즘을 구현해야 합니다.

지원자가 제어할 엘리베이터 시스템은 다음과 같습니다.

Timestamp (시간)

엘리베이터 시스템은 가상의 시간을 사용하며 timestamp라 부른다.
Timestamp는 0부터 시작하고 엘리베이터에 명령을 내릴 때마다 1씩 증가한다.

Call (승객)

승객이 엘리베이터 탑승을 위해 보내는 요청, 방향 버튼을 누르는 행위를 call이라 표현한다. Call에는 탑승하려는 층과 목적지 층이 포함된다.
어떤 승객을 태우거나 내려줄지도 엘리베이터 제어 시스템이 결정해야 한다. 승객은 스스로 타거나 내리지 않는다.
내리려는 층과 다른 층에 승객을 내려주면 다시 엘리베이터를 타기 위해 대기한다.

엘리베이터

엘리베이터는 여러 대가 존재하며 모두 사용할 수도 있고 일부만 사용해도 된다.
엘리베이터에 명령을 내려 각각의 엘리베이터를 층을 이동하거나 멈추고, 문을 열 거나 닫고, 승객을 태우거나 내려 줄 수 있다.
엘리베이터는 정원이 있어 정해진 수 이상의 승객을 태울 수 없다.
엘리베이터에는 현재 상태를 표현하는 status가 있으며, 값으로는 STOPPED, OPENED, UPWARD, DOWNWARD가 있다.
사용할 수 있는 명령은 다음과 같다.

명령	설명
`STOP`	엘리베이터를 멈춘다. 현재 층에 머무르기 원하는 경우 `STOP` 명령을 통해 머무를 수 있다.
`UP`	엘리베이터를 한 층 올린다. 최상층인 경우 현재 층을 유지한다.
`DOWN`	엘리베이터를 한 층 내린다. 1층인 경우 1층을 유지한다.
`OPEN`	엘리베이터의 문을 연다. 엘리베이터의 문이 열린 상태를 유지하기 위해서는 `OPEN` 명령을 사용한다.
`CLOSE`	엘리베이터의 문을 닫는다.
`ENTER`	엘리베이터에 승객을 태운다.
`EXIT`	엘리베이터의 승객을 내린다. 목적지가 아닌 곳에서 내린 경우, OnCall API의 `calls`에 내린 층과 내린 시점의 timestamp로 변경되어 다시 들어가게 된다.

명령에 따른 status 전환을 그림과 표로 표현하면 아래와 같다.

문제의 특징 및 의도

엘리베이터 1대의 동작은 대부분 지원자에게 친숙할 것입니다. 우리가 실생활에서 자주 접하는 엘리베이터 알고리즘은 “collective control”, “elevator algorithm” 등으로 불리는데 아래와 같이 2가지 규칙으로 구성됩니다.

엘리베이터 내에 탑승객이 있거나 현재 진행 방향의 앞쪽에 같은 진행 방향으로 이동하고자 하는 승객이 있으면, 현재의 방향을 유지한다.
현재 진행 방향의 요청들을 전부 처리하고 나면, 반대 방향의 요청을 처리하기 위해 방향을 전환한다. 만약 반대 방향의 요청이 없다면 멈추어 요청을 기다린다.

간단하고 직관적인 알고리즘입니다. 운영체제 수업을 열심히 들은 학생이라면 디스크 스케줄링 알고리즘 중 하나인 look 알고리즘을 떠올릴 수도 있겠습니다.

반면, 복수의 엘리베이터를 제어하기 위해서는 추가로 승객의 요청을 어느 엘리베이터에 할당할 것인지를 결정해야 합니다. 얼핏 보면 간단해 보이는 이 요구사항의 추가로 시스템은 제법 복잡해지게 됩니다. 어느 엘리베이터에 승객을 할당하는 것이 효율적인지 비용 계산을 해야 하고, 승객이 어디에 탑승하고 있는지를 관리해야 합니다. 층별로 구역을 나누어 운행한다면(홀/짝, 고층/저층 분리 운영 등) 환승 기능도 구현해야 합니다.

1대의 엘리베이터 제어는 쉽고 간단해 보이지만, 3문제를 모두 풀기 위해서는 반드시 복수 엘리베이터를 제어해야 합니다. 또한 각 문제의 승객 패턴도 다르고, 승객 패턴에 따라 효율적으로 엘리베이터를 구성해야 합니다. 따라서 시스템 디자인 시 다양한 엘리베이터 알고리즘을 실험할 수 있도록 추상화 & 모듈화를 통해 변경에 유연하도록 디자인해야 합니다. 실제 내부 모의 검증 시에도 문제 요구사항 분석 없이 1대만 먼저 운행하는 식으로 시작한 피실험자의 경우, 여러 대를 제어하는 시스템으로 리팩토링하는 단계에서 시간을 너무 소모하여 시간 내에 문제를 다 풀지 못하는 경우가 속출하였습니다.

승객 트래픽 모델링

엘리베이터 요청은 크게 3가지로 분류할 수 있습니다. (빌딩의 입구는 1층이라고 가정) (참고: https://beta.vu.nl/nl/Images/werkstuk-boer_tcm235-91327.pdf)

incoming: 1층에서 특정 층으로 이동하는 요청
outgoing: 특정 층에서 1층으로 이동하는 요청
inter-floor: 1층을 제외한 층간 이동

이번 테스트에서는 총 3개의 빌딩을 제시했습니다.

첫 번째 어피치 맨션의 경우 5층 높이의 작은 맨션이고 총 요청은 6개입니다. 쉬운 문제를 통해 엘리베이터 시스템에 익숙해지고 API 연동을 해보는 몸풀기 문제라 할 수 있습니다.

두 번째 제이지 빌딩은 25층 건물에 요청은 200개입니다. 위의 3가지 타입의 요청이 적절히 섞여 있는 가장 일반적인 형태의 모델이라고 할 수 있습니다.

세 번째 라이언 타워는 25층 건물에 요청은 500개입니다. 라이언 타워는 승객의 패턴을 제공하고, 이에 맞는 효율적인 엘리베이터 분배 알고리즘을 구현하도록 유도한 문제입니다. 입구는 1층이고, 2층-12층은 개별 회사에 임대를 하고, 13층-25층은 카카오가 사용합니다. 따라서 2층-12층 내에서는 층간 이동이 거의 없는 반면, 13층-25층 사이에서는 층간 이동이 빈번합니다. 또한 13층에 카카오프렌즈샵이 위치하여 1층과 13층을 오가는 고객들이 많다는 상황을 설정하였습니다.

다양한 접근방법

FIFO

가장 쉬운 접근법입니다. 요청이 들어온 순서대로 태우고 목적지에 내려준 후 다음 요청을 처리하는 형태입니다. 어피치 맨션의 경우 이 접근으로도 쉽게 풀립니다만, 제이지 빌딩, 라이언 타워의 경우 각각 약 4000, 13000 timestamp로 좋은 점수를 받을 수 없습니다.

Collective control

위에서 설명한 collective control 알고리즘입니다. 가장 친숙한 동작 방식입니다. 1대만 사용했음에도 불구하고 제이지 빌딩에서 972의 timestamp를 기록할 정도로 효율적입니다. 라이언 타워의 경우 약 2000 timestamp를 기록할 수 있습니다.

다양한 전략들

이번 문제의 엘리베이터는 보통의 엘리베이터와 다른 점이 있습니다. 이 부분을 활용하면 고득점을 할 수 있는데요. 출제진도 예상하지 못한 다양한 접근 방법들이 나와 놀랐습니다. 어떤 것들이 있는지 살펴보겠습니다.

0번 엘리베이터를 주목해주세요. 3명의 승객을 태우고 올라가던 엘리베이터는 17층에서 승객 1명을 내려주고 내려가는 방향의 승객 2명을 태워 올라갑니다. 일반적인 알고리즘과는 다른 방식인데요. 힌트는 평가 방법에 있습니다. 평가 조건은 모든 승객을 목적 층으로 수송해야 하며 가장 마지막 승객이 목적 층에 하차하였을 때의 시간 기준으로 평가를 합니다. 따라서 엘리베이터 내에 공간이 충분하다면 문이 열린 김에 태워가는 것이, 방향 전환 후 다시 멈추고, 문을 열고, 탑승시키는 것보다 효율적입니다.

마찬가지로 승객의 요청이 들어왔을 때 바로 요청을 처리하지 않고 대기하는 지원자도 있었습니다. 승객을 태우기 위해 멈추고, 문을 열고, 닫고, 태우는 것이 모두 timestamp를 잡아먹기 때문에 충분히 기다렸다가 한꺼번에 태우는 것입니다. 또한 대기 중인 승객의 수에 따라 엘리베이터 이동 전략을 달리한 지원자도 있었습니다.

그리고 결정적으로 현실의 엘리베이터와 차이가 나는 부분이 있습니다. 바로 요청을 받을 때 목적 층을 사전에 알 수 있다는 것입니다. 이 정보를 토대로 엘리베이터에 승객을 가고자 하는 층별로 그룹화하여 탑승시킬 수 있습니다. 심지어 엘리베이터를 움직이기 전에 모든 승객의 요청을 다 수집한 후에 움직이기 시작한 지원자도 있었습니다.