더치페이 모임 회비 정산 공식과 송금 횟수 최소화 그래프 알고리즘

직접 해보기 →

동호회 활동, 대학 동창 모임, 혹은 친구들과의 여행을 마친 뒤에는 어김없이 비용 정산의 순간이 찾아옵니다. 누구는 숙소를 결제했고, 다른 사람은 식비를 냈으며, 또 다른 사람은 입장료를 결제했다면 지출 내역이 뒤엉켜 서로가 서로에게 얼마를 보내야 하는지 복잡해집니다. 이 상황에서 단순 n분의 1을 하여 송금을 주고받으면 수많은 송금 트랜잭션이 유발되어 번거롭습니다. 본 글에서는 이 송금 횟수를 극한으로 줄이는 정산 알고리즘을 수학적으로 분석합니다.

---

1. 개별 순 잔액(Net Balance) 산출 공식

정산에 참여하는 총인원수를 $N$, 각 멤버의 인덱스를 $i$ ($1 \le i \le N$)라 합시다. 모임에서 발생한 총 비용($C_{\text{total}}$)은 모든 멤버가 개별적으로 먼저 지출한 금액($P_i$)의 합산입니다:

[ C_{\text{total}} = \sum_{i=1}^{N} P_i ]

각자 동등하게 부담해야 할 1인당 평균 분담금($A$)은 단순 평균값입니다: [ A = \frac{C_{\text{total}}}{N} ]

각 멤버 $i$가 최종적으로 더 내야 하거나(음수) 돌려받아야 하는(양수) 순 잔액($B_i$)은 자신이 선지출한 금액에서 분담금을 뺀 값으로 정의됩니다: [ B_i = P_i - A ]

이때 모든 가입 멤버의 순 잔액 합계는 제로섬(Zero-sum) 상태를 충족합니다: [ \sum_{i=1}^{N} B_i = 0 ]

---

2. 송금 경로 최소화(Simplify Debts) 알고리즘

수십 번의 송금을 방지하고 가장 효율적인 정산 루트를 확보하기 위해, 컴퓨터 공학에서는 그리디(Greedy) 그래프 간소화 기법을 활용합니다.

청산 처리 단계:

1. 모든 멤버의 순 잔액($B_i$)을 계산하여 가장 많이 받아야 하는 채권자 그룹(최대 양수 $B_{\text{creditor}}$)과 가장 많이 줘야 하는 채무자 그룹(최대 음수 $B_{\text{debtor}}$)으로 분류하여 각각 정렬(Sorting)합니다.
2. 가장 빚이 많은 채무자가 가장 받을 돈이 많은 채권자에게 돈을 이체합니다. 이때 이체하는 금액 $T$는 두 잔액의 절대값 중 작은 값입니다: [ T = \min(|B_{\text{debtor}}|, B_{\text{creditor}}) ]
3. 두 멤버의 잔액을 이체액 $T$만큼 업데이트합니다:
   • 채무자 잔액: $B_{\text{debtor}} \leftarrow B_{\text{debtor}} + T$
   • 채권자 잔액: $B_{\text{creditor}} \leftarrow B_{\text{creditor}} - T$
4. 순 잔액이 0이 된 멤버는 리스트에서 소거하고, 남은 인원들에 대해 모든 잔액이 0이 될 때까지 1~3단계를 재귀적으로 반복합니다.

가상 예제:

• 멤버: A, B, C (3명, 분담금 3만 원)
• 선지출액: A=9만 원, B=0원, C=0원
• 순 잔액 ($B$): A = +6만 원, B = -3만 원, C = -3만 원
• 알고리즘 매칭:
  • 가장 빚이 많은 B(-3만)가 A(+6만)에게 3만 원 송금 $\rightarrow$ B는 0원으로 완결, A 잔액 +3만 원으로 조정.
  • 다음으로 빚이 많은 C(-3만)가 A(+3만)에게 3만 원 송금 $\rightarrow$ C와 A 모두 0원으로 청산 완료.

송금 경로는 오직 2회만 유발되어 매우 깔끔한 금융 정산 가이드가 도출됩니다.

[!NOTE] 모임 회비 정산 계산기는 이러한 그리디 최소 송금 알고리즘이 브라우저 백엔드단에 적용되어 있습니다. 멤버 이름과 복수 지출 항목만 나열해 적으면 한 명이 다 이체받아 다시 쪼개어 송금하는 수고로움 없이, 멤버 개개인이 직접 이체해야 할 대상 계좌와 액수를 직관적으로 안내해 줍니다.

---

3. 복잡한 가변 분담 비율(가중 정산) 적용

경우에 따라 지참 술을 안 마신 사람, 뒤늦게 2차부터 참석한 사람 등 **가중 분담 비율(%)**을 반영해야 하는 경우가 있습니다. 이 역시 각 참가자별 가중치 계수 $W_i$ ($0 \le W_i \le 1.0$)를 1인당 분담 공식 분모에 결합하여 수정 잔액을 유도하는 수학 모형을 적용하면 공정한 소수점 정산 처리가 능히 가능합니다.