2026 카카오그룹 신입크루 공채 코딩테스트 1차 문제해설
2026 카카오그룹 신입크루 1차 코딩테스트는 문자열 처리, 시뮬레이션, 트리 최적화, 그래프 탐색 등 다양한 난도의 7문제로 구성되었으며, 글에서는 그중 일부 문제의 해결 전략을 설명합니다. 핵심은 문제별 제약을 활용해 중복 제거, 주기 탐색, 구조적 정렬, 상태 완전탐색, BFS 시뮬레이션으로 풀이 범위를 줄이는 것입니다. 특히 3번 문제는 최적해의 트리 구조를 증명해 탐색 공간을 크게 축소합니다. ## 문제 1: 스포 방지 구간의 중요한 단어 판별 - 문자열을 공백 기준으로 나누고 각 단어의 시작·끝 인덱스를 구합니다. - 단어 구간과 스포 방지 구간 `[s, e]`가 한 글자라도 겹치면 스포 방지 단어로 분류합니다. - 비스포 구간에 등장한 단어는 `Set`이나 `HashMap`에 저장해 중복 여부를 관리합니다. - 스포 방지 단어 중 다음 조건을 모두 만족하는 단어만 중요한 단어로 셉니다. - 스포 방지 구간과 겹친다. - 비스포 구간에는 등장하지 않았다. - 같은 시점에 왼쪽에서 먼저 공개된 중요한 단어와 중복되지 않는다. - 여러 단어가 동시에 공개될 때는 왼쪽 단어부터 처리하므로, 처리한 중요한 단어도 별도로 저장해야 합니다. ## 문제 2: 모든 신호등이 노란불이 되는 시점 찾기 - 각 신호등은 `G + R + Y` 길이의 주기를 무한히 반복합니다. - 모든 신호등이 동시에 노란불인 첫 시점을 찾기 위해 시뮬레이션합니다. - 정답이 존재하지 않을 수도 있으므로 종료 시점을 정해야 합니다. - 모든 주기 길이의 최소공배수까지 확인하면 이후 상태가 반복됩니다. - 각 `G + R + Y`가 최대 20이므로 충분히 큰 상한까지 직접 시뮬레이션하는 방법도 가능합니다. - 구현 방법은 여러 가지입니다. - 매초 각 신호등의 현재 상태를 갱신합니다. - 시간 배열을 만들고 각 시점의 노란불 개수를 셉니다. - 각 신호등의 노란불 구간을 수식으로 계산해 특정 시점에 노란불인지 판정합니다. - 모든 신호등의 노란불 개수가 신호등 수와 같아지는 첫 시점을 답으로 선택합니다. ## 문제 3: 트리의 리프 노드 수 최대화 - 분배수는 2 또는 3이며, 같은 깊이의 분배 노드는 모두 같은 분배수를 사용합니다. - 분배수 `k`인 노드 하나는 예산을 1 사용하고 리프 수를 `k - 1`만큼 증가시킵니다. - 루트에서 리프까지의 분배도는 경로상의 분배수 곱이며, 항상 `2^p × 3^q` 형태입니다. - 각 경로의 곱이 `split_limit`을 넘지 않아야 합니다. ### 부분 분배의 정렬 - 같은 분배수를 사용하는 연속된 층에서 부분 분배가 여러 번 발생한다면, 얕은 층부터 최대한 완전 분배하도록 순서를 바꿀 수 있습니다. - 순서를 바꿔도 다음 값은 변하지 않습니다. - 전체 예산 사용량 - 전체 리프 수 증가량 - 각 경로에서 분배수 곱의 총량 - 따라서 하나의 분배수 블록에서는 부분 분배가 최대 한 깊이에서만 발생하도록 정렬할 수 있습니다. ### 2분배층을 3분배층보다 위에 배치 - 프런티어 크기가 `W`일 때: - `2 → 3` 순서의 예산은 `W + 2W = 3W` - `3 → 2` 순서의 예산은 `W + 3W = 4W` - 두 순서 모두 최종 프런티어 크기는 `6W`지만, `2 → 3`이 더 적은 예산을 사용합니다. - 따라서 최적해는 일반적으로 다음 형태로 정렬할 수 있습니다. ```text 2분배층 여러 개 → 3분배층 여러 개 ``` ### 풀이 절차 - 가능한 모든 `(i, j)`에 대해 `2^i × 3^j ≤ split_limit`인지 확인합니다. - 각 조합마다 `2`를 사용하는 층을 먼저, `3`을 사용하는 층을 나중에 배치합니다. - 각 층에서 프런티어 전체를 분배할 수 있으면 예산을 사용해 다음 층으로 이동합니다. - 예산이 부족해지면 남은 예산만큼 부분 분배하고 해당 경우를 종료합니다. - 모든 조합 중 최종 리프 수가 가장 큰 값을 답으로 선택합니다. ## 문제 4: 바이러스 파이프 감염 최대화 - 트리의 간선은 A, B, C 세 종류의 파이프로 구성됩니다. - 한 번에는 한 종류의 파이프만 열 수 있으며, 현재 감염된 배양체에서 해당 종류의 파이프만 따라가며 연결된 모든 배양체가 감염됩니다. - 이미 감염된 배양체는 계속 감염 상태로 유지됩니다. - 같은 종류의 파이프를 연속해서 여는 것은 상태 변화가 없으므로 고려할 필요가 없습니다. - 파이프를 열 때마다 현재 감염 집합을 시작점으로 DFS 또는 BFS를 수행합니다. - 가능한 파이프 열림 순서를 모두 시뮬레이션합니다. - 최대 길이가 10이므로 순서의 수는 `3^10 = 59,049`로 충분히 작습니다. - 각 순서에서 최종 감염 배양체 수를 계산하고 최댓값을 구합니다. ## 문제 5: 카카오 앱 밀기 시뮬레이션 - 격자 안의 정사각형 앱을 한 칸 밀면, 앞을 막는 앱들도 같은 방향으로 연쇄 이동합니다. - 앱이 격자 밖으로 나가면 반대편으로 넘어오며, 이 과정에서 추가 충돌이 발생할 수 있습니다. - 앱 블록이 2×2, 3×3처럼 크기 때문에 연쇄 이동이 여러 행과 열로 퍼질 수 있습니다. ### BFS 기반 연쇄 처리 - 명령을 처리할 때 처음 선택한 앱을 시드로 둡니다. - BFS로 해당 앱이 이동할 때 함께 밀려야 하는 앱을 탐색합니다. - 탐색이 끝나면 관련 앱을 동시에 한 칸 이동시킵니다. - 격자 밖으로 잘린 앱이 생기면 이를 다음 라운드의 새로운 시드로 사용합니다. - 새로운 시드가 더 이상 없을 때까지 다음 과정을 반복합니다. 1. 시드 설정 2. BFS로 충돌 앱 탐색 3. 앱 동시 이동 4. 잘린 앱을 다음 시드로 등록 - 격자 크기와 블록 수의 제한이 작아 직접 상태를 시뮬레이션할 수 있으며, 유한한 상태 공간 때문에 연쇄 과정의 종료도 보장됩니다. 문제별로 자료구조와 알고리즘을 복잡하게 적용하기보다, 문자열 중복 관리에는 집합, 반복 주기에는 최소공배수, 트리에는 교환 논증과 완전탐색, 감염·충돌에는 BFS를 적용하는 것이 핵심입니다. 특히 최적화 문제에서는 가능한 구조를 먼저 증명해 탐색 범위를 줄이는 접근이 효과적입니다.
원문 읽기(새 탭에서 열림)
