# Lagrangian Relaxation Patterns Lagrangian Relaxation Patterns는 딱 맞춰야 하는 제약을 penalty로 목적식에 흡수해, DP, flow, greedy, shortest path 같은 더 단순한 oracle을 반복 호출하는 모델링 패턴입니다. Alien Optimization은 그중 "정확히 K개" 제약을 DP count와 함께 다루는 대표 사례이고, 이 레슨은 같은 생각을 더 넓은 최적화 문제에 적용하는 기준을 정리합니다. ## 문제 신호 | 문제 표현 | Lagrangian 관점 | | --- | --- | | 정확히 `K`개 골라야 한다 | 개수에 penalty를 붙인 relaxed DP | | 예산 `B` 이하에서 최대 보상 | 비용 violation에 multiplier 부여 | | flow 양과 비용 조건이 함께 있다 | capacity/flow 제약을 dual 변수로 분리 | | 선택 개수가 늘수록 score가 단조적으로 변한다 | multiplier 이분 탐색 후보 | | 제약만 없으면 greedy/DP가 쉬워진다 | relaxed oracle을 반복 호출 | 핵심은 제약을 없애는 것이 아니라, 제약을 만족하지 않는 정도에 가격을 매겨서 더 쉬운 문제로 바꾸는 것입니다. ### 먼저 걸러야 할 경우 이 기법은 penalty를 붙였을 때 relaxed oracle이 실제로 쉬워질 때만 이득이 있습니다. 고정된 `lambda`에서도 여전히 원래 문제와 같은 차원의 DP, 같은 flow 제약, 같은 어려운 조합 선택을 풀어야 한다면 relaxation이 아니라 문제를 다시 쓴 것에 가깝습니다. 구현 전에 "`lambda`를 고정하면 어떤 상태나 제약이 사라지는가?"를 한 줄로 먼저 적어 보고, 답이 없으면 다른 모델을 찾는 편이 낫습니다. ## 기본 변환 원래 문제가 아래라고 합시다. ```text maximize value(x) subject to count(x) = K ``` `lambda`를 고정하고 relaxed objective를 풉니다. ```text maximize value(x) - lambda * count(x) ``` `lambda`가 커지면 선택 하나가 비싸지므로 선택 개수는 줄어드는 방향으로 움직입니다. 반대로 `lambda`가 작아지면 더 많이 고르는 해가 좋아집니다. 정확히 `K`개짜리 원래 objective는 relaxed score에서 penalty를 되돌려 계산합니다. ```text answer = relaxedScore(lambda) + lambda * K ``` 단, 이 식은 `lambda`에서 얻은 해의 count가 `K`에 맞거나, tie-break와 convex hull 성질로 보정 가능한 경우에 안전합니다. ## 작은 예시 서로 인접한 원소를 동시에 고를 수 없는 배열에서 정확히 `K`개를 고른다고 하겠습니다. ```text values = [8, 7, 6, 5] K = 2 ``` penalty `lambda = 3`을 붙이면 각 선택 score는 아래처럼 바뀝니다. ```text relaxed values = [5, 4, 3, 2] ``` 인접 금지 DP는 이제 "몇 개를 골라야 하는가"를 상태로 들고 가지 않아도 됩니다. 대신 DP 결과에 `count`를 같이 저장해, 현재 penalty에서 몇 개를 고르는지 관찰합니다. ## Count를 같이 들고 가는 DP 아래 코드는 path independent set에서 penalty가 붙은 최댓값과 선택 개수를 동시에 계산합니다. 동점이면 더 많이 고른 해를 택해 count 단조성을 관찰하기 쉽게 만듭니다. 아래 함수는 long long에 들어가는 점수·penalty 및 곱을 전제로 합니다. relaxed.score+penalty*K는 일반적으로 최대화 원문제의 상계입니다. 정확한 K 해 또는 강한 복원 조건 없이는 정답이라고 반환하지 않습니다. 예산 부등식 완화는 최대화에서 value-lambda*(cost-B), lambda>=0처럼 부호를 정합니다. > **코드 환경: 일반 C++17 학습용.** 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 [공통 코드](https://h.readiz.com/learn/cpp-common-library)와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다. ```cpp compile-check #include #include #include using namespace std; struct Result { long long score = 0; int count = 0; }; Result better(Result a, Result b) { if (a.score != b.score) { return a.score > b.score ? a : b; } return a.count > b.count ? a : b; } Result solveRelaxedPath(const vector& value, long long penalty) { Result prev2{0, 0}; Result prev1{0, 0}; for (int x : value) { Result take{prev2.score + x - penalty, prev2.count + 1}; Result skip = prev1; Result cur = better(take, skip); prev2 = prev1; prev1 = cur; } return prev1; } long long dualUpperBound(const vector& value, int targetCount, long long penalty) { Result relaxed = solveRelaxedPath(value, penalty); return relaxed.score + penalty * targetCount; } ``` 실제 정답을 얻으려면 penalty를 이분 탐색하거나, 가능한 breakpoint를 찾거나, count가 정확히 맞는 구간을 확인해야 합니다. 이 코드는 relaxed oracle의 모양을 보여 주는 골격입니다. ## Flow와 Greedy에 붙이는 방식 Lagrangian relaxation은 DP에만 붙지 않습니다. | 원래 제약 | Relaxed oracle | | --- | --- | | 특정 색 간선 수 제한 | 해당 색에만 penalty를 붙인 MST oracle, 복원 조건 별도 | | 예산 안에서 최대 flow | 비용에 multiplier를 붙인 min-cost flow | | coverage를 일정 이상 만족 | uncovered item penalty가 붙은 set 선택 | | 평균 또는 비율 목적식 | `value - lambda * weight` 판정 | 제약을 penalty로 바꿨을 때 oracle이 정말 쉬워지는지가 중요합니다. penalty를 붙였는데도 같은 난이도의 문제라면 relaxation의 이점이 없습니다. ## Dual 변수 해석 `lambda`는 제약 하나의 그림자 가격입니다. ```text lambda가 너무 작다 -> 제약 자원을 과하게 사용한다 lambda가 너무 크다 -> 제약 자원을 너무 적게 사용한다 ``` 문제에서 여러 제약이 동시에 나오면 multiplier도 여러 개가 됩니다. 이 경우 단순 이분 탐색 대신 subgradient, dual averaging, coordinate search 같은 방식이 필요할 수 있습니다. ## 단조성과 Tie-Break Lagrangian 이분 탐색은 response가 단조적일 때 안전합니다. | response | penalty 증가 시 기대 방향 | | --- | --- | | 선택 개수 | 감소 | | 사용 예산 | 감소 | | flow 양 | 감소하거나 유지 | | violation | 감소 | 동점 처리에 따라 count가 흔들리면 breakpoint 주변에서 같은 `lambda`로 서로 다른 해가 나올 수 있습니다. 그래서 DP 상태에 `(score, count)`를 같이 두고, 최대화 기준 다음의 tie-break를 명시합니다. ## 최소 비용 Exact-K와 복원 조건 정확히 K개 선택하는 비용 F(K)를 직접 계산하기 어려울 때 G(lambda)=min_k(F(k)+lambda*k)를 푸는 oracle을 사용합니다. 고정 lambda에서 실제로 계산이 쉬워져야 이득이 있습니다. ### 단조성과 복원 조건 lambda가 증가하면 최적 선택 수는 비증가합니다. 두 최적해의 부등식을 더하면 이를 보일 수 있습니다. 그러나 이 단조성만으로 모든 K의 정답을 복원할 수는 없습니다. ```text F(0)=0, F(1)=10, F(2)=0 ``` 어떤 lambda에서도 k=1은 최적이 되지 않습니다. K=1에 G(lambda)-lambda를 출력하면 실제 값 10을 복원하지 못합니다. F의 이산 볼록성 등으로 각 K가 lower hull 위에 놓인다는 조건을 증명해야 합니다. 정수 lambda만 탐색할 수 있는지도 별도 조건입니다. ### DP oracle 아래는 배열을 비어 있지 않은 구간들로 나누는 O(N²) oracle입니다. cost(l,r)는 구간 비용이고 모든 비용·penalty 합은 INF/2 미만의 유효 범위여야 합니다. n>=0이며 같은 비용이면 더 많은 구간을 선택합니다. ```cpp compile-check #include #include #include #include using namespace std; struct ParametricDpResult { long long value = 0; int count = 0; }; struct ParametricDp { static constexpr long long INF = (1LL << 60); template static ParametricDpResult solveWithPenalty(int n, long long lambda, Cost cost) { vector dp(n + 1, {INF, 0}); dp[0] = {0, 0}; for (int right = 1; right <= n; ++right) { ParametricDpResult best{INF, 0}; for (int left = 0; left < right; ++left) { if (dp[left].value >= INF / 2) { continue; } ParametricDpResult candidate{ dp[left].value + cost(left + 1, right) + lambda, dp[left].count + 1 }; if (candidate.value < best.value || (candidate.value == best.value && candidate.count > best.count)) { best = candidate; } } dp[right] = best; } return dp[n]; } }; ``` 같은 lambda에서 최소·최대 count가 필요하면 tie-break를 각각 두 방향으로 실행합니다. 최소화에서 정확한 K의 relaxed 해를 얻었을 때 답은 G(lambda)-lambda*K입니다. 최대화에서 value-lambda*k를 풀었다면 lambda*K를 더합니다. ### Breakpoint 예시 비용10·count1인 A와 비용7·count2인 B는 lambda=3에서 relaxed 값13으로 같습니다. 더 큰 count를 택하면 B, 작은 count를 택하면 A가 반환됩니다. K가 두 count 사이에 있다는 사실만으로 내부 K의 정확한 비용을 보장하지는 않습니다. 정수 이분 탐색은 충분한 penalty 범위를 먼저 증명하고 count>=K 경계를 찾습니다. oracle 비용 T(N)에 탐색 횟수를 곱합니다. 앞의 인접 금지 선택 oracle은 최대화에 penalty를 빼고, 여기의 분할 oracle은 최소화에 penalty를 더한다는 부호 차이를 비교합니다.