🧩 DP & 최적화

DP 기초 작은 문제의 답을 저장해 큰 문제를 푼다. 강의 3개

배낭 문제 담을까 말까 — 대표적인 2차원 DP. 강의 3개 비트마스킹 집합을 정수의 비트로 표현해 빠르게 다룬다. 강의 3개

최장 공통 부분 수열 두 수열의 공통 부분 수열 중 가장 긴 것 — 2차원 DP의 정석. 강의 3개

최장 증가 부분 수열 LIS — O(N log N) 이분 탐색 풀이까지. 강의 3개 트리 DP 트리 위에서 자식의 답을 모아 부모의 답을 만든다. 강의 3개

비트마스크 DP 방문 집합을 비트로 든 채 상태를 전이한다 — 외판원 문제. 강의 3개 구간 DP 구간을 쪼개는 경계를 고르는 DP — 행렬 곱셈 순서. 강의 3개

컨벡스 헐 트릭 직선들의 최솟값 질의로 DP를 가속한다. 강의 2개 분할 정복 최적화 결정 단조성으로 DP를 O(N log N)으로. 강의 2개

크누스 최적화 사각 부등식으로 구간 DP를 O(N²)으로. 강의 2개

Aliens 트릭 라그랑주 완화로 "정확히 k개" 제약을 벗긴다. 강의 2개 슬로프 트릭 볼록 함수의 기울기 변화점만 들고 하는 DP. 강의 2개