재배열 부등식 계산기

같은 방향으로 정렬해 같은 위치끼리 곱해 더한 합이 두 수열을 어떻게 짝지어도(어떤 순열로 곱해도) 나올 수 있는 값 중 가장 크고, 반대 방향으로 정렬해 곱한 합이 가장 작다는 정리입니다. 임의의 순서로 짝지은 합은 항상 이 최댓값과 최솟값 사이에 있습니다.

정리 자체가 "정렬만 하면 최댓값·최솟값이 나온다"는 것을 보장하기 때문입니다. 두 수열을 각각 오름차순으로 정렬해 곱하면 최댓값, 한쪽만 내림차순으로 정렬해 곱하면 최솟값이 나옵니다. 이 계산기도 정렬 두 번만으로 계산합니다.

인접 교환 논증으로 증명됩니다. aᵢ<aⱼ인데 짝지어진 b가 거꾸로(bᵢ>bⱼ) 매칭돼 있다면 그 둘의 b를 맞바꿔도 합이 줄지 않습니다((aⱼ−aᵢ)(bⱼ−bᵢ) ≥ 0이 되도록). 이런 "거꾸로 된 쌍"이 하나도 없을 때까지 반복하면 같은 순서로 정렬된 상태, 즉 최댓값에 도달합니다.

두 수열 중 하나라도 모든 값이 같으면(상수 수열) 어떤 순서로 짝지어도 합이 같아 최댓값과 최솟값이 일치합니다. 그 밖에는 순서가 완전히 같을 때만 최댓값에, 완전히 반대일 때만 최솟값에 등호가 성립합니다.

예를 들어 여러 작업의 소요 시간과 가중치가 있을 때, 가장 오래 걸리는 작업에 가장 낮은 가중치(또는 그 반대)를 배정하는 식으로 총합을 최소화·최대화하는 스케줄링 문제의 근거가 됩니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지고 넣은 값은 이 기기에만 남습니다.