grep

Engineering

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

jack.pot카카오

2026년 3월 11일

원문에서 보기 ↗

안녕하세요, 카카오에서 계정시스템을 담당하고 있는 개발자 잭입니다.

2026년도 카카오그룹 신입크루 공개 채용을 위한 코딩테스트가 지난해 10월 2차례에 걸쳐 진행되었습니다. 그 중 1차 코딩테스트는 총 7문제가 출제되었으며, 난이도가 쉬운 문제부터 적절한 알고리즘을 적용해야 통과할 수 있는 문제까지 골고루 구성하였습니다.

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

문제 1: 중요한 단어를 스포 방지

문자열 처리와 중복 처리를 통해 해결할 수 있습니다.

문제에서 정의하는 중요한 단어는 아래 조건을 모두 만족해야 합니다.

  1. 스포 방지 구간에 단어의 일부 혹은 전부가 포함될 것

  2. 스포 방지 구간이 아닌 구간(=비스포 방지 구간)에 등장한 적이 없을 것

  3. (동시에 공개된 단어를 왼쪽부터 판정하면서) 단어 공개 시점에 이미 공개된 스포 방지 단어와 중복되지 않을 것

    • 여러 단어가 같은 시점에 공개되면, 왼쪽 단어부터 순서대로 판정합니다.

공백으로 구분된 단어를 하나씩 확인하면서 위 조건을 충족하는 단어의 수를 세면 됩니다.

구현 방법은 아래와 같습니다.

  1. message 문자열을 공백으로 분리해 각 단어의 [start, end] 인덱스와 문자열을 얻습니다.

  2. 비스포 방지 구간의 단어를 따로 모아 중복 처리를 해줍니다. 이 과정에서 언어에 따라 set 또는 HashMap 등의 자료구조를 사용합니다.

    • 단어 구간 [start, end]와 스포 구간 [s, e]가 한 글자라도 겹치면 스포 방지 구간 단어입니다. 그렇지 않으면 비스포 방지 구간 단어입니다.

  3. 단어를 하나씩 확인하며 스포 방지 구간 단어일 경우 ① 2번에서 처리한 비스포 방지 구간 단어와 중복되지 않는지, ② 이미 공개된 중요한 단어와 중복되지 않는지 확인합니다. 둘 모두 아닐 경우 중요한 단어 개수를 하나 추가하고 해당 단어를 중복 처리합니다.

그룹총점추가 제한 사항의도
#17%message 의 모든 단어는 서로 겹치지 않고 한 번씩만 등장합니다.기본적인 단어 구간 추출/겹침 판정을 확인합니다. 중복 처리를 신경 쓰지 않아도 해결할 수 있습니다.
#213%모든 스포 방지 구간은 각각 정확히 한 단어의 시작과 끝을 가리킵니다. spoiler_ranges 의 길이 = 1스포 구간이 정확히 하나이므로 스포 단어도 정확히 하나입니다. 문자열 처리가 간결하고 비스포 구간 중복만 여부만 확인하여 해결할 수 있습니다.
#345%모든 스포 방지 구간은 각각 정확히 한 단어의 시작과 끝을 가리킵니다.그룹 #2와 달리 여러 스포 구간이 있으므로 이전에 공개된 스포 단어와의 중복 여부를 함께 확인하여 해결할 수 있습니다.
#435%추가 제한 사항 없음-

문제 2: 노란불 신호등

자료구조와 반복문, 조건문 등 프로그래밍의 기초와 최소공배수 등 수학적 지식을 적절히 활용하여 해결할 수 있습니다.

문제 풀이는 크게 시뮬레이션 종료 시점 결정, 시뮬레이션 구현 두 가지 과정으로 이루어집니다. 신호의 사이클은 무한히 반복됩니다. 만약 모든 신호등 사이클 길이(G + R + Y)의 최소공배수까지 모든 신호등이 노란불인 구간이 존재하지 않는다면, 정답을 구할 수 없습니다. 따라서 시뮬레이션을 종료할 시점을 정해야 합니다. GCD 등의 방법으로 모든 신호등 사이클 길이의 최소공배수를 구하거나 G + R + Y의 값이 각각 20 이하이므로 최대 20^5의 시간까지만 시뮬레이션하면 정답의 유무를 구할 수 있습니다.

