카카오 코딩 테스트 2차, 핵심 문제 풀이 전략을 파헤치다!

마스크(Mask)를 활용하여 각 스테이지의 힌트 구매 여부를 결정하고, 1차원 정수 배열 cnt를 통해 각 스테이지에서 사용 가능한 힌트권 수를 관리한다.

cnt 배열의 오버플로우(Overflow) 예외 처리가 중요하며, 총 비용과 answer 값을 비교하여 최솟값을 갱신한다.

이러한 접근 방식은 모든 가능한 경우의 수를 체계적으로 탐색하여 최적의 해를 보장하지만, 스테이지 수가 증가함에 따라 시간 복잡도(Time Complexity)가 지수적으로 증가하는 단점이 있다.

cost[L][R]과 pick[L][R] 배열을 정의하여, 보물이 L~R 구간에 있을 때 최소 비용과 굴착해야 하는 열을 저장한다.

각 구간마다 보물을 확실하게 찾기 위한 최소 비용을 계산하기 위해, 굴착 비용과 보물이 왼쪽에 있을 경우, 오른쪽에 있을 경우의 비용을 고려한다.

시간 복잡도(Time Complexity)는 O(w^3)으로, w는 최대 200까지 주어지므로 충분히 빠른 시간 안에 cost, pick 배열을 채울 수 있다. 다이나믹 프로그래밍(Dynamic Programming)은 최적 부분 구조(Optimal Substructure)와 중복되는 부분 문제(Overlapping Subproblems)를 활용하여 효율성을 높인다.

1차원 구간 최솟값을 단조 deque로 평균 O(1)에 구한 뒤, 이를 가로 한 번, 세로 한 번 적용하여 2차원 창의 최솟값을 얻는다.

슬라이딩 윈도우(Sliding Window) 기법은 고정된 크기의 윈도우를 이동시키면서 문제를 해결하는 데 유용하며, 시간 복잡도(Time Complexity)를 O(N)으로 줄일 수 있다.

선택 규칙을 반영하여 최솟값, r, c의 우선순위에 따라 부분 격자를 갱신하며, 시간 복잡도(Time Complexity)는 O(mn), 추가 메모리는 O(mn)이다.

arr의 누적 합 배열과 arr^2의 누적합을 활용하여, l과 r이 속한 숫자 구간을 빠르게 찾고 구간 합을 계산한다.

윈도우를 한 칸 이동할 때 발생하는 차이를 이용하여, 등차수열의 성질을 활용하여 윈도우의 합이 K인 시작점의 개수를 계산한다.

O(N)의 시간 복잡도(Time Complexity)로 전체 C를 계산할 수 있으며, 윈도우의 왼쪽 끝과 오른쪽 끝이 일정한 숫자 구간 안에 머무는 동안에는 위 차이가 항상 같은 값(상수)이다.

기차의 현재 위치와 직전 방향 정보를 유지하며, 빈칸에 놓을 수 있는 선로 종류를 모두 시도한다.

장애물이나 방향에 맞지 않는 선로를 만난 경우 가지치기(Pruning)를 수행하여 탐색 공간을 줄인다.

기차가 (n, m)에 도착했을 때, 모든 선로를 지나갔는지와 3번 선로의 사용 횟수를 확인하여 정답 가짓수를 계산한다.

백트래킹(Backtracking)은 가능한 모든 경우의 수를 탐색하지만, 최악의 경우 시간 복잡도(Time Complexity)가 지수적으로 증가할 수 있다.

각 문제의 풀이 과정에서 시간 복잡도(Time Complexity)를 최소화하고, 공간 효율성을 고려하는 것이 중요하다.

문제 해결을 위한 핵심 아이디어를 도출하고, 이를 효율적으로 구현할 수 있는 능력이 요구된다.

실전의 타이트한 시간 제한 속에서, 정확하고 효율적인 코드 설계 능력이 핵심이다. 고도화된 최적화 과정을 통해 더 단단한 엔지니어로 성장할 수 있다.