2026 카카오그룹 신입크루 공채 코딩테스트 2차 문제해설

Context

신입 개발자 채용을 위한 코딩테스트는 단순히 정답을 내는 것을 넘어 효율성 있는 알고리즘 설계와 구현 정확성을 검증해야 한다.

Technical Solution

• 문제 1 (힌트 스테이지): 비트마스킹을 이용한 완전탐색으로 2^n개 경우의 수를 순회하며 최소 비용 계산, cnt 배열로 오버플로우 처리
• 문제 2 (보물 찾기): 동적계획법 DP[L][R]으로 구간별 최소 탐색 비용 계산, O(w³) 시간복잡도로 모든 구간의 최적 굴착 위치 저장
• 문제 3 (선인장 숨기기): 단조 deque 기반 슬라이딩 윈도우로 2차원 배열의 구간 최솟값을 O(mn) 시간에 계산
• 문제 4 (제곱 개수 배열): 누적합 배열로 brr의 '숫자 구간' 경계 위치를 O(N)에 탐색, 등차수열 성질을 활용해 합이 K인 윈도우를 O(N)에 계산
• 문제 5 (기차 선로): 백트래킹으로 각 빈 칸에서 가능한 모든 선로 종류 시도, 현재 위치와 직전 이동 방향 정보를 유지하며 장애물 감지 시 가지치기

Key Takeaway

격자 크기가 제한적이거나 상태 조합이 가능할 때는 백트래킹과 가지치기로 지수적 탐색을 수행할 수 있으며, 동적계획법은 구간 경계가 명확한 최적 부분구조 문제에 O(n³) 이내 시간복잡도로 적용 가능하다.