시뮬레이션을 구현하는 방법은 다양합니다. 신호등의 수가 적으므로 각 신호등별 현재 신호와 그 신호가 얼마나 지속되는지 기억하여 매 초마다 상태를 갱신하고, 모든 신호가 노란불인 시점을 찾아도 충분히 풀이할 수 있습니다. 보다 간단하게는 종료 시점까지 배열을 생성하고 각각의 신호등마다 신호를 바꿔가며 노란 신호를 세면서 신호등의 수와 노란불의 수가 같은 첫 시점을 찾아도 됩니다. 또는 신호등 사이클이 i번 반복됐을 때 노란불 구간이 (G + R + Y) * i + G부터 (G + R + Y) * i + G + Y 이전까지로 시점 t마다 각각의 신호등이 노란불인지 여부를 체크해 판단할 수도 있습니다.

그룹총점테스트 케이스 그룹 설명의도
#130%신호등이 모두 노란불이 되는 시각이 20 이하인 정답이 존재합니다.시뮬레이션할 최종 시점을 20으로 고정하여 해결할 수 있습니다.
#230%신호등이 모두 노란불이 되는 경우가 존재합니다.정답이 반드시 존재합니다.시뮬레이션을 중단할 최종 시점을 고려하지 않아도 해결할 수 있습니다.
#340%추가 제한 사항 없음-

문제 3: 리프 노드 수 최대화

아래에서는 필요한 용어를 정리한 뒤, 핵심이 되는 명제 1, 2를 증명하고, 그 귀결로서 명제 3(최적해의 트리 모양)를 제시합니다. 마지막에 간결한 풀이 절차를 서술합니다.

문제 규칙 및 용어 설명

문제 규칙에 의해, 같은 깊이의 분배 노드는 모두 같은 분배수(k)를 가집니다. 같은 깊이에 있는 노드들의 집합을 프런티어(frontier)라 하고, 그 크기를 W라 하겠습니다.

어떤 깊이에서

분배수가 k인 분배 1회는 예산(dist_limit)을 1을 소모하며, 리프 수를 (k-1)만큼 증가시킵니다. 모든 리프의 분배도는 루트 노드까지 경로상의 분배수의 곱이므로 항상 2^p × 3^q 꼴이며, 각 경로에 대해 이 곱이 split_limit 이하가 되어야 합니다.

명제 1: 부분 분배는 한 깊이에서만 일어나도록 정렬할 수 있습니다.

같은 분배수 k를 여러 깊이에 걸쳐 연속으로 쓰는 구간(이하 k-블록) 안에서 여러 번의 부분 분배가 있다면, 이를 얕은 깊이에서 먼저 완전 분배로 수행하도록 바꾸어도 리프 수, 예산 소모, 분배도 제약이 악화되지 않습니다.

증명은 k-블록의 인접한 두 층 r과 r+1만 보면 충분합니다. 두 층에서 각각 a회, b회 분배를 수행한다고 해보겠습니다.

따라서 k-블록 내부의 분배는 윗층을 가능한 한 완전 분배로 채운 뒤 다음 층으로 진행하는 형태로 정렬할 수 있으며, 그 결과 부분 분배는 해당 블록에서 많아야 한 깊이에서만 발생합니다.

명제 2: 2-블록을 위에, 3-블록을 아래에 두는 것이 예산 면에서 유리합니다.

완전 분배가 가능한 두 인접 층 r과 r+1의 순서만 비교합니다. r층에 도달했을 때 프런티어의 크기가 W라면,

