2023 카카오모빌리티 2차 코딩테스트가 12/03 14:00 - 17:00에 진행되었다.
1차 코테가 모두를 놀라게 할 정도의 충격적인 (...) 난이도였기에, 2차는 난이도가 어떨지 궁금했다.
확실히 1차의 충격적인 난이도에 비해 변별력있게 나왔고, CS 문제 난이도도 나쁘지 않았다.
스스로 푼 풀이라 실제 정답과 다를 수 있다는 것에 유의...
Q1
사용된 알고리즘: DP
예상 난이도 (Solved.ac 기준): G4
보행으로 이동할 수 있는 최대 시간이 정해져있기에, 이를 활용한 이차원 DP를 설계하면 된다.하지만, (도보 - 대중교통), (도보 - 자전거) 가 나뉘어져 있기에, DP를 두 번 돌려야 한다.
대충...dp[a][x][y] -> 위 이동방법중 a번째 이동방법을 사용했을 때, 현재 x번째 구역에 도달하려고 하고 연속 누적 보행 시간이 y분일 때, 도착하기 위해 필요한 최소시간
이 되겠다.
설계만 하면 dp 점화식 자체는 큰 문제 없지만, 대중교통의 경우 -1이 나오면 필터링 해야하는 것에 유의.
Q2
사용된 알고리즘: 플로이드-워셜, 완전탐색
예상 난이도 (Solved.ac 기준): G3
구역이 50개이고, 2개의 센터를 설치해야 하니 모든 경우는 완전탐색으로 충분히 세울 수 있다.
그런데, 잘 생각해보면 어떤 구역에서 출발해서 도착할 수 있는 지점을 택하는건, 거리 d 이하의 모든 지점을 고르는 것과 같다.
따라서 최단거리를 구해야 하는데, 모든 구역이 센터가 될 수 있기에 단순히 All-Pair Shortest Path 를 구한 다음에 꺼내서 써먹으면 된다.
정점의 수가 충분히 적으니 플로이드 워셜로 밀자.
또한 잘 생각해보면, 두 센터 중 한군데에만 도달할 수 있는 구역이 있을테고, 두 센터 모두에 접근 가능한 구역이 있을 것이다.
이걸 잘 조율해서 최대 수용가능한 인원을 세보자.
- 한 군데에만 도달할 수 있는 구역의 경우, 어차피 모든 인원이 그 구역으로 가야한다.
- 두 군데 모두 도달할 수 있다면, 둘 중 남은 곳으로 가면 된다.
- 따라서, 일단 한 군데만 갈 수 있는 구역의 인원들만 이동시켜보자.
-> min(limit, x) + min(limit, y)
- 이렇게 되면, x 센터에서 추가적으로 수용가능한 인원은 max(0, limit - x) 명, y 센터의 경우에는 max(0, limit - y) 라고 할 수 있다.
- 따라서, 최종적으로는 min(limit, x) + min(limiy, y) + min(xy, max(0, limit - x) + max(0, limit - y)) 명이 된다.
따라서, 우리는 x 구역에 방문 가능한 지점을 기록하고, y 구역에 방문 가능한 지점을 기록한 다음에, 둘 모두 방문 가능한 총 인원/두 구역 각각에 방문 가능한 인원을 기록하고 위 식을 때려박으면 된다.
차근차근 접근하면 해결할 수 있다.
CS
- 적당한 난이도로 나왔다. 면접에 필수적인 문제들 중심인듯?
- DB, 알고리즘, 자료구조, OS, Network 분야로 출제되었고, 난이도는 올해 카카오 2차와 라인 CS 와 같은 괴랄한 난이도는 아니었다.
총평
- 1차 3문제와 2차 2문제를 그냥 합쳐서 코테를 한 번 보면 되는거 아닐까?