카카오, 2024 겨울 인턴십 코딩 테스트 5문제 해설 공개

카카오가 2024 채용 연계형 겨울 인턴십 코딩 테스트의 5개 문제에 대한 상세 해설을 공개했다. 이번 테스트는 자료구조 활용부터 동적 계획법까지 다양한 알고리즘 역량을 평가하도록 구성되었으며, 각 문제의 최적 풀이와 시간복잡도 분석이 포함되었다.

문제별 핵심 풀이 전략

• 가장 많이 받은 선물: 2차원 배열을 이용해 선물 주고받은 관계를 카운팅하고, 이를 기반으로 순위를 매기는 자료구조 활용 문제다.
• 도넛과 막대 그래프: 그래프의 정점과 간선 수, 차선(나가는/들어오는 간선) 등을 분석해 생성된 정점과 그래프의 형태(도넛, 막대, 8자)를 구분한다. 이 방법은 O(V+E)의 시간복잡도로 해결 가능하다.
• 주사위 고르기: 주사위 조합을 완전탐색하되, A와 B의 주사위 결과를 분리해 시뮬레이션한 뒤 정렬 및 투 포인터 기법을 적용해 시간복잡도를 O(m log m) 수준으로 최적화한다.
• 카드게임: 동전 소모를 최소화하기 위해 손에 있는 카드(a)와 뽑은 카드(b)를 구분하고, 동전 0개(두 장 모두 a), 1개(각각 한 장), 2개(두 장 모두 b) 순으로 우선순위를 두어 진행하는 그리디 알고리즘을 적용한다.
• 산 모양 타일링: 정삼각형 격자에서 마름모 타일의 덮는 경우를 4가지로 분류하고, 직전 상태에 따라 경우의 수가 달라지는 조건을 고려해 다이나믹 프로그래밍(DP) 점화식을 세운다. 전체 시간복잡도는 O(n)이다.