두 경우 모두 r+2층의 프런티어 크기는 W × 2 × 3 = 6W로 같지만, 예산 소모는 전자가 3W로 후자 4보다 작습니다. 즉, 같은 개수의 2분배층과 3분배층을 전부 채운다면, 2분배층을 위에, 3분배층을 아래에 두는 것이 동일한 결과를 더 적은 예산으로 달성할 수 있습니다.

이 교환을 적용할 수 있는 모든 인접 층을 반복적으로 바꾸면, 모든 2-블록이 모든 3-블록보다 위에 오도록 만들 수 있습니다.

명제 3: 최적해의 모양(명제 1, 2의 귀결)

명제 2에 의해 층 순서는 2-블록 → 3-블록으로 배치할 수 있고, 명제 1에 의해 각 블록 내부에서는 윗층부터 완전 분배로 채우며 진행하다가 마지막 한 층에서만 부분 분배가 일어나도록 정렬할 수 있습니다.

이로써 최적해는 "위에서 연속된 2분배층과, 그 아래 연속된 3분배층"이라는 형태를 가지며, 전체 트리에서 부분 분배는 많아야 한 깊이에서만 발생합니다.

따라서 리프가 실제로 존재하는 깊이는 마지막에 분배를 멈춘 층과 그 바로 아래의 층으로 한정됩니다.

풀이 절차

경로곱이 2^i × 3^j ≤ S를 만족하는 모든 정수쌍 (i, j)을 시도해볼 수 있습니다. 명제 2에 따라 층의 순서는 "2-블록 i층 → 3-블록 j층"으로 고정합니다.

프런티어를 1에서 시작해 윗층부터 차례로 진행합니다. 각 층에서 완전 분배가 가능하면, 그 층의 프런티어 수만큼 예산을 소모하고 프런티어를 해당 층의 분배수(k)배로 갱신하며 다음 층으로 내려갑니다.

어느 층에서 예산이 모자라면, 그 층에서 남은 예산만큼 부분 분배를 수행하고 종료합니다.

이렇게 얻는 최종 리프 수를 (i, j)마다 평가하고, 그 중 최댓값을 구합니다. 동일한 i에 대해서는 j를 허용 범위에서 최대화해도 손해가 없으므로, 가능한 i들을 순회하며 각 i에 대해 성립하는 최대 j를 구해 평가할 수도 있습니다.

그룹총점테스트 케이스 그룹 설명의도
#130%dist_limit ≤ 10, split_limit ≤ 50트리가 정렬되지 않은 모든 형태를 완전탐색하여 해결할 수 있습니다.
#270%추가 제한 사항 없음-

문제 4: 바이러스 파이프

이 문제는 그래프 탐색(DFS 또는 BFS)을 이용하여 해결할 수 있습니다.

이 문제의 핵심은 트리의 간선이 A, B, C 세 가지 종류의 파이프로 연결되어 있으며, 한 번에 한 종류의 파이프만 전부 열었다가 닫을 수 있다는 점입니다. 처음에는 하나의 배양체만 감염된 상태로 시작합니다. 특정 종류의 파이프를 열면, 그 파이프를 통해 현재 감염된 배양체와 같은 파이프 종류로 연결된 모든 배양체가 동시에 감염됩니다. 같은 종류의 파이프를 연속해서 여는 것은 의미가 없으며, 한 번 감염된 배양체는 계속 감염 상태를 유지합니다.

핵심 알고리즘은 그래프 탐색(DFS 또는 BFS)입니다. 파이프를 열 때마다, 현재 감염된 배양체를 시작점으로 하여 해당 종류의 파이프만 따라갈 수 있는 부분그래프를 탐색합니다. 탐색을 통해 방문할 수 있는 모든 배양체를 감염시킵니다. 이 과정을 가능한 모든 파이프 열림 순서에 대해 완전탐색으로 시뮬레이션하면, 주어진 조건에서 감염시킬 수 있는 배양체의 최대 개수를 구할 수 있습니다. k가 최대 10이므로 경우의 수(3^10 = 59,049)는 충분히 작습니다.

