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

2026년도 카카오그룹 신입크루 공개 채용을 위한 코딩테스트가 지난해 10월 2차례에 걸쳐 진행되었습니다. 그 중 2차 코딩테스트는 총 5문제가 출제되었으며, 1차 테스트보다 문제수는 적지만 난이도는 좀 더 높은 문제들로 구성하였습니다.

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

문제 1: 힌트 스테이지

문제 풀러 가기

각 스테이지에서 힌트 번들을 구매할지 여부를 2^k 으로 완전탐색하여 해결할 수 있습니다.

어떤 스테이지에서 힌트 번들을 구매할지 미리 정했다면, 각 스테이지에서 힌트권을 사용 가능한 최대 개수만큼 사용했을 때의 스테이지 해결 비용을 더해 나가면 됩니다. 구체적인 구현 방법은 아래와 같습니다.

mask 를 0부터 2^ n -1까지 순회합니다. mask 값으로 어떤 스테이지에서 힌트 번들을 구매할지 결정합니다.
- 1차원 정수 배열 cnt 를 선언하고 모든 원소를 0으로 초기화합니다. ( cnt[i] = i 번 스테이지에서 사용 가능한 힌트권 수)
- i 를 1부터 n 까지 순회합니다. i 는 현재 스테이지 번호를 의미합니다.
  - 총 비용에 cost[i-1][cnt[i]] 를 더해 줍니다. 즉, 현재 스테이지에서 힌트권을 최대로 사용했을 때의 비용을 더합니다.
  - mask & 2^(i-1)를 연산한 값이 1인 경우(현재 스테이지에서 힌트 번들을 구매하는 경우), 총 비용에 해당 스테이지 힌트 번들의 판매 가격을 더해주고 구매한 힌트권에 대해서 cnt 배열을 업데이트 해줍니다. 이때, cnt 배열의 원소 값이 n 이상일 경우 오버플로우가 발생할 수 있으므로 예외 처리를 해줘야 합니다.
반환할 answer 값을 계산한 총 비용과 비교해 최솟값을 갱신해 줍니다.

그룹	총점	테스트 케이스 그룹 설명	의도
#1	30%	힌트 번들에 힌트권이 한 개씩만 들어 있습니다.	힌트 번들을 모두 구매해도 한 스테이지에서 최대 n-1개의 힌트권을 가질 수 있습니다. 따라서 오버플로우를 고려하지 못했어도 점수를 받을 수 있습니다.
#2	20%	힌트 번들의 가격이 모두 0원입니다.	모든 힌트 번들을 구매하면 항상 최적이므로 완전탐색이 필요하지 않습니다.
#3	50%	추가 제한 사항 없음	-

문제 2: 보물 찾기

문제 풀러 가기

이 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다.

문제의 제한사항에서는 보물을 확실하게 찾을 수 있는 비용을 보장해주고 있습니다. 보물을 확실하게 찾기 위한 최소 비용이란 보물이 1~w열 중 어디에 있던 상관없이 반드시 보물을 찾을 수 있음을 보장하는 최소 비용을 의미합니다. 예를 들어, 세 번째 예시 케이스 [2, 100, 1, 100, 3, 100, 1]의 경우 해당 값이 105입니다. 이는 105의 비용을 사용하면 반드시 보물을 찾을 수 있는 방법이 있음을 의미합니다.

먼저  3열을  굴착합니다.  (비용  1  발생)
	-  보물이  3열에  있을  경우  →  총비용  1
	-  보물이  왼쪽에  있을  경우  →  보물이  1열,  2열  중에  있으므로  두  열을  모두  굴착해  비용  102를  추가  사용  (총비용  103)
	-  보물이  오른쪽에  있을  경우  →  5열을  굴착  (비용  3  발생)
		-  보물이  5열에  있을  경우  →  총비용  4
		-  보물이  왼쪽(4열)에  있을  경우  →  4열을  굴착  (총비용  104)
		-  보물이  오른쪽(6열,  7열  중)에  있을  경우  →  두  열을  모두  굴착해  비용  101을  추가  사용  (총비용  105)

각 구간마다 보물을 확실하게 찾기 위한 최소 비용과, 비용이 최소가 되도록 하기 위해 선택해야 하는 열을 다이나믹 프로그래밍으로 구할 수 있습니다.

먼저 cost, pick 배열을 다음과 같이 정의합니다.

cost[L][R]  :  보물이  L~R  구간에  있을  때,  보물을  찾기  위한  최소  비용
pick[L][R]  :  보물이  L~R  구간에  있을  때,  굴착해야  하는  열

