2026 카카오그룹 신입크루 공채 코딩테스트 2차 문제해설
2026 카카오그룹 신입크루 2차 코딩테스트는 총 5문제로, 완전탐색부터 동적 계획법, 슬라이딩 윈도우, 수학적 관찰, 백트래킹까지 다양한 문제 해결 능력을 요구했다. 각 문제는 단순한 구현보다 상태를 효율적으로 표현하고, 불필요한 탐색을 줄이는 설계가 핵심이었다. 특히 입력 크기가 큰 문제에서는 배열을 직접 생성하지 않고 누적합이나 구간별 규칙을 활용해야 했다. ## 문제 1: 힌트 스테이지 — 구매 조합 완전탐색 - 각 스테이지에서 힌트 번들을 구매할지 여부를 비트마스크로 표현한다. - `mask`를 `0`부터 `2^n - 1`까지 순회하며 모든 구매 조합을 확인한다. - 특정 구매 조합이 정해지면: - 현재 스테이지에서 사용할 수 있는 힌트권을 최대한 사용한다. - 그때의 스테이지 해결 비용과 구매 비용을 합산한다. - 번들 구매 후 이후 스테이지에서 사용할 수 있는 힌트권 수를 갱신한다. - 모든 조합 중 총비용이 가장 작은 값을 답으로 선택한다. - 힌트권 수가 `n` 이상 증가할 수 있으므로 배열 인덱스 오버플로를 방지해야 한다. - 핵심 시간복잡도는 구매 여부를 전부 확인하는 완전탐색에 기반한다. ## 문제 2: 보물 찾기 — 구간 DP - 보물이 `L`열부터 `R`열 사이에 있을 때, 반드시 찾기 위한 최소 비용을 `cost[L][R]`로 정의한다. - 구간 안의 `i`열을 굴착하면 다음 세 경우를 고려해야 한다. - 보물이 `i`열에 있으면 추가 비용은 없다. - 보물이 왼쪽에 있으면 `cost[L][i-1]`가 추가된다. - 보물이 오른쪽에 있으면 `cost[i+1][R]`가 추가된다. - 따라서 `i`열을 선택했을 때 필요한 비용은 다음 세 값의 최댓값이다. - `depth[i]` - `depth[i] + cost[L][i-1]` - `depth[i] + cost[i+1][R]` - 이 최댓값을 최소화하는 `i`를 선택해 `cost[L][R]`와 `pick[L][R]`를 갱신한다. - `pick` 배열에는 각 구간에서 처음 굴착해야 할 열을 저장한다. - 이후 전체 구간 `[1, w]`에서 시작해 굴착 결과에 따라 왼쪽 또는 오른쪽 구간으로 범위를 좁힌다. - 열의 개수가 최대 200이므로 모든 구간과 후보 열을 확인하는 `O(w^3)` DP가 가능하다. - 단순히 항상 가운데 열을 고르는 전략은 각 열의 굴착 비용을 반영하지 못해 최적해를 보장하지 않는다. ## 문제 3: 선인장 숨기기 — 2차원 슬라이딩 윈도우 - 각 칸에 해당 칸이 몇 번째 빗방울에 젖는지를 기록한다. - 비를 한 번도 맞지 않는 칸은 `INF`로 설정한다. - `w × h` 부분격자 `W`가 처음 비를 맞는 시각은 내부 값의 최솟값이다. - `f(W) = W 내부 원소들의 최솟값` - 따라서 `f(W)`가 가장 큰 부분격자를 찾으면 된다. - 2차원 최솟값을 직접 반복 계산하지 않고, 단조 deque를 이용해 두 번의 1차원 슬라이딩 윈도우로 처리한다. - 각 행에서 너비 `w`의 최솟값을 계산한다. - 그 결과에 대해 각 열마다 높이 `h`의 최솟값을 계산한다. - 단조 deque에서는: - 새 값을 넣을 때 뒤에서 더 큰 값들을 제거한다. - 윈도우를 벗어난 인덱스는 앞에서 제거한다. - 각 원소가 deque에 최대 한 번 들어가고 한 번 나오므로 전체 시간복잡도는 `O(mn)`이다. - 최솟값이 같으면 더 위쪽, 다시 같으면 더 왼쪽에 있는 부분격자를 선택한다. - 추가 메모리도 `O(mn)`이며, `m × n ≤ 5 × 10^5` 조건을 처리할 수 있다. ## 문제 4: 제곱 개수 배열 — 누적합과 구간 점프 - `brr`는 `arr[i]` 값을 `arr[i]`번 연속해서 추가해 만든 배열이다. - `brr`의 길이가 최대 `10^15` 수준이 될 수 있어 실제 배열을 생성하면 안 된다. - `arr`의 누적합을 이용해 `brr`의 특정 인덱스가 어떤 동일 값 구간에 속하는지 찾는다. - `arr[i]^2`의 누적합도 만들어 여러 숫자 구간에 걸친 합을 빠르게 계산한다. ### 구간 합 K 계산 - `[l, r]` 구간은 최대 세 부분으로 나눈다. - `l`이 속한 구간의 남은 부분 - 완전히 포함되는 가운데 숫자 구간들 - `r`이 속한 구간의 앞부분 - 양 끝이 같은 숫자 구간에 속하면 값과 길이를 곱해 한 번에 계산할 수 있다. - 누적합을 이용해 각 부분을 `O(1)`에 계산한다. ### 합이 K인 윈도우 개수 C 계산 - `brr` 위에서 고정된 길이의 윈도우를 한 칸씩 이동시키면 일반적으로 배열 길이에 비례하는 시간이 걸린다. - 하지만 윈도우의 왼쪽 끝과 오른쪽 끝이 각각 같은 숫자 구간에 머무는 동안에는, 윈도우 합의 변화량이 일정하다. - 이 구간에서 윈도우 합은 등차수열이 되므로 합이 `K`인 시작점의 개수를 수식으로 한 번에 계산할 수 있다. - 숫자가 바뀌는 경계까지 점프한 뒤 같은 과정을 반복한다. - 숫자 구간의 경계를 기준으로 이동하므로 전체 시간복잡도는 `O(N)`이다. ## 문제 5: 기차 선로 — 백트래킹과 시뮬레이션 - 격자 크기가 최대 20칸으로 작아 가능한 선로 배치 수를 백트래킹으로 탐색할 수 있다. - 기차는 `(1, 1)`에서 출발해 현재 선로의 방향에 따라 한 칸씩 이동한다. - 빈칸을 만날 때마다 놓을 수 있는 모든 선로 종류를 시도한다. - 새 선로의 형태는 다음 두 정보에 의해 결정된다. - 직전에 어느 방향에서 들어왔는지 - 다음에 어느 방향으로 나갈지 - 따라서 현재 위치뿐 아니라 이전 이동 방향도 탐색 상태에 포함해야 한다. - 다음과 같은 경우에는 즉시 탐색을 중단한다. - 장애물로 이동하는 경우 - 현재 방향과 맞지 않는 선로를 만난 경우 - 격자 밖으로 나가는 경우 - 도착점 `(n, m)`에 도달하면 전체 조건을 검증한다. - 격자에 놓인 모든 선로를 기차가 지나갔는지 확인한다. - 3번 선로를 가로와 세로 방향으로 각각 한 번씩, 총 두 번 통과했는지 확인한다. - 모든 조건을 만족하는 경로만 정답 개수에 포함한다. - 경우의 수가 많지 않지만 상태와 선로 연결 조건을 정확히 구현하는 것이 가장 중요하다. 각 문제는 문제의 구조에 맞는 알고리즘 선택이 성능을 좌우한다. 작은 상태 공간에서는 완전탐색과 백트래킹을 사용하고, 구간 선택 문제는 DP로 상태를 저장하며, 대규모 배열 문제는 누적합·단조 deque·구간 점프처럼 반복 계산을 제거하는 기법을 적용하는 것이 효과적이다.
원문 읽기(새 탭에서 열림)