Exchange argument
Exchange argument란?
임의의 상태에서 매순간 손해보지 않으면서, 원소끼리의 교환을 통해 얻어지는 상태로 나아가는 것을 반복하면 최적의 상태를 얻을 수 있다는 탐욕적인 주장입니다.
이해를 위해 다양한 문제에서의 활용을 소개해보겠습니다.
구두 수선공(링크)
우리는 주어지는 작업의 순서를 정해서 최적의 작업순서를 정해야 합니다. 임의의 작업 순서가 정해졌을 때 비용은 $ (T_{k_1}) \times S_{k_2} + (T_{k_1}+T_{k_2}) \times S_{k_3} + … (T_{k_1}+T_{k_2}+…T_{k_{n_-1}}) \times S_{k_n} $ 이 됩니다.
여기서 $ i $ 번째와 $ i+1 $ 번째의 작업의 순서를 서로 바꾸는 시행에 대해 생각해봅시다. 이미 $ i-1 $ 번째까지 작업이 완료되었으므로 $ k_i $ 와 $ k_{i+1} $ 의 작업의 순서를 바꿔도 $ i-1 $ 번째까지의 작업시간에 영향을 주지 않습니다. 또한, $ Sum(T_{k_1}\sim T_{k_{i+1}}) $ 은 바뀌지 않으므로 $ i+2\sim N $ 번째 작업시간에 영향을 주지 않습니다. 즉, 인접한 두 순서의 교환은 이 두 작업에만 영향을 미치게 됩니다. 그러면 $ k_i $ 와 $ k_{i+1} $ 의 작업의 순서를 정해줘서 전체 작업시간을 줄여봅시다.
$ Sum(T_{k_1}\sim T_{k_{i-1}}) \times S_{k_i} + Sum(T_{k_1}\sim T_{k_{i-1}} + T_{k_i}) \times S_{k_{i+1}} $ $ Sum(T_{k_1}\sim T_{k_{i-1}}) \times S_{k_{i+1}} + Sum(T_{k_1}\sim T_{k_{i-1}} + T_{k_{i+1}}) \times S_{k_i} $
$ k_i $ 번째와 $ k_{i+1} $ 번째의 작업순서를 바꾸지 않았을 때, 이 두 작업에서 걸리는 시간의 합은 위 수식과 같습니다. 작업순서를 바꾸었을 때의 수식은 아래입니다. 위 식이 아래 식보다 작지 않으면 순서를 바꿔주는 그리디를 생각해봅시다. 그리고 이러한 수식을 만족하는 인접한 두 원소가 존재하면 바꿔주는 시행을 반복해봅시다. 이때 얻어지는 순서를 $ P $ 라고 할때, $ P $ 가 최적일 것 같습니다. 정말 $ P $ 가 최적해를 가질까요? 이를 증명해봅시다.
$ Sum(T_{k_1}\sim T_{k_{i-1}}) \times (S_{k_i} + S_{k_{i+1}}) $ 이 두 수식에서 모두 나타나므로 대소관계에는 영향을 주지 않으니 정리해서 부등식으로 나타내봅시다.
식을 정리하면 $ K_i $ , $ K_{i+1} $ 에 관한 식으로 만들어집니다.
부등식은 $ T_{k_i} \times S_{k_{i+1}} \geq T_{k_{i+1}} \times S_{k_i} $ 가 되고, 저 식을 만족한다면 두 작업 순서를 바꿔주고 있는 것이죠.
위 식을 조금 더 정리하면, $ \frac{T_{k_i}}{S_{k_i}} \geq \frac{T_{k_{i+1}}}{S_{k_{i+1}}} $ 이 됩니다. 그러면, $ P $ 는 $ \frac{T_i}{S_i} $ 로 정렬한 순서라는 것을 알 수 있습니다. 이는 임의의 순서 $ Q $ 에서 앞서 말한 그리디 전략을 수행했을 때, 항상 $ P $ 와 똑같이 만들 수 있다는 것의 증명이 됩니다. 그러면 $ P $ 가 아닌 임의의 최적해 $ P* $ 가 존재할 때, $ P* $ 에서도 손실을 발생시키지 않으면서 항상 $ P $ 로 만들어줄 수 있다는 뜻이 되므로 $ P $ 가 $ P* $ 보다 작지 않습니다. 따라서 우리가 구한 $ P $ 도 최적해가 됩니다.
이로써 위의 Exchange argument를 증명하였습니다.
위의 사실을 조금 더 응용해봅시다.
SW 역량테스트(링크)
앞서 말한 문제에서는 모든 작업을 시행해야 했기에 그냥 정렬해서 출력하면 됐지만, 이 문제는 제한시간 $ T $ 내에 몇개의 작업을 골라서 순서 또한 정해야 한다는 점이 다릅니다. 한편으로는, 이미 수행할 작업들의 목록이 정해져 있다면 그때의 순서를 정하는 것은 위 문제와 동일하게 생각할 수 있는데요. 마찬가지로, $ \frac{R_i}{P_i} $ 로 정렬해서 순서를 정한 다음에 걸리는 시간을 기준으로한 냅색DP를 통해 수행할 작업의 목록을 정해주면 됩니다.
typedef long long ll;
struct node {
int m, p, r;
} vec[50];
int dp[100001];
int main() {
int n, t;
scanf("%d %d", &n, &t);
for (int i = 0; i < n; i++) scanf("%d", &vec[i].m);
for (int i = 0; i < n; i++) scanf("%d", &vec[i].p);
for (int i = 0; i < n; i++) scanf("%d", &vec[i].r);
sort(vec, vec + n, [](node v1, node v2) {
return (ll)v1.r * v2.p < (ll)v2.r * v1.p;
});
memset(dp, -1, sizeof(dp));
dp[0] = 0;
for (int i = 0; i < n; i++) {
for (int j = t; j >= vec[i].r; j--)
if (dp[j - vec[i].r] != -1)
dp[j] = max((ll)dp[j], dp[j - vec[i].r] + vec[i].m - (ll)j * vec[i].p);
}
int mav = 0;
for (int i = 0; i <= t; i++) mav = max(mav, dp[i]);
printf("%d", mav);
}
Exchange Argument를 이용하여 문제를 해결할 때, $ P $ 가 아닌 임의의 최적해 $ P* $ 가 존재할 때 $ P* $ 에서도 손실을 발생시키지 않으면서 항상 $ P $ 로 만들어줄 수 있다는 보장이 필요하기 때문에, 위의 두 문제와 같이 명확하게 특정기준으로 정렬해놓고 문제를 해결하는 경우가 대부분입니다.
여태까지, Exchange Argument를 이용하여 두 스케쥴링 문제들을 해결해봤습니다.
직사각형(링크)
이 문제와 같이 스케쥴링이 아닌 문제도 Exchange Argument를 이용하여 해결할 수 있습니다. 같은 길이의 막대쌍을 다 짝지어놓고, 남는 막대의 길이는 1 줄이는 방식으로 직사각형의 두 변에 사용 될 막대쌍들의 집합을 정해놓습니다. 결론부터 말하자면, 최적해는 길이 순서대로 두 막대쌍끼리 직사각형을 만드는 것을 반복하는 것이 됩니다. 이를 증명해봅시다.
일단, 막대쌍들을 임의대로 짝지어서 직사각형들을 만들어 놓아봅시다. 이제 임의의 두 직사각형을 골랐을 때, 사용된 막대쌍들이 각각 $ A,B,C,D $ 이고 $ A\leq B\leq C\leq D $ 라고 할때, 막대쌍들을 최적으로 분배하는 방법은 $ A \times B + C \times D $ 로 짝짓는 것이 될 것입니다. 이런 식으로 두 직사각형을 고르고 재분배를 계속 하다보면 결국, 길이 순서대로 막대쌍을 짝지은 직사각형들이 만들어집니다. 이렇게 만들어진 직사각형들은 최적해일까요? 앞선 문제와 마찬가지로 임의의 최적해 $ P* $ 에서 손실을 발생시키지 않으면서, 항상 $ P $ 로 만들수 있기에 위 Exchange Argument가 성립한다는 것을 보일 수 있습니다.
이제, 이를 이용해서 풀 수 있는 문제 몇가지를 간략하게 소개하고 글을 마치겠습니다.
Installing Apps(링크)
설치할 앱들의 리스트가 정해져 있다면, 직관적으로 $ D_i-S_i $ 가 큰 순서대로 설치하는 것이 유리하다는 사실을 알 수 있습니다. 이 순서로 정렬하고 냅색 DP를 해주면 됩니다. 위의 두 스케쥴링 문제와 마찬가지로 인접한 두 원소의 교환에서 다른 원소들에게 영향을 주지 않기에 두 원소에서 유리한 선택을 해주는 것을 반복하는 것으로 이해할 수 있습니다.
Level Up(링크)
각 구간을 L1, L2라고 할때, L1 다음에 L2를 넣겠다는 생각을 포기합시다. 어떤 원소를 L1에 넣을 지, L2에 넣을 지, 넣지 않을지로 냅색 DP하는 것을 생각할 수 있습니다. 이때 L1에 넣을 원소의 리스트가 정해져 있다면, $ X_i $ 가 작은 순서대로 넣는 것이 그렇지 않은 것보다 더 많은 경우의 수를 가지고 있다는 걸 알 수 있습니다. 마찬가지로 Exchange Argument로 생각할 수 있습니다.
FarmCraft(링크)
노드 X에서 다음으로 노드 Y를 방문했을 때, X로 돌아오기 전에 Y의 서브트리를 전부 방문하고 오는 것이 유리하겠죠. 이제, 어느 서브트리를 먼저 방문할 것인지에 대한 순서를 정해야하고 Exchange Argument로 해결할 수 있습니다.
Touch the sky(링크)
어떤 풍선을 터트릴 지 리스트를 정했다면, $ L_i + D_i $ 가 작은 순서대로 터트리는 것이 유리합니다. 이제 적절한 전략으로 그 리스트를 정해주면 됩니다.
Exchange Argument는 직관적으로 보이는 것에 대해 증명할 때도, 풀이가 보이지 않는 경우에도 유용하게 사용할 수 있는 전략으로 보입니다. 이런 유형의 문제들은 대부분 재미도 있어서 꼭 배워보시는 것을 추천드립니다.
긴 글 읽어주셔서 감사합니다.