그룹총점테스트 케이스 그룹 설명의도
#110%트리가 일렬 모양입니다. (각 배양체에 연결된 파이프가 1개 또는 2개)단순 시뮬레이션 동작을 구현합니다.
#220%파이프 종류가 A와 B만 주어집니다.교대 순서만 고려하여 해결할 수 있습니다.
#330%한 배양체에 연결된 파이프 종류가 모두 다릅니다.연쇄적인 바이러스 감염을 고려하지 않아도 됩니다.
#440%추가 제한 없음-

문제 5: 카카오 앱 정리하기

이 문제는 격자에 놓인 여러 정사각형 앱 블록 중 하나를 선택해 상·하·좌·우로 한 칸 밀면, 그 앞을 막는 앱들도 같은 방향으로 연쇄적으로 한 칸씩 밀려나고, 격자를 벗어난 앱은 반대편으로 넘어가게 되어 또 다른 충돌을 만들 수 있다는 규칙을 그대로 시뮬레이션 구현하여 해결할 수 있습니다. 블록 크기가 2×2, 3×3처럼 클 수 있어 연쇄가 여러 행과 열로 퍼질 수 있습니다.

핵심 구현 방법은 처음 밀리는 앱을 시드로 BFS를 통해 연쇄적으로 밀리는 앱들을 확인 후 한 칸씩만 밀기 → 격자를 벗어나며 잘린 앱들을 새 시드로 반복입니다.

  1. 명령 하나를 처리할 때, 먼저 시작 앱을 시드로 잡고 이번에 한 칸 밀면 "같이 밀려야 하는 앱들"을 BFS로 넓혀가며 탐색합니다.

    • 해당 과정을 그림으로 나타내면 아래와 같습니다.

    • 빨간색은 현재 미는 앱

    • 초록색은 밀려야 하는 앱

    • 격자 밖을 넘어간 앱은 잘린 상태로 구현해 둡니다.

  2. 이동 결과로 잘린 앱들을 다음 라운드의 시드로 삼아 다시 BFS → 동시 이동을 반복합니다. 시드가 더 이상 생기지 않으면 그 명령의 처리가 끝입니다.

시작 앱은 케이스에 따라 여러 번 움직일 수 있지만, 한 명령 동안 일어나는 전체 이동 횟수는 이번 연쇄에 관여한 앱 개수와 격자 크기로 상한이 묶여 짧은 시간 내에 종료됩니다. 실제 테스트 케이스도 적절한 솔루션을 통해 짧은 시간 내에 실행됩니다. 격자와 블록의 상태 조합이 유한하므로 언젠가 처음 상태로 되돌아오게 되어 종료가 보장되기 때문입니다.

복잡도는 N, M ≤ 10 로 충분히 여유롭습니다. 한 라운드의 연쇄 수집(BFS)은 O(N·M) 셀 확인으로 끝나고, 라운드 수도 대략 O(N·M) 내외이므로 명령이 최대 1000개여도 문제 없습니다.

그룹총점테스트 케이스 그룹 설명의도
#15%1x1 크기의 앱 1개만 존재합니다.단순 앱의 이동만 구현하여 해결할 수 있습니다.
#210%2x2 크기의 앱 1개만 존재합니다.#1에 더불어 앱이 잘렸을 때를 구현하여 해결할 수 있습니다.
#315%모든 앱의 크기가 1x1입니다.앱의 연쇄 밀기가 하나의 행 또는 열에서만 일어납니다.
#420%앱이 격자 밖으로 이동하는 명령이 주어지지 않습니다.앱의 연쇄적인 밀림을 모든 행과 열에 대하여 구현하여 해결할 수 있습니다.
#550%추가 제한 사항 없음-

문제 6: 발전소 회로 복구

기본적인 BFS와 비트마스킹 DP로 해결할 수 있습니다.

먼저, 모든 회로가 같은 층에 있다고 가정하고 엘리베이터와 회로 사이의 최단 거리를 BFS로 구해 dist 배열에 저장합니다.

