2022년 카카오 여름 인턴십 코딩 테스트가 지난 5월 7일에 5시간에 걸쳐 진행되었습니다. 시간이 부족하여 문제를 풀지 못하는 아쉬움이 없도록 1시간을 늘려 테스트를 진행한 것이 작년과 조금 달라진 부분이었습니다.

이번 인턴 코딩 테스트는 총 5문제가 출제되었습니다. 모든 문제는 문제별 테스트 케이스를 모두 통과해야 해당 테스트 케이스 세트에 대한 점수를 얻을 수 있도록 하였고, 문제별 부분 점수는 인정되지 않았습니다. 단, 일부 문제는 정확성과 효율성 테스트 케이스를 구분하여 점수를 별도로 부여함으로써, 효율적으로 문제를 해결한 지원자들이 추가 점수를 얻을 수 있도록 하였습니다.

그럼 각 문제별 해설을 살펴보겠습니다.

문제 1번 - 성격 유형 검사하기

문제에서 제시하는 내용을 구현하면 되는 문제입니다.

해시나 배열을 이용하여 각 성격 유형별로 점수를 저장합니다.
해시나 조건문을 이용하여 각 설문지에서 선택한 대로 성격 유형에 점수를 부여합니다.
모든 문제에 대하여 각 성격 유형에 점수를 부여한 후, 적절한 for 문과 if 문으로 각 지표마다 어떤 성격 유형이 점수가 더 높은지 확인합니다.
- 점수가 같을 경우 사전순으로 빠른 성격 유형을 선택합니다.

문제 2번 - 두 큐 합 같게 만들기

문제에서 요구하는 것은 queue1과 queue2의 원소 합을 같게 만드는 것입니다. 처음 주어진 queue1의 합을 L, queue2의 합을 R이라고 했을 때, L과 R을 같게 만들기 위해서는 다음과 같은 탐욕법을 사용하여 해결할 수 있습니다.

L > R이라면, queue1의 원소를 queue2로 넘겨줍니다.
L < R이라면, queue2의 원소를 queue1로 넘겨줍니다.

위 방법이 왜 유효한지 간단하게 증명하면 다음과 같습니다.

앞에서 설명한 방식과 반대로 L > R인 상황에서 먼저 L을 증가시키고 R을 감소시키는 방법이 최적인 경우가 있다고 가정하겠습니다. 이 경우 L = R을 만들기 위해서는 언젠가 L을 감소시키고 R을 증가시켜야 하고, 결국 queue1의 원소를 queue2로 넘겨주는 동작은 반드시 필요합니다. queue2의 원소를 queue1으로 넘겨준 이후에 queue1의 원소를 queue2로 넘겨주든, 이 순서를 반대로 하든 결과는 동일하기 때문에, L > R인 상황에서 L을 감소시키는 방법은 항상 최적이 될 수 있습니다.

이때, 직접 큐(Queue) 자료구조를 이용하지 않고 단순히 배열을 큐로 사용하면 0번 원소를 지우는 과정에서 시간 초과가 발생할 수도 있습니다.

이 방법 이외에도, 각 큐의 원소를 실제로 이동시키지 않고 한 구간의 시작 위치와 끝 위치를 포인터로 지정하여 이동하는 투 포인터(Two Pointers) 방식의 풀이도 존재합니다.

먼저 queue1을 왼쪽, queue2를 오른쪽에 이어 붙이고 하나의 배열처럼 본다고 생각해 봅시다. 이 경우 각 큐에 pop 또는 insert 연산을 하는 것은 배열의 경계를 이동시키거나 맨 앞의 원소를 맨 뒤에 이동시키는 연산을 하는 것이라고 볼 수 있으므로, 각 큐는 이렇게 정의한 배열에서 연속된 구간의 원소로만 이루어진다고 생각할 수 있습니다. 이 상황에서 queue1의 시작과 끝을 나타내는 두 포인터를 적절히 이동시키는 것입니다.

각 큐의 원소의 합은 (L + R) / 2가 되어야 하므로, queue1의 두 포인터 내에 있는 모든 원소의 합이 (L + R) / 2보다 작을 땐 끝 위치를 가리키는 포인터를 이동시키고 (L + R) / 2보다 클 땐 시작 위치를 가리키는 포인터를 이동시키면 됩니다.

이때, 전체 배열의 길이가 2n이므로, 한 포인터 당 최대 2n번의 이동이 필요합니다. 따라서, 총 4n만큼의 작업을 수행한 뒤에도 두 큐의 합을 같게 만들지 못했다면 그 이후에는 이미 탐색했던 구간을 다시 탐색하는 것이므로 의미가 없습니다. 이 경우에는 -1을 반환합니다.

