채무 간소화가 송금 횟수를 최소화하는 원리
지출을 기록하면 계산기가 복잡하게 얽힌 채무 관계를 최소한의 송금으로 정리합니다. 이 기법을 ‘채무 간소화(Debt Simplification)’라고 합니다.
1. 각자의 순잔액 계산
각 멤버에 대해 ‘지불한 총액 − 부담해야 할 총액’을 계산합니다. 양수면 받을 사람, 음수면 낼 사람입니다.
2. 가장 큰 채무자와 가장 큰 채권자 매칭
가장 많이 빚진 사람과 가장 많이 받을 사람을 짝지어 한 번의 송금으로 양쪽 잔액을 최대한 상쇄합니다.
3. 모두 0이 될 때까지 반복
매칭할 때마다 금액이 작은 쪽 잔액이 상쇄되어 사라지고, 다음 쌍으로 넘어갑니다. 이 그리디 방식은 최소 송금 횟수를 보장합니다.