안녕하세요, 카카오에서 계정시스템 개발을 맡고 있는 잭입니다.
2024 카카오 채용 연계형 겨울 인턴십 코딩 테스트가 지난 11월 25일(토)에 5시간에 걸쳐 진행되었습니다. 문제를 이해하면 쉽게 해결할 수 있는 구현문제와 함께 적절한 알고리즘을 이용해야 통과할 수 있는 문제까지 고루 배치하기 위해 노력하였습니다.
이번 인턴십 코딩 테스트는 총 5문제가 출제되었으며, 문제별 테스트 케이스를 완벽하게 통과해야 점수를 얻을 수 있었습니다.
그럼 각 문제별 해설을 살펴보겠습니다.
문제 1: 가장 많이 받은 선물
이 문제는 자료구조와 반복문, 조건문 등 프로그래밍의 기초 개념들을 적절히 활용하여 푸는 문제입니다.
N명의 이름 리스트에 인덱스를 붙이고 N×N 2차원 배열에 선물을 주고받은 횟수를 저장하는 방법으로 요구사항을 구현할 수 있습니다. 이름 리스트에 인덱스를 붙일 때, 언어에 따라 해시맵(HashMap) 등의 자료구조를 활용할 수 있고, 입력 사이즈가 작기 때문에 인덱스를 찾는 내장 함수를 사용하거나 반복문을 사용해 인덱스를 찾는 코드를 직접 구현해도 됩니다.
이를 위해, 각 gifts의 원소에서 선물을 준 사람 A와 받은 사람 B의 이름을 분리합니다. A의 인덱스가 i, B의 인덱스가 j라면 위에서 생성한 2차원 배열의 (i행, j열)의 값을 1 늘려 A가 B에게 보낸 선물의 수를 카운팅 할 수 있습니다. gifts의 모든 기록을 저장하면 A가 B에게 준 선물의 총 수는 배열의 (i행, j열)의 값, A가 모두에게 준 선물의 수는 배열의 i행의 합, A가 모두에게 받은 선물의 수는 배열의 i열의 합으로 구할 수 있습니다.
위 값들을 모두 구했다면 각 사람마다 자신을 제외한 N – 1명에게 선물을 몇 개 받는지 카운팅하고, 그 최댓값을 갱신해 문제의 정답을 구할 수 있습니다.
문제 2: 도넛과 막대그래프
이 문제는 세 가지 모양의 그래프와 생성된 정점의 특징을 분석하는 것이 핵심인 문제입니다. 각 그래프의 모양은 아래와 같습니다.
이제, 각 세 가지 모양의 그래프와 생성된 정점의 나가는 간선과 들어오는 간선에 관한 특징을 설명드리겠습니다.
아래의 강조 처리된 부분은 각 그래프 혹은 정점에서만 유일하게 나타나는 특징입니다.
- 생성된 정점: 나가는 간선이 2개 이상(그래프의 개수) 존재하고, 들어오는 간선이 존재하지 않습니다.
- 막대 모양 그래프: 생성된 정점과 연결된 간선을 제외했을 때, 들어오는 간선이 없는 정점이 하나 존재하고, 나가는 간선이 없는 정점이 하나 존재합니다(두 정점은 같을 수 있습니다). 나머지 정점은 나가는 간선과 들어오는 간선이 하나씩 존재합니다.
- 도넛 모양 그래프: 생성된 정점과 연결된 간선을 제외했을 때, 모든 정점이 나가는 간선과 들어오는 간선이 하나씩 존재합니다.
- 8자 모양 그래프: 생성된 정점과 연결된 간선을 제외했을 때, 1개의 정점을 제외하면 나가는 간선과 들어오는 간선이 하나씩 존재합니다. 1개의 정점은 나가는 간선 2개와 들어오는 간선 2개가 존재합니다.
위 내용을 바탕으로, 아래의 절차를 코드로 구현해, 같이 생성된 정점과 각 그래프를 찾아낼 수 있습니다.
- 들어오는 간선이 존재하지 않고, 나가는 간선이 2개 이상인 정점을 찾습니다. 이러한 정점은 하나만 존재하며, 해당 정점이 생성된 정점입니다.
- 생성된 정점과 연결된 간선의 개수를 셉니다. 해당 간선들의 개수는 모양 그래프의 총개수와 동일합니다.
- 생성된 정점과 연결된 간선을 모두 삭제합니다.
- 들어오는 간선이 없는 정점의 개수 혹은 나가는 간선이 없는 정점의 개수를 셉니다. 해당 정점들은 각 막대 모양 그래프마다 하나씩만 존재하기 때문에 해당 정점들의 개수는 막대 모양 그래프의 개수와 동일합니다.
- 들어오는 간선이 2개이면서 나가는 간선이 2개인 정점의 개수를 셉니다. 해당 정점들은 각 8자 모양 그래프마다 하나씩만 존재하기 때문에, 해당 정점들의 개수는 8자 모양 그래프의 개수와 동일합니다.
- 모양 그래프의 총 개수에서 4번과 5번에서 센 정점들의 개수를 뺍니다. 구한 값은 도넛 모양 그래프의 개수와 동일합니다.
문제 3: 주사위 고르기
이 문제는 제한사항을 파악해, 효율적인 시간복잡도의 완전탐색 풀이를 설계할 수 있어야 합니다.
주사위 눈의 합이 큰 순서대로 주사위를 가져가면 최적이라는 착각을 할 수 있으나, 단순히 눈의 합이 큰 주사위를 가져간다고 해서 승률이 높아지지는 않습니다. 테스트케이스 제한사항의 크기가 작으므로, 가능한 모든 경우를 탐색하는 방법으로 문제를 해결할 수 있습니다. 단, 제한사항을 고려해 지나치게 비효율적인 시간복잡도가 되지 않도록 주의해야 합니다.
풀이를 크게 1: A가 가져갈 주사위를 선택하는 부분과, 2: 가져간 주사위를 굴린 결과를 세는 부분으로 나누겠습니다.
풀이 1: A가 가져갈 주사위를 선택하는 부분
A가 가져갈 주사위를 선택하는 모든 경우를 완전탐색으로 찾습니다. 백트래킹, 비트마스킹 등의 기법을 사용해 주사위를 선택하거나, 언어에 따라 조합(Combination)을 구할 수 있는 라이브러리를 적절히 사용하면 해당 구현이 가능합니다. 이러한 방법으로 탐색하게 되는 경우의 수는 n개의 주사위 중 n/2개의 주사위를 고르는 방법의 수입니다. 문제의 제한에 따르면 n의 최댓값은 10이고, n이 최댓값일 때 10개의 주사위 중 5개의 주사위를 고르는 방법의 수는 252입니다.
풀이 2: 가져간 주사위를 굴린 결과를 세는 부분
2-1) 시간복잡도를 고려하지 않은 완전탐색
다음으로 A, B가 가져간 주사위 조합마다 A의 승률을 계산하기 위해, 각 주사위를 굴린 모든 경우를 시뮬레이션해 A가 이기는 경우의 수를 구합니다. 이때, A, B의 주사위를 한꺼번에 모두 시뮬레이션한다면 각 주사위마다 나올 수 있는 눈이 6개이므로 6^n가지 경우를 탐색하게 됩니다. 이러한 방법으로 가능한 주사위 조합마다 모든 6^n가지 경우를 시뮬레이션하게 되면, n이 최댓값인 10일 때 252 × 6^10 = 15,237,476,352가지 경우를 탐색하게 되므로, 시간초과를 받게 됩니다.
2-2) 시간복잡도를 고려한 완전탐색
시간복잡도를 줄이기 위해 A와 B의 주사위를 한꺼번에 모두 시뮬레이션해 승패를 판단하는 대신, A와 B의 주사위를 따로 시뮬레이션하는 아이디어가 필요합니다.
먼저 A의 주사위를 굴린 결과만 시뮬레이션해 6^(n/2) 가지에 대해 주사위 눈의 합을 저장해 두고, 마찬가지로 B의 주사위를 굴린 결과 6^(n/2) 가지에 대해 주사위 눈의 합을 저장해 둡니다. A와 B의 주사위 눈의 합을 저장해 둔 배열을 각각 arrA, arrB라고 하겠습니다. arrA의 각 원소 x에 대해, x보다 작은 arrB의 원소 개수를 세어, 그 값을 모두 합하면 A가 승리하는 경우의 수와 같아집니다. 이 값은 배열 arrA, arrB를 정렬한 뒤 누적 합, 투 포인터, 이분 탐색등의 기법을 사용해 구할 수 있습니다. arrA의 길이 6^(n/2)를 m이라고 할 때, 정렬이 필요 없는 구현의 경우 O(m), 정렬이 필요한 구현의 경우 O(m × log m)의 시간복잡도를 가집니다. n이 최댓값인 10일 때 m은 6^5 = 7,776이므로, 가능한 주사위 조합의 최댓값인 252를 곱해도 충분히 빠른 실행시간을 가지게 됩니다.
위에서 설명한 풀이 1과 2의 두 구현 부분을 합치면, 가능한 모든 주사위 조합에 대해 A가 승리하는 경우의 수를 구할 수 있고, 그중 승률이 가장 높은 주사위 조합을 찾을 수 있습니다.
문제 4: 카드게임
a, 현재 라운드까지 뽑은 카드 중 아직 가져오지 않은 카드를 담은 배열을 b라고 하겠습니다. 각 라운드에서 아래와 같은 우선순위에 따라 최대한 적은 동전을 소모하면서 라운드를 진행하면 최적의 답을 구할 수 있습니다. - 동전 0개 소모: 카드 두 장에 적힌 수의 합이
n+1이 되도록a배열의 카드 두 장을 내고 다음 라운드로 진행합니다. - 동전 1개 소모: 카드 두 장에 적힌 수의 합이
n+1이 되도록a배열의 카드 한 장과b배열의 카드 한 장을 내고 다음 라운드로 진행합니다. - 동전 2개 소모: 카드 두 장에 적힌 수의 합이
n+1이 되도록b배열의 카드 두 장을 내고 다음 라운드로 진행합니다.
위 세 가지 방법이 모두 불가능할 때, 현재 라운드가 도달 가능한 최대 라운드가 됩니다.
문제 5: 산 모양 타일링
이 문제는 정삼각형 격자 타일링의 특징을 이용해, 타일링 방법을 단순화해야 문제를 해결할 수 있습니다.
정삼각형 격자에서 마름모 타일은 언제나 사다리꼴의 윗변과 변을 공유하는 아래 방향 정삼각형(▽ 모양) 하나와 위 방향 정삼각형(△ 모양) 하나를 덮게 됩니다. 이 문제에서 아래 방향 정삼각형의 개수는 사다리꼴의 윗변의 길이인 n이기 때문에, 먼저 아래 방향 정삼각형 n개를 어떻게 덮을지 결정하고 남은 부분을 모두 정삼각형 타일로 덮는 경우의 수를 세는 방법으로 답을 구할 수 있습니다.
아래 방향 정삼각형을 타일로 덮는 방법은 아래와 같이 총 4가지입니다.
- 위쪽 정삼각형과 함께 마름모 타일로 덮기
- 왼쪽 정삼각형과 함께 마름모 타일로 덮기
- 오른쪽 정삼각형과 함께 마름모 타일로 덮기
- 정삼각형 타일로 덮기
가장 왼쪽의 아래 방향 정삼각형부터 시작하여 오른쪽으로 가며 하나씩 타일로 덮는 방법을 결정해 나갑니다. 이때, 아래와 같은 조건을 고려해야 합니다.
- 1번 방법은 위쪽 정삼각형이 있는 경우에만 적용할 수 있습니다.
- 직전 아래 방향 정삼각형에 3번 방법을 적용했다면, 현재 아래 방향 정삼각형에 2번 방법을 적용할 수 없습니다.
a[k]=k번째 아래 방향 정삼각형까지 덮되,k번째 아래 방향 정삼각형을 덮는 방법이 3번 방법인 경우의 수b[k]=k번째 아래 방향 정삼각형까지 덮되,k번째 아래 방향 정삼각형을 덮는 방법이 3번 방법이 아닌 경우의 수
a[k]와 b[k]를 a[k-1]과 b[k-1]에 대한 점화식으로 표현해 봅시다. Case 1. `k`번째 아래 방향 정삼각형 위에 정삼각형이 붙은 경우 (tops[k-1] = 1)
a[k]의 경우, k-1번째 아래 방향 정삼각형을 덮은 방법이 3번 방법인지와 관계없이 3번 방법을 적용할 수 있습니다. 따라서, a[k] = a[k-1] + b[k-1]입니다.
b[k]의 경우, 만약 k-1번째 아래 방향 정삼각형을 덮은 방법이 3번 방법이었다면, k번째 아래 방향 정삼각형에는 1번 또는 4번 방법을 적용할 수 있습니다. 그렇지 않다면 1번, 2번, 4번 중 하나의 방법을 적용할 수 있습니다. 따라서, k-1번째 아래 방향 정삼각형을 3번 방법으로 덮는 a[k-1]개의 방법 각각마다 2개씩, 그리고 k-1번째 아래 방향 정삼각형을 3번 방법이 아닌 방법으로 덮는 b[k-1]개의 방법 각각마다 3개씩의 방법이 있습니다. 따라서 b[k] = 2 × a[k-1] + 3 × b[k-1]입니다.
Case 2. `k`번째 아래 방향 정삼각형 위에 정삼각형이 붙지 않은 경우 (tops[k-1] = 0)
a[k]의 경우 Case 1과 동일하게 a[k] = a[k-1] + b[k-1]입니다.
b[k]의 경우, 1번 방법을 적용할 수 없습니다. 따라서, k-1번째 아래 방향 정삼각형을 3번 방법으로 덮는 a[k-1]개의 방법 각각마다 1개씩, 그리고 k-1번째 아래 방향 정삼각형을 3번 방법이 아닌 방법으로 덮는 b[k-1]개의 방법 각각마다 2개씩의 방법이 있습니다. 따라서, b[k] = a[k-1] + 2 x b[k-1]입니다.
이와 같이 a[k]와 b[k]를 a[k-1]과 b[k-1]에 대한 식으로 나타낼 수 있으므로, 다이나믹 프로그래밍을 이용하여 a[n]과 b[n]을 구할 수 있습니다. 초기값은 a[1]=1, b[1]은 1번째 정삼각형 위에 정삼각형이 붙은 경우 3, 그렇지 않은 경우 2로 초기화하거나, a[0] = 0, b[0] = 1로 초기화하는 방법이 있습니다.
구하려는 정답은 a[n] + b[n]입니다. 경우의 수를 10007로 나눈 나머지를 구해야 하므로, 연산을 할 때마다 10007로 나눈 나머지를 구하여 저장하면 됩니다. 예를 들어, a[k] = (a[k-1] + b[k-1]) % 10007와 같이 계산하면 됩니다.이때, 전체 시간복잡도는 O(n)입니다.
마치며
지금까지 2024 카카오 채용 연계형 겨울 인턴십 코딩 테스트 문제와 풀이를 살펴보았습니다.
위에서 설명드린 풀이 방법 외에도 다양한 해결법이 있습니다. 이때, 핵심은 문제를 풀이할 때는 주어진 제한사항을 고려하여 효율적인 방법을 찾아내는 것입니다. 실제 코딩테스트를 치르는 과정에서, 종료시간이 주는 압박감에 참가자 분들이 제실력을 미처 발휘하지 못했을 수도 있는데요, 시험이 마무리된 만큼 이제는 여유롭게 다양한 풀이법을 생각하여 더욱 완성도 높은 소스코드를 작성해 보시기 바랍니다.
이번 코딩 테스트에 응시해 주신 모든 분들께 감사드리며, 앞으로도 많은 관심 부탁드립니다.
감사합니다.