보물이 LR 사이에 있는 임의의 i열을 굴착하면 depth[i]만큼의 비용이 발생합니다.

보물이 i열에 있다면 비용이 더 필요하지 않습니다.
보물이 왼쪽에 있다면 추가로 필요한 비용은 cost[L][i-1]입니다.
보물이 오른쪽에 있다면 추가로 필요한 비용은 cost[i+1][R]입니다.

따라서 L~R 구간에 보물이 있다면, i열을 굴착할 때 보물을 찾기 위해 필요한 최소 비용은 (depth[i], depth[i] + cost[L][i-1], depth[i] + cost[i+1][R]) 세 값 중 가장 큰 값이 됩니다.

이 값이 가장 작아지는 i를 골랐을 때 해당 값이 cost[L][R]이 되고, 그때의 i가 pick[L][R]이 됩니다. L 이상 R 이하의 모든 i에 대해 위 값을 계산해 cost[L][R]과 pick[L][R]을 구합니다. 모든 (L, R) 구간의 개수는 w^2에 비례하고, 각 구간에서 시도할 i의 개수는 w에 비례합니다. w는 최대 200까지 주어지므로, O(w^3)의 시간복잡도로 충분히 빠른 시간 안에 cost, pick 배열을 채울 수 있습니다.

가능한 모든 구간에 대해 어느 열을 굴착해야 할지 pick 배열에 저장해 뒀으므로, L = 1, R = w로 시작해 excavate(pick[L][R]) 반환값에 따라 매번 구간을 좁혀가면서 보물을 찾을 때까지 pick[L][R]열을 굴착해 가면 문제에서 보장하는 money 이내의 비용을 사용해 보물을 찾을 수 있습니다.

많은 응시자들이 매번 가운데를 고르며 구간을 반씩 좁혀나가는 방법으로 풀이를 시도했습니다. 여기서 더 나아가 항상 가운데만 고르는 대신 굴착 비용이나 가운데로부터의 거리에 가중치를 주어 휴리스틱을 시도한 풀이도 보였습니다.

문제 3: 선인장 숨기기

문제 풀러 가기

deque 자료구조와 슬라이딩 윈도우를 이용하여 해결할 수 있습니다.

격자 각 칸에 해당 칸이 몇 번째 빗방울에 젖는지 번호를 매기면, 임의의 w×h 크기 부분격자 W가 처음으로 비를 맞는 시각은 W 안의 최솟값입니다. 따라서 모든 W 중에서 이 최솟값을 최대화하는 부분격자를 구하면 됩니다. 비가 오지 않은 칸은 INF로 두면, 한 번도 젖지 않는 창이 자동으로 최우선이 됩니다. 동률이면 더 위, 더 왼쪽 부분격자를 고릅니다.

1. 풀이 아이디어

drops의 i번째 좌표가 가리키는 칸에 시간 i를 부여하고, 비가 오지 않은 칸은 INF로 채웁니다.
부분격자 W를 평가하는 값은 f(W) = min(time[r][c] | (r,c)∈W)입니다.
목표는 f(W)를 최대화하는 부분격자의 왼쪽 위 좌표를 찾는 것입니다.

2. 슬라이딩 윈도우 기법을 이용하여 부분격자 내 최솟값을 O(1)에 계산

핵심은 1차원 구간 최솟값을 단조 deque로 평균 O(1)에 구한 뒤, 이를 가로 한 번·세로 한 번 적용해 2차원 창의 최솟값을 얻는 것입니다. 단조 deque는 원소가 오름차순이 되도록 뒤에서 큰 값을 제거하며 넣고, 창을 벗어난 앞쪽 인덱스는 빼줍니다. 각 원소는 최대 한 번 들어가고 한 번 나오므로 전체는 O(N)입니다.

절차는 다음과 같습니다. 각 행에 대해 폭 w의 1차원 슬라이딩 최솟값을 구해 row_mins를 만듭니다. 열 c를 고정하고 row_mins[*][c]에 높이 h의 1차원 슬라이딩 최솟값을 한 번 더 적용해, 좌상단 좌표가 (r, c)인 w×h 부분격자의 f(W) 값을 얻습니다. 아래는 1차원 슬라이딩 최솟값을 구하는 코드 예시입니다. 이와 유사한 방식으로 2차원 배열의 슬라이딩 최솟값도 구할 수 있습니다.

for  i,  v  in  enumerate(arr):
	while  dq  and  dq[-1][0]  >=  v:
		dq.pop()
	dq.append((v,  i))
	while  dq  and  dq[0][1]  <=  i  -  k:
		dq.popleft()
	if  i  >=  k  -  1:
		out.append(dq[0][0])