이제 위 값을 활용해 비트마스킹 DP로 문제를 해결하면 됩니다. dp 배열의 정의는 아래와 같습니다.

이때 i 번 패널이 마스크에서 대응되는 값은 2^( i-1 )으로 설정하겠습니다.

기술자가 항상 1번 패널에서 출발하므로 dp[0][1] = 0, 나머지 원소 값을 무한대 값으로 초기화합니다. mask 를 1부터 2^ k -1까지, last 를 1부터 k 까지 순회하면서 dp 배열 값을 갱신해 가면 됩니다. ( k 는 패널의 개수)

dp[mask][last] 에서 아직 방문하지 않은 패널 중 다음으로 이동할 next 번 패널을 고르고, next 번 패널을 활성화 가능한지 확인합니다. 활성화 가능 여부는 다음과 같이 확인할 수 있습니다.

next 번 패널이 활성화 가능한 패널이라면, dp[mask | 2^(next-1)][next] 값을 dp[mask][last] + 최단 시간 값과 비교해 최솟값으로 갱신하면 됩니다. 이때 a 번 회로에서 b 번 회로로 이동하는 최단 시간은 아래와 같이 두 가지 경우에 따라 구하면 됩니다.

  1. a 번 회로와 b 번 회로의 층이 서로 같은 경우: a 번 회로와 b 번 회로 사이의 최단거리와 같습니다. 따라서 최단 시간은 dist[a][b] 가 됩니다.

  2. a 번 회로와 b 번 회로의 층이 서로 다른 경우: a 번 회로에서 엘리베이터로 이동한 후, 엘리베이터로 층을 이동하고, 엘리베이터에서 b 번 회로로 이동해야 합니다. 따라서 최단 시간은 dist[a][0] + 두 층의 차이 + dist[0][b] 가 됩니다.

위와 같은 방법으로 dp 배열을 모두 갱신하고 mask = 2^ k -1(모든 패널을 활성화)을 만족하는 dp[mask][last] 값 중 최솟값을 반환하면 정답이 됩니다.

그룹총점테스트 케이스 그룹 설명의도
#113%패널이 두 개만 존재하는 그룹입니다. seqs의 원소가 하나만 존재할 수 밖에 없습니다.a번 패널에서 b번 패널로 이동하는데 필요한 최단 시간만 구하여 해결할 수 있습니다.
#218%패널이 다섯 개 이하만 존재하는 그룹입니다.k!으로 패널 방문 순서를 미리 정한 다음 순서대로 이동하면 됩니다. 이때 두 회로 사이를 이동하는 최단 시간을 구하여 해결할 수 있습니다.
#322%층이 하나만 존재하는 그룹입니다.최단 시간을 구할 때 두 케이스로 나누지 않아도 됩니다. 비트마스킹 DP를 이용하여 해결할 수 있습니다.
#417%1번 패널부터 k번 패널까지 순서대로 방문해야 하는 그룹입니다.정해진 순서대로 방문하여 해결할 수 있습니다.
#530%추가 제한 사항 없음-

문제 7: 최고 속도

문제 풀이를 위해 좌표평면 상에서 각 도로가 만나는 점들을 구할 필요가 있습니다. 이 점들을 교차점이라고 부르겠습니다.

도로는 최대 m = 1000개까지 주어지므로, 이중 반복문으로 가능한 모든 도로 쌍에 대해 교차점을 확인하면 O(m^2)의 시간복잡도로 충분히 빠른 시간 안에 모든 교차점을 구할 수 있습니다. 모든 도로는 x축 혹은 y축에 평행합니다. 도로의 두 끝점을 x-구간/y-구간으로 보고 두 도로의 x범위와 y범위가 겹치는지 확인하면 비교적 쉽게 교차점을 구할 수 있습니다.

각 도로를 해당 도로 위에 있는 카메라들을 기준으로 분할합니다. 도로의 정중앙에는 항상 카메라가 하나 있으며, 그 외에도 카메라가 더 있다면 도로 위에 있는 교차점들 중에 존재하게 됩니다.

