2026 Kakao Group New Crew Open Recruitment Coding Test Round 2 Problem Explanations
The post explains solutions to five problems from Kakao’s 2026 new-employee second-round coding test. The problems require a range of techniques: exhaustive search, dynamic programming, monotonic deques, prefix sums with arithmetic-sequence jumps, and backtracking. The central lesson is to exploit each problem’s structural constraints rather than simulate large data directly. ## Problem 1: Hint Stage - Enumerate every combination of stages where hint bundles are purchased using a bitmask from `0` to `2^n - 1`. - For each combination: - Track the number of hint tickets available at every stage with a `cnt` array. - Add the cost of solving each stage while using as many available hints as possible. - Add the purchase price when a bundle is selected. - Update future `cnt` values when tickets are purchased. - Guard against integer overflow when the number of tickets exceeds `n`. - The full solution uses exhaustive search; some subtasks can be solved more simply when bundles cost zero or contain only one ticket. ## Problem 2: Treasure Hunt - Use interval dynamic programming to minimize the cost required to guarantee finding the treasure, regardless of which column contains it. - Define: - `cost[L][R]`: minimum guaranteed cost when the treasure is somewhere between columns `L` and `R`. - `pick[L][R]`: the column to excavate first for that interval. - If column `i` is excavated: - The cost is `depth[i]` if the treasure is there. - If it is to the left, the additional cost is `cost[L][i-1]`. - If it is to the right, the additional cost is `cost[i+1][R]`. - Therefore, the required cost for choosing `i` is: `max(depth[i], depth[i] + cost[L][i-1], depth[i] + cost[i+1][R])` - Choose the `i` minimizing this value and store it in `pick[L][R]`. - With at most 200 columns, the `O(w^3)` dynamic programming solution is sufficient. - Reconstruct the excavation strategy by repeatedly narrowing the interval according to the result of `excavate(pick[L][R])`. - Simply choosing the middle column, even with heuristic weighting, is not guaranteed to be optimal. ## Problem 3: Hiding the Cactus - Convert the rainfall order into a grid: - Assign each wet cell the index of the raindrop that first reaches it. - Assign `INF` to cells that never receive rain. - For a `w × h` subgrid, its first rainfall time is the minimum value inside it. - The goal is to maximize this minimum, preferring the uppermost and then leftmost subgrid in case of ties. - Compute two-dimensional window minima efficiently: - Apply a monotonic deque horizontally to obtain minimum values for width-`w` windows in every row. - Apply the same technique vertically to those results using height-`h` windows. - Each deque processes elements in amortized `O(1)` time, producing: - Time complexity: `O(mn)` - Additional space: `O(mn)` - This is necessary because the grid may contain up to `5 × 10^5` cells. ## Problem 4: Squared-Count Array - `brr` is formed by repeating each `arr[i]` exactly `arr[i]` times. For example, `[2, 1, 5]` becomes `[2, 2, 1, 5, 5, 5, 5, 5]`. - Since `brr` can have total length up to `10^15`, it must not be constructed explicitly. - Build: - A prefix sum of `arr` to locate which repeated-value segment contains a given index in `brr`. - A prefix sum of `arr[i]^2` to calculate sums across complete segments. ### Calculating `K` - Divide the requested range `[l, r]` into: - The remaining part of the segment containing `l`. - Complete segments in the middle. - The beginning part of the segment containing `r`. - Each part can be calculated in constant time after preprocessing. - If both endpoints belong to the same segment, calculate the result as value × length. ### Calculating `C` - Count fixed-length windows whose sum equals `K`. - Moving a window one position changes its sum by: `new right value - old left value` - While both endpoints remain in the same repeated-value segments, this difference is constant, so window sums form an arithmetic progression. - Jump directly to the next segment boundary instead of moving one position at a time. - Within each arithmetic-progression interval, determine the number of windows summing to `K` mathematically. - This reduces the overall computation to `O(N)`. ## Problem 5: Train Tracks - Because the grid is at most 20 cells in each dimension, backtracking can enumerate valid track placements. - Simulate the train from `(1, 1)` to `(n, m)`. - When encountering an empty cell, try every track type that is compatible with: - The direction from which the train arrived. - The direction in which it will leave. - The search state must include both the current position and the previous travel direction. - Prune immediately when: - The train moves into an obstacle. - The current track does not connect in the required direction. - Upon reaching `(n, m)`, verify that: - Every placed track has been traversed. - Track type 3 has been traversed once horizontally and once vertically. - Valid configurations are counted only after all these conditions are satisfied. The recommended approach is to match the algorithm to the data structure of each problem: enumerate only when constraints permit it, use interval DP for guaranteed search strategies, monotonic deques for sliding minima, mathematical jumps for enormous implicit arrays, and carefully designed backtracking for small but highly constrained grids.
Read original(opens in new tab)