문제 3번 - 코딩 테스트 공부

주어진 모든 문제를 풀 수 있는 알고력과 코딩력을 가진다는 말은, 주어진 problems 배열에서 가장 높은 req_alp와 req_cop을 각각 알고력과 코딩력으로 가지는 것과 동일합니다. 따라서, 해결해야 하는 문제는 (초기 알고력, 초기 코딩력) 상태에서 시작해 (목표 알고력, 목표 코딩력) 상태에 도달하는 최단 시간을 구하는 문제입니다.

이때, 목표 알고력을 넘는 알고력이나 목표 코딩력을 넘는 코딩력은 구현 방법에 따라 시간 초과나 세그먼트 폴트와 같이 예상치 못한 런타임 오류를 일으킬 수 있습니다. 목표 알고력을 넘는 알고력은 목표 알고력으로, 목표 코딩력을 넘는 코딩력은 목표 코딩력으로 계산하도록 처리하는 것이 안전한 방법입니다.

이 문제는 2차원 동적계획법(DP)으로 풀이가 가능합니다. DP 배열을 아래와 같이 정의합니다.

dp[i][j] : (알고력 i, 코딩력 j) 상태에 도달하는 데 필요한 최단 시간

이렇게 DP 배열을 정의하면 문제에서 요구하는 답은 dp[목표 알고력][목표 코딩력]입니다. dp[초기 알고력][초기 코딩력] = 0으로 기저 사례를 잡고 나머지 DP 배열의 값은 무한(적당히 큰 값)으로 초기화한 후 다음과 같은 방법으로 DP 배열을 업데이트 합니다.

알고리즘을 공부하여 알고력을 1 높이는 경우:
dp[i+1][j] = min(dp[i+1][j], dp[i][j]+1)
코딩을 공부하여 코딩력을 1 높이는 경우:
dp[i][j+1] = min(dp[i][j+1], dp[i][j]+1)
문제 하나를 선택하여 알고력과 코딩력을 높이는 경우:
dp[i+alp_rwd][j+cop_rwd] = min(dp[i+alp_rwd][j+cop_rwd], dp[i][j]+cost) (단, i >= alp_req이고 j >= cop_req)

초기 알고력 <= i <= 목표 알고력, 초기 코딩력 <= j <= 목표 코딩력인 모든 (i, j)에 대해서 dp[i][j] 값을 업데이트해야 하므로, 시간 복잡도는 O(목표 알고력 * 목표 코딩력 * (problems 배열의 길이))가 됩니다.

이 방법 이외에도, 그래프로 모델링하여 최단 거리를 찾는 문제(다익스트라 알고리즘 사용)로 바꾸어 해결하는 풀이도 있습니다.

문제 4번 - 등산 코스 정하기

출입구 A에서 산봉우리 B를 방문했다가 다시 출입구 A로 돌아오는 intensity가 가장 작은 등산코스를 찾는다고 가정해보겠습니다.

A-?-…-?-B-?-…-?-A 와 같은 등산코스에서 A를 제외한 모든 지점에서 휴식을 취한다고 생각하면 경로에 포함된 등산로들의 w값 중 최댓값이 등산코스의 intensity가 됩니다. 또한, intensity가 최소가 되도록 A에서 B로 가는 길을 찾았다면 B에서 A로 돌아올 때도 똑같은 길을 그대로 돌아오면 intensity가 최소가 됩니다. 따라서, 출입구-산봉우리-출입구 경로의 최소 intensity를 찾는 대신, 출입구-산봉우리 경로의 최소 intensity만 찾아도 문제를 해결할 수 있습니다.

출입구-산봉우리 경로의 최소 intensity를 찾기 위해 문제에 등장하는 등산로를 다음과 같이 바꾼다고 가정합니다.

출입구에 연결된 양방향 등산로 -> 출입구에서 다른 지점으로만 이동 가능한 단방향 등산로
산봉우리 연결된 양방향 등산로 -> 다른 지점에서 산봉우리로만 이동 가능한 단방향 등산로

위와 같이 문제를 바꾼다면 별다른 중복처리 없이 등산코스에서 출입구는 처음과 끝에 한 번씩, 산봉우리는 한 번만 포함되어야 하는 규칙을 지킬 수 있습니다.

임의의 출입구 A에서 어느 산봉우리로 가야 intensity가 최소가 되는지는 다익스트라 알고리즘을 변형하면 쉽게 구할 수 있습니다. 배열 intensity를 다음과 같이 정의합니다.

