DP 마스터: 100제

상태의 의미, 초기값, 마지막 행동과 계산 순서를 익힌다. 피보나치형 문제의 반복을 줄이고 경우의 수, 최솟값, 최댓값, 도달 불가능 상태, 기본 격자 경로와 Top-down/Bottom-up을 서로 다른 문제에서 연습한다.

배열이나 문자열을 왼쪽부터 한 번 처리하며 미래에 필요한 상수 개의 상태만 남긴다. 선택/비선택, 연속 길이, 마지막 상태, 최대·최소 동시 저장, 최대 한 번의 전략 변경, 최솟값과 경우의 수 동시 관리, parent를 이용한 최적 상태열 복원을 다룬다. 모든 문제는 O(N) 또는 O(N×상수)에 풀리며 입력 크기만큼 커지는 행동 횟수나 용량 축을 사용하지 않는다.

단순 선형 DP와 배낭 사이의 간격을 메운다. 현재 상태로 올 수 있는 모든 이전 위치나 문자열 분할점을 탐색하고, 두 prefix, 정확한 선택 수와 분할 수처럼 범위가 입력에 따라 달라지는 보조 상태 축을 관리한다. O(N²) LIS, 차이를 상태로 저장하는 DP, 경로 복원과 Egg Drop을 차례로 다룬다.

0/1, Subset Sum 가능 여부와 경우의 수, 무한 배낭, 최소 동전, 가치 축, Bounded Knapsack, 정확히 K개, 두 자원 제한을 중복 없이 연습한다. 「트럭 적재 최적화」는 c_i개를 Binary Splitting하고, 「서울에서 경산까지」는 도시와 누적 시간을 상태로 쓰는 종합 배낭 문제다.

기본 LIS와 LCS는 3단계에서 끝내고, 최대합 LIS, 공통 부분 문자열, 회문 부분수열, 편집 거리, 실제 LCS 복원과 서로 다른 공통 부분수열 세기로 발전한다. 이후 좌표 압축 자료구조에 (LIS 길이, 개수)를 함께 저장하고, LCIS, Trie 기반 사전 분해, KMP 자동자 상태와 삭제 DP의 결합을 다룬다.

격자 5문제와 구간 5문제로 압축한다. 격자에서는 장애물, 최소 비용, 자원 사용, 최대 정사각형, 양방향 행 sweep을 다룬다. 구간에서는 양 끝 선택, 행렬 곱셈 순서, 인접 합치기, 같은 문자를 합치는 비정형 전이, 마지막 풍선을 정하는 종합 전이로 발전한다.

DAG 최장 경로와 작업 일정, 트리의 선택/비선택, 독립 집합과 정점 커버, 트리 경로 상태, rerooting, 자식 DP 배열의 배낭식 병합을 익힌다.

대표 상태: dp[u][0] = u를 선택하지 않았을 때, dp[u][1] = u를 선택했을 때, dp[u][k] = u의 서브트리에서 정확히 k개를 선택한 최적값.
트리 DP의 본질은 자식의 답을 먼저 구하고 부모의 답을 계산하는 것이다. 「루트 연결 연구팀」에서는 자식별 상태 배열을 전형적인 배낭 전이로 병합한다. 「두 번째 지름」은 전역 상위 두 경로 후보와 동률을 관리하고, 「두 동강 난 트리의 지름」은 각 자식을 제외한 위쪽 깊이와 지름을 rerooting으로 전달한다.

집합 상태, 작업 배정, 마지막 원소를 기억하는 TSP와 경로 수, 부분집합 분할, 모든 정점 방문 최단 거리, 완전 매칭과 사이클 중복 제거, 행 프로필을 연습한다.

대표 상태: dp[mask], dp[mask][last].
「연구실 좌석 배치」에서는 dp[row][mask]로 이전 행과 현재 행의 호환성을 검사한다. 시간복잡도 O(2^N), O(N·2^N), O(N²·2^N), 모든 부분마스크 순회 O(3^N)를 입력 제한과 함께 계산한다.

금지·포함 숫자 조건부터 자릿수 DP의 위치(pos), 상한 일치 여부(tight), 선행 0 처리(started), 이전 숫자, 사용한 숫자 집합과 값·자릿수 합의 나머지 상태까지 연속해서 익힌다. 이후 승리·패배 게임 DP, DAG 게임, 확률분포 DP와 기댓값 점화식으로 확장하고 Cudak에서 자릿수 합 조건을 종합한다.

대표 상태: dp[pos][tight][started][state], dp[state] = 승리 가능 여부 또는 기대 행동 횟수.

Prefix Sum과 Monotone Queue, 격자의 3방향 전이 압축, prefix 합을 이용한 분할 개수 세기, 사분면 재귀 DP, 누적합을 포함한 행렬 거듭제곱, SOS DP를 다룬다. 후반에는 Floyd-Warshall과 구간 비용 DP, 단조 스택과 4방향 직사각형 누적, Divide and Conquer Optimization, Knuth Optimization을 실제 문제로 연결한다.

전부 풀지 못해도 병목 전이가 무엇인지, 단순 O(N²)를 어떤 구조로 줄일 수 있는지 설명할 수 있어야 한다. 최종 문제는 상태 설계, 시간 최적화, 답 복원, 다른 알고리즘 결합, 까다로운 초기값 중 여러 요소를 함께 요구한다.