총 시간 복잡도는 가로 O(mn), 세로 O(mn)로 총 O(mn)이며, 1차원 단계에서 각 원소가 한 번 들어가고 한 번 나오므로 평균 O(1)로 처리됩니다. m×n ≤ 5×10^5 조건에서 충분히 빠르게 동작합니다.

3. 선택 규칙 반영

각 부분격자를 다음 우선순위에 따라 갱신합니다.

최솟값(f(W)가 클수록 우선합니다.
r이 작을수록, 같으면 c가 작을수록 우선합니다.

4. 시간·공간 복잡도

시간 복잡도는 O(mn), 추가 메모리는 O(mn)입니다. m×n ≤ 5×10^5 조건에서 충분히 빠르게 동작합니다.

그룹	총점	테스트 케이스 그룹 설명	의도
#1	30%	m, n ≤ 50	작은 격자입니다. 완전탐색으로도 통과할 수 있으며, 각 부분격자에 대해 모든 내부 원소를 탐색하는 것을 반복하더라도 시간 내에 해결할 수 있습니다.
#2	70%	추가 제한 사항 없음	-

문제 4: 제곱 개수 배열

문제 풀러 가기

구간합과 수학적 관찰을 통해 해결할 수 있습니다.

배열 brr 는 배열 arr 의 인덱스 순서대로 arr[i] 를 배열 brr 에 연속으로 arr[i] 개씩 추가하여 만든 배열입니다. 예를 들어, arr 가 [2, 1, 5]이면 brr 는 [2, 2, 1, 5, 5, 5, 5, 5]입니다. 하지만 brr 의 원소의 합이 최대 10^15이므로, 실제로 배열을 만들면 시간 안에 답을 구할 수 없습니다. 첫 번째 반환값 K를 구하기 위해서는, l과 r 각 인덱스가 brr 의 어느 “같은 숫자가 이어지는 구간”(이하 숫자 구간)에 속하는지 빠르게 찾아야 합니다. 이를 위해 arr 의 누적 합 배열을 만들어 두고 "인덱스가 어느 숫자 구간에 있는가"를 찾아냅니다. 또 arr^2 의 누적합을 만들어 두어 구간합을 구하는데 활용합니다.

또한 문제의 두 번째 반환값 C를 구하기 위해 고정된 윈도우를 brr 위에서 슬라이딩해야 합니다. 하지만 한 칸씩 윈도우를 움직일 경우, O(|brr|)로 시간초과가 나게 되므로 brr 배열의 특징과 등차수열의 성질을 활용하여 N번의 점프로 모든 경우를 확인해야 O(N)에 문제를 해결할 수 있습니다.

1. K(구간 합) 계산

brr 의 [l…r] 합은 보통 세 덩어리로 나눠서 계산합니다.

1. 왼쪽 부분: l이 있는 숫자 구간의 남은 칸만큼 값을 더합니다.
2. 가운데 부분: 각 구간은 미리 만든 arr² 누적으로 한 번에 더합니다.
3. 오른쪽 부분: r이 있는 숫자 구간의 앞부분만큼 값을 더합니다.

왼쪽과 오른쪽이 같은 숫자 구간이라면, "해당 값 × 길이"로 한 번에 계산됩니다. 핵심은 l과 r이 각각 어느 숫자 구간에 속하는가를 누적합 배열을 사용하여 O(N)안에 찾고, 위 세 부분을 O(1)에 합하는 것입니다.

해당 설명의 예시를 그림으로 나타내면 아래와 같습니다.

왼쪽 부분: 3x2
가운데 부분: 1 + 2×2 + 1
오른쪽 부분: 5x4

2. C(합이 K인 고정된 윈도우의 개수)

윈도우의 길이를 w = r - l + 1, 윈도우의 시작점을 s라 하고

S(s)  =  brr[s]  +  brr[s+1]  +  ...  +  brr[s+w-1]

을 윈도우의 합이라고 가정합니다. 한 칸 이동할 때

S(s+1)  -  S(s)  =  brr[s+w]  -  brr[s]

가 항상 성립합니다.

해당 설명의 예시를 그림으로 나타내면 다음과 같습니다.

윈도우를 오른쪽으로 한 칸 이동할 때마다 동일한 차이(Y-X)가 발생합니다.

즉, 윈도우의 왼쪽 끝과 오른쪽 끝이 각각 일정한 숫자 구간 안에 머무는 동안에는, 위 차이가 항상 같은 값(상수)입니다. 따라서 "경계(숫자가 바뀌는 지점)까지"의 구간에 대해, S(s)는 다음과 같은 등차수열이 됩니다.

S(s)  =  S(s0)  +  (s  -  s0)  *  delta
delta  =  (들어오는  값)  -  (나가는  값)
s  ∈  [s0,  s0  +  m  -  1]
#  m은  경계에  닿기  전까지  한  칸씩  옮길  수  있는  최대  길이
#  s0는  경계의  시작  지점

이 등차수열에서 S(s) = K인 시작점의 개수는 다음과 같이 한 번에 결정됩니다.

if  delta  ==  0:
	#  합이  구간  내에서  항상  같음
	if  S(s0)  ==  K:  count  +=  m
	else:              count  +=  0
else:
	#  등차수의  한  항이  K가  되는지  확인
	t  =  (K  -  S(s0))  /  delta
	#  t가  정수이면서  0  ≤  t  ≤  m-1  이면  정확히  1개
	if  t  is  integer  and  0  ≤  t  <  m:  count  +=  1

그 구간이 끝나면(왼쪽 또는 오른쪽 끝이 숫자 경계를 만나면) 시작점을 s0 에서 s0 + m 으로 점프하고, 같은 절차를 반복하면 전체 C 를 O(N)에 구할 수 있습니다. 초기값 S(s0) 는 위의 K 계산 아이디어를 윈도우 구간 [s0 … s0+w-1] 에 적용해 구하면 됩니다.

그룹	총점	테스트 케이스 그룹 설명	의도
#1	5%	l = r	윈도우의 길이가 1로 특정 숫자의 개수를 모두 더하여 해결할 수 있습니다.
#2	15%	N ≤ 100, arr[i] ≤ 10	brr의 길이가 1,000V이하로 brr 배열을 직접 만들어서 완전탐색으로 문제를 해결할 수 있습니다.
#3	35%	정답이 C = 1인 테스트 케이스만 주어집니다.	위 방식대로 K를 구하여 해결할 수 있습니다.
#4	45%	추가 제한 사항 없음	-

문제 5: 기차 선로

문제 풀러 가기

문제에서 주어지는 격자의 크기가 최대 20칸으로, 선로를 규칙에 맞게 놓는 방법의 수가 많지 않기 때문에 백트래킹 기법으로 문제를 해결할 수 있습니다. 구현이 까다로울 수 있는 문제로, 실수 없이 정확하게 설계하고 구현할 수 있는 능력이 필요합니다.

기차를 (1, 1)에서 출발시켜 현재 칸에 있는 선로에 따라 다음 칸으로 한 칸씩 이동하며 (n, m)에 도착할 때까지 시뮬레이션을 진행합니다. 이때 빈칸을 만날 때마다 놓을 수 있는 선로 종류를 모두 시도합니다. 빈칸에 놓는 선로는 이전 방향, 다음 방향 두 가지 요소에 따라 결정되므로, 기차의 현재 위치뿐만 아니라 직전에 어느 방향에서 왔는지에 대한 정보도 유지합니다. 장애물로 이동하거나 방향에 맞지 않는 선로를 만난 경우 더 이상 탐색하지 않고 가지치기합니다.

기차가 (n, m)에 도착했다면 마지막으로 기차가 격자에 놓인 모든 선로를 지나갔는지, 3번 선로는 가로세로로 한 번씩 총 두 번 지나갔는지 확인하고 문제가 없다면 정답 가짓수의 하나로 셉니다.

그룹	총점	테스트 케이스 그룹 설명	의도
#1	35%	3번 선로를 고려하지 않아도 되는 경우만 주어집니다.	3번 선로는 다른 선로와 다르게 재방문 하게 되는 특징이 있어 구현이 까다로울 수 있습니다. 3번 선로를 고려하지 않게 되면 각 칸의 방문 여부를 비트마스킹으로 표시해 다이나믹 프로그래밍 등으로 해결할 수 있습니다.
#2	65%	추가 제한 사항 없음	-

마치며

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

2차 전체 문제 풀러 가기

2차 코딩테스트는 이미 1차를 통해 검증된 실력을 갖춘 분들이 응시하는 만큼, 단순히 답을 내는 것을 넘어 효율성과 설계의 깊이를 시험하는 고난도 문제들로 출제하였습니다. 실전의 타이트한 시간 제한 속에서 미처 발휘하지 못한 부분들이 있겠지만, 이제는 한 걸음 물러나 이 문제들이 요구했던 본질적인 논리를 다시금 복기해 보시기 바랍니다. 고도화된 최적화 과정을 고민해 보는 이 시간이 여러분을 더 단단한 엔지니어로 만들어 줄 것입니다.

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

코딩테스트 1차 문제해설

감사합니다.

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