카메라를 기준으로 분할된 도로에서 같은 부분에 있는 교차점과 도시들은 서로 카메라를 지나치지 않고 이동할 수 있습니다. 이 점(교차점과 도시)들을 DSU(Disjoint Set Union, 서로소 집합) 자료구조를 활용해 같은 집합으로 합칩니다. 모든 도로에 대해 이 과정을 적용하면 제한 속도 없이 이동 가능한 점들은 서로 같은 집합에 속하게 됩니다. 따라서 제한 속도 없이 이동 가능한 도시들은 1번 도시와 같은 집합에 속하게 됩니다.

도로에서 카메라를 사이에 두고 서로 다른 부분으로 분할된 교차점과 도시들은 해당 카메라를 지나쳐야 이동할 수 있습니다. 카메라를 사이에 두고 서로 다른 부분으로 분할된 점들을 카메라의 제한 속도 = 가중치인 간선으로 연결합니다. 이때, 같은 지점에 카메라가 여러 개 있을 경우, 제한 속도가 가장 낮은 카메라 하나만 간선 연결에 사용해야 합니다. 모든 도로에 대해 분할된 부분마다 이러한 간선을 만듭니다.

모든 간선 중 가중치가 최대(= x)인 간선을 찾아 이 간선이 연결하는 점들을 같은 집합으로 합칩니다. 이때 다른 집합에 속했던 두 점이 같은 집합으로 합쳐졌다면, 제한속도가 x인 카메라를 지나쳤을 때 두 점 사이를 이동할 수 있게 되었다는 의미이므로, 두 점 사이를 이동하기 위한 최고 속도는 x가 됩니다. 따라서 1번 도시와 다른 집합에 속했던 도시가 1번 도시와 같은 집합에 속하게 바뀐다면 해당 도시의 최고 속도가 x임을 알 수 있습니다. 같은 방식으로 x 다음으로 가중치가 큰(= y) 간선의 정점을 같은 집합으로 합치면 최고 속도가 y인 도시를 알 수 있습니다.

따라서 간선을 가중치 기준 내림차순 정렬해 가중치가 큰 간선부터 순서대로 위 과정을 적용하면 모든 도시에 대해 최고 속도를 구할 수 있습니다.

그룹총점테스트 케이스 그룹 설명의도
#115%모든 도로는 x축에 평행합니다. 즉, y1 = `y2입니다.모든 교차점들은 도로의 양 끝점에서만 생기게 됩니다. 도로를 x좌표 기준으로 정렬하고, 1번 도시에서 출발해 x좌표를 늘리거나 줄여가며 최고 속도를 업데이트해주는 방식으로 문제를 해결할 수 있습니다.
#230%주어지는 모든 좌표의 절댓값은 40 이하의 정수입니다.나올 수 있는 좌표가 최대 81 × 81 = 6561개로, 각 좌표를 2차원 배열이나 해시맵 등의 자료구조에 저장해 구현을 단순화하여 해결할 수 있습니다.
#355%추가 제한 사항 없음-

마치며

지금까지 2026 카카오그룹 신입크루 공채 코딩테스트 1차 문제와 풀이를 살펴보았습니다.

위에 소개한 방법 외에도 다양한 풀이법이 있을 것입니다. 코딩테스트는 주어진 제한사항과 정해진 시간 내에서 최적의 효율을 찾아내는 것이 중요하다고 생각합니다. 실제 코딩테스트를 치르는 과정에서 긴장감 때문에 준비한 실력을 다 보여주지 못해 아쉬움이 남을 수도 있지만, 이제는 여유로운 마음으로 다른 풀이법을 고민하며 나만의 더 단단한 코드를 완성해 보시길 바랍니다.

이번 코딩테스트에 응시해 주신 모든 분들에게 감사드리며, 코딩테스트 2차 문제해설도 별도로 작성되어 있으니 함께 참고하시기 바랍니다.

감사합니다.