대규모 데이터셋에서 동적 계획법(Dynamic Programming)을 적용할 때, DP 테이블의 크기가 너무 커지거나 상태 전이 비용이 높아져 발생하는 성능 문제를 해결하기 위한 고급 최적화 기법(예: Convex Hull Trick, Divide and Conquer Optimization, Monotonic Queue Optimization)들을 설명하고, 각 기법이 어떤 형태의 점화식에 적용될 수 있는지 구체적인 예시를 들어 설명하시오.

면접관님, 대규모 데이터셋에서 동적 계획법을 사용할 때 DP 테이블 크기나 상태 전이 비용 때문에 성능 문제가 발생할 수 있습니다. 이를 해결하기 위한 고급 최적화 기법들이 있습니다.

먼저 Convex Hull Trick은 점화식이 dp[i] = min(a[j] * b[i] + c[j]) 형태일 때 유용합니다. 각 j에 대해 직선 y = a[j] * x + c[j]을 그리고, 이 직선들의 lower envelope를 유지하면서 최적의 j를 빠르게 찾습니다.

Divide and Conquer Optimization은 점화식이 dp[i][j] = min(dp[i-1][k] + cost(k, j)) 형태이고, cost(k, j)가 Monge array 조건을 만족할 때 사용할 수 있습니다. 이 경우, 최적의 k가 단조 증가한다는 성질을 이용하여 분할 정복 방식으로 문제를 해결합니다.

Monotonic Queue Optimization은 점화식이 dp[i] = min(dp[j] + cost(i, j)) 형태이고, j의 범위가 i에 따라 단조적으로 변할 때 효과적입니다. 큐를 사용하여 dp[j] + cost(i, j) 값이 최소가 될 가능성이 없는 j들을 제거하면서 최적값을 찾습니다. 예를 들어, 슬라이딩 윈도우 최솟값 문제에 적용할 수 있습니다.