줄다리기 알고리즘: 두 그룹의 합 차이를 최소화하는 분할 방법

줄다리기 알고리즘이란?

줄다리기(Tug of War) 알고리즘은 주어진 정수 집합을 두 그룹으로 나누되, 각 그룹에 속한 숫자들의 합이 서로 최대한 비슷해지도록 분할하는 문제입니다. 실제 줄다리기 경기에서 양 팀의 힘이 균형을 이루도록 팀을 편성하는 것과 같은 원리입니다.

분할 조건

원소 개수 n이 짝수인 경우: 두 부분집합의 크기는 각각 n/2로 같아야 합니다.
원소 개수 n이 홀수인 경우: 한쪽 부분집합은 (n-1)/2개, 다른 쪽은 (n+1)/2개로 나눕니다.

입력 및 출력 예시

입력: 서로 다른 무게들의 집합
{23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}

출력: 합의 차이가 최소가 되도록 좌우 부분집합을 배분
Left: {45, -34, 12, 98, -1}
Right: {23, 0, -99, 4, 189, 4}

알고리즘 동작 원리

이 알고리즘은 백트래킹(backtracking) 기법을 사용합니다. 각 원소마다 '현재 그룹에 포함한다 / 포함하지 않는다' 두 가지 경우를 모두 탐색하되, 남은 원소만으로 절반을 채울 수 없는 경우는 미리 잘라내는(가지치기) 방식으로 탐색 범위를 줄입니다.

함수 호출 형식은 다음과 같습니다.

tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos)

매개변수 설명

weight: 주어진 무게(정수) 배열
n: 전체 원소의 개수
curr: 현재 탐색 단계에서의 선택 여부를 기록하는 리스트
select: 지금까지 선택한 원소의 개수
sol: 최종 해답(좌·우 부분집합)을 저장하는 배열
diff: 두 부분집합 합의 최소 차이
sum: 전체 원소의 합
total: 현재 선택된 부분집합의 합
pos: 현재 검사 중인 원소의 위치

의사 코드

Begin
    if pos = n then                     // 모든 원소를 확인한 경우 종료
        return
    if (n/2 - select) > (n - pos) then  // 남은 원소로 절반을 채울 수 없으면 가지치기
        return
    // 현재 원소를 선택하지 않는 경우 탐색
    tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos+1)
    select := select + 1
    total := total + weight[pos]
    curr[pos] := true                   // pos 위치의 원소를 선택

    if select = n/2 then                // 절반을 모두 선택한 경우
        if |sum/2 - total| < diff then  // 더 나은 해답인지 확인
            diff := |sum/2 - total|
            for i := 0 to n do
                sol[i] := curr[i]       // 현재 선택 상태를 해답으로 저장
            done
    else
        tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos+1)
    curr[pos] := false                  // 백트래킹: 선택을 되돌림
End

C++ 구현 예제

#include <iostream>
#include <cmath>
using namespace std;

void tugOfWar(int* weight, int n, bool curr[], int select, bool sol[], int &diff, int sum, int total, int pos) {
    if (pos == n)          // 모든 원소를 확인한 경우
        return;
    if ((n/2 - select) > (n - pos))   // 남은 원소가 부족하면 탐색 중단
        return;
    tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos+1);

    select++;
    total += weight[pos];
    curr[pos] = true;      // 현재 원소를 해답 후보에 포함

    if (select == n/2) {   // 절반이 선택되면 하나의 해가 완성됨
        if (abs(sum/2 - total) < diff) {   // 기존보다 나은 해답인지 검사
            diff = abs(sum/2 - total);
            for (int i = 0; i<n; i++)
                sol[i] = curr[i];
        }
    } else {
        tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos+1);
    }
    curr[pos] = false;     // 백트래킹: 선택 해제
}

void findSolution(int *arr, int n) {
    bool* curr = new bool[n];
    bool* soln = new bool[n];
    int diff = INT_MAX;    // 최소 차이를 무한대로 초기화
    int sum = 0;

    for (int i=0; i<n; i++) {
        sum += arr[i];                 // 전체 원소의 합 계산
        curr[i] = soln[i] = false;     // 모든 선택 상태 초기화
    }

    tugOfWar(arr, n, curr, 0, soln, diff, sum, 0, 0);
    cout << "Left: ";

    for (int i=0; i<n; i++)
        if (soln[i] == true)
            cout << arr[i] << " ";
    cout << endl << "Right: ";

    for (int i=0; i<n; i++)
        if (soln[i] == false)
            cout << arr[i] << " ";
}

int main() {
    int weight[] = {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4};
    int n = 11;
    findSolution(weight, n);
}

실행 결과

Left: 45 -34 12 98 -1
Right: 23 0 -99 4 189 4

시간 복잡도

각 원소를 포함하거나 제외하는 두 가지 선택지가 있으므로, 이론상 시간 복잡도는 O(2ⁿ)입니다. 다만 가지치기를 통해 남은 원소가 부족한 경우를 조기에 제외하기 때문에, 실제 탐색 공간은 전체 2ⁿ보다 훨씬 작아집니다.