intensity[i] = 출입구 A에서 출발하여 i번 지점까지 올 때 가능한 최소 intensity(=등산로들의 가중치 중 최댓값)

임의의 출입구 A에서 시작해 각 지점까지의 intensity 배열을 점점 채워나간다고 생각해봅시다. 경로에 포함된 등산로들의 w값 중 최댓값이 경로의 intensity이기 때문에, 등산로를 더 지날수록 경로의 intensity는 단조 증가하는 형태를 띕니다(예를 들어, A-B-C 경로의 intensity가 3이라면 A-B-C-D 경로의 intensity가 3보다 작아질 수는 없습니다). 경로의 가중치가 단조 증가하는 성질 덕분에 다익스트라 알고리즘을 변형하면 intensity 배열을 채우는 알고리즘을 만들 수 있습니다.

일반적인 다익스트라 알고리즘에서, from 정점에서 to 정점으로 가는 가중치가 weight인 간선이 있을 때 최단거리 배열 dist의 갱신 방식은 아래와 같습니다.

if dist[to] > dist[from] + weight then

dist[to] = dist[from] + weight

이를 아래와 같이 변형해 intensity 배열을 갱신할 수 있습니다.

if intensity[to] > max(intensity[from], weight) then

intensity[to] = max(intensity[from], weight)

모든 지점에 대해 intensity 배열의 값을 채웠다면 산봉우리 중 intensity 배열의 값이 가장 작으면서 번호가 가장 낮은 산봉우리를 고르면 문제의 정답을 찾을 수 있습니다.

만약 모든 출입구에서 한 번씩 다익스트라 알고리즘을 따로 실행해 정답을 찾는다면 시간 초과가 발생하게 됩니다. 문제의 정답을 찾기 위해선 어느 출입구에서 출발하는지에 상관없이 intensity의 최솟값과 산봉우리의 번호만 알면 됩니다. 따라서 모든 출입구에서 다익스트라 알고리즘을 실행하는 대신, 한 번의 다익스트라에서 모든 출입구를 시작 정점으로 두고 알고리즘을 실행한다면 시간 초과를 피할 수 있습니다.

문제 5번 - 행렬과 연산

이 문제를 풀기 위해서는 약간의 아이디어와 덱 혹은 링크드리스트에 대한 이해가 필요합니다. N by M 행렬이 있고, 연산 Q개가 들어온다고 가정하겠습니다.

정확성 테스트 케이스 해설

행렬의 원소는 총 NM개가 있고, Rotate 연산에 영향을 받는 바깥쪽 원소는 총 2(N+M-2)개가 있습니다. ShiftRow 연산의 경우에는 모든 원소가 움직이므로 원소 NM개를 일일이 움직이게 되면 O(NM)의 시간 복잡도로 해결할 수 있습니다. Rotate 연산의 경우에는 바깥의 모든 원소가 움직이므로 원소 2(N+M-2)개를 움직이게 되면 O(N+M)의 시간 복잡도로 해결할 수 있습니다. 총 Q개의 연산이 들어오므로 O(NMQ)의 시간 복잡도로 해결할 수 있고, NM이 최대 1만, Q가 최대 100이므로 시간 내에 해결이 가능합니다.

효율성 테스트 케이스 해설

먼저 ShiftRow 연산만을 처리하는 방법부터 생각해봅시다. ShiftRow 연산에서는 행 단위로 원소들이 움직이게 됩니다. 따라서, 행 단위로 행렬을 잘라서 관리해줍니다. 다음은 5 by 5 행렬에 ShiftRow 연산을 시행하여 행 단위로 움직이는 예시입니다.

여기서 모든 행을 움직이는 것이나, 마지막 행을 맨 위로 올리기만 하는 것이나 같은 결과가 나오는 것을 확인할 수 있습니다.

모든 원소들을 움직이면 O(NM)의 시간복잡도가 들지만, 각각의 행을 따로 관리하여 하나의 행만 움직이면 O(M)의 시간 복잡도로 ShiftRow 연산을 처리할 수 있어, 모든 연산을 O(MQ)에 처리할 수 있습니다. 하지만 M은 최대 5만이고 연산의 개수 Q는 최대 10만이므로 시간 복잡도 O(MQ)도 부담이 됩니다.

그렇기에 행 자체를 움직이는 것이 아니라 행의 인덱스만 움직여 처리해줄 것입니다. 왜냐하면 ShiftRow 연산은 행의 순서만 바꿀 뿐이지 각 행의 원소가 바뀌지는 않기 때문에 각 행의 순서만 알고 있어도 상관이 없기 때문입니다. 다음과 같이 인덱스만 관리하게 되면 마지막 행의 인덱스 값만 맨 앞으로 보내주는 것으로 ShiftRow를 해결할 수 있습니다.

