카카오, 2022 여름 인턴십 코딩 테스트 5문제 해설 공개

카카오는 2022년 5월 7일에 실시된 여름 인턴십 코딩 테스트의 5문제에 대한 해설을 공개했다. 이번 테스트는 작년과 달리 시간이 1시간 늘어난 5시간 동안 진행되었으며, 모든 문제는 테스트 케이스를 모두 통과해야 점수를 받을 수 있고 부분 점수는 인정되지 않았다. 단, 일부 문제는 정확성과 효율성 테스트를 구분하여 효율적인 풀이에 추가 점수를 부여했다.

주요 문제별 풀이 전략은 다음과 같다. 문제 2번 '두 큐 합 같게 만들기'는 탐욕법이나 투 포인터 방식을 사용하여 큐의 경계를 이동시키며 합을 맞추는 방식으로 해결할 수 있다. 문제 3번 '코딩 테스트 공부'는 알고력과 코딩력 상태를 2차원 동적계획법(DP) 배열로 정의하여 목표 상태까지의 최단 시간을 구하거나, 그래프 모델링을 통해 다익스트라 알고리즘으로 해결할 수 있다. 문제 4번 '등산 코스 정하기'는 다익스트라 알고리즘을 변형하여 경로 가중치의 최댓값을 최소화하는 방식으로, 모든 출입구를 한 번의 알고리즘 실행에서 시작 정점으로 처리해 시간 복잡도를 줄인다. 문제 5번 '행렬과 연산'은 덱이나 링크드 리스트를 활용해 행과 열의 인덱스만 관리함으로써 실제 데이터 이동 없이 연산을 수행하고, 시간 복잡도를 O(NMQ)에서 O(NM+Q)로 개선한다.