인덱스의 개수는 N개가 있고, 이것을 덱이나 링크드리스트처럼 앞 뒤에서 삽입/삭제가 O(1)에 가능한 자료구조를 사용한다면 ShiftRow 연산을 O(1)에 처리할 수 있습니다.

이제, Rotate 연산을 처리하는 방법을 생각해 봅시다.

ShiftRow 연산을 처리할 때, 각각의 행을 따로 관리하여 문제를 해결했습니다. 그 상태에서 Rotate 연산을 시행한다면 1번째 행의 모든 원소, 마지막 행의 모든 원소, 모든 행의 1번째 원소, 모든 행의 마지막 원소를 움직여 줘야 됩니다.

먼저, 1번째 행의 모든 원소와 마지막 행의 모든 원소를 움직이는 방법을 살펴봅시다. 1번째 행의 변화를 살펴보면, 마지막 원소는 2번째 행의 마지막 원소로 옮겨가고, 2번째 행의 1번째 원소가 1번째 행의 1번째 원소로 들어오는 것을 알 수 있습니다. 실제로 움직이는 것은 다음과 같이 2번째 행의 1번째 원소와 1번째 행의 마지막 원소만이 움직이는 것이죠.

만약, 1번째 행을 덱이나 링크드리스트처럼 앞 뒤에서 삽입/삭제가 O(1)에 가능한 자료구조를 사용한다면 1번째 행은 Rotate 연산을 O(1)에 처리할 수 있습니다. 마지막 행도 1번째 행과 같은 방식으로 처리할 수 있습니다.

그러면 이제 모든 행의 1번째 원소, 모든 행의 마지막 원소가 움직이는 방식을 생각해 봅시다. 모든 행의 1번째 원소의 변화를 살펴봅시다. 2번째 행의 1번째 원소는 1번째 행의 1번째 원소로, 3번째 행의 1번째 원소는 2번째 행의 1번째 원소로, … 모든 원소의 행이 바뀌기는 하지만 어떤 행의 1번째 원소라는 것은 변하지 않습니다. 그렇기에 다음과 같이 모든 행의 1번째 원소, 모든 행의 마지막 원소, 즉 1번째 열과 마지막 열을 따로 관리해 줄 것입니다.

이제 Rotate 연산은 다음과 같은 방법으로 시행할 수 있습니다.

1번째 열과 마지막 열도 마찬가지로 덱이나 링크드리스트로 관리해 준다면, 행렬의 크기와 상관없이 O(1)에 Rotate 연산을 시행할 수 있습니다.

자, 이제 이 상태에서 다시 ShiftRow 연산을 처리하는 방법을 생각해 봅시다. 각각의 행들은 이전과 같이 처리해주면 됩니다. 다음과 같이 1번째 열과 마지막 열은 마지막 원소를 1번째 원소로 옮기는 방식을 사용하여 O(1)에 처리할 수 있습니다.

자, 이제 ShiftRow 연산과 Rotate 연산 모두 O(1)에 처리할 수 있게 되었습니다. Q개의 연산들을 O(Q)에 처리할 수 있고, 처리된 행과 열들로 마지막 상태의 행렬을 만드는 데 O(NM)이 걸리게 되므로, O(NM+Q)에 이 문제를 해결할 수 있습니다.

이 방법 이외에도, NM의 범위가 10만 이하라는 점을 이용하여 O(Q*min(N, M))로 해결하는 풀이도 있습니다. N과 M 중 작은 쪽의 최댓값은 sqrt(10만)이고 이 값은 317보다 작으므로, 시간 내에 해결이 가능합니다.

N이 M보다 작을 땐 N개의 행을 덱 또는 링크드리스트로 관리하고, M이 N보다 작을 땐 M개의 열을 덱 또는 링크드리스트로 관리하여 Rotate 연산 또는 ShiftRow 연산을 수행하는 것입니다.

마치며

지금까지 2022 여름 인턴십 코딩 테스트 문제와 풀이를 살펴보았습니다.

본문에서 제시된 풀이는 여러 가지 가능한 풀이 중 일부로, 여러 가지 접근이 있을 수 있습니다. 참가자 여러분이 사용한 풀이법과 본문에서 소개한 풀이법 이외에도 또 다른 접근을 고민해 보시는 것도 많은 도움이 될 것이라 생각합니다.

이번 테스트에 응시해 주신 모든 분들께 감사드리며, 항상 건강에 유의하시고 카카오에서 뵙기를 기대하겠습니다.

감사합니다.

2022 테크 여름인턴십 코딩테스트 해설