친구 여러 명이 서로에게 돈을 빌려주고 빌린 상황을 생각해 봅시다. 이처럼 금전 거래가 얽혀 있으면 친구 관계망 안에 여러 갈래의 현금 흐름이 발생합니다. 우리가 풀어야 할 과제는 바로 네트워크 전체의 현금 흐름, 즉 거래 건수와 이동 금액을 최소한으로 줄이는 것입니다.
예를 들어 P1, P2, P3라는 세 명의 친구가 있다고 가정하면, 이들 사이의 현재 현금 흐름은 아래와 같습니다.
위 다이어그램의 현금 흐름은 아직 최소화되지 않은 상태입니다. 불필요한 중간 거래를 걷어내고 깔끔하게 정산하면 최종적으로 다음과 같은 단순한 구조가 됩니다.
접근 방법: 그리디(Greedy) 알고리즘
이 문제는 그리디(탐욕) 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 단계마다 한 사람의 모든 채권·채무를 완전히 정산한 뒤, 나머지 n-1명에 대해 같은 작업을 재귀적으로 반복하는 것입니다.
그렇다면 첫 번째로 정산할 사람은 어떻게 고를까요? 답은 각 사람의 순액(net amount)을 계산하는 것입니다. 순액은 '받아야 할 총 금액(채권)'에서 '갚아야 할 총 금액(채무)'을 뺀 값입니다. 순액을 모두 구한 뒤 최솟값과 최댓값을 가진 두 노드를 찾으면, 각각 가장 많이 빚진 사람(최대 채무자)과 가장 많이 받을 사람(최대 채권자)이 됩니다. 이때 최솟값을 가진 사람부터 정산을 시작합니다.
알고리즘 단계
- 모든 사람 Pi(0 ≤ i ≤ n-1)에 대해 다음 단계를 수행합니다.
- 각 사람의 순액을 계산합니다. 사람 i의 순액은 총 채권 합계에서 총 채무 합계를 뺀 값입니다.
- 순액이 가장 큰 사람(최대 채권자 Pc)과 가장 작은 사람(최대 채무자 Pd)을 찾습니다. Pc가 받을 최대 금액을 max_credit, Pd가 지불할 최대 금액을 max_debit이라 하겠습니다.
- x := max_credit과 max_debit 중 더 작은 값으로 설정한 뒤, Pd에서 x만큼 차감하여 Pc에게 x만큼 입금합니다.
- x가 max_credit과 같다면 Pc의 정산이 완료된 것이므로 Pc를 대상 집합에서 제외하고, 남은 n-1명에 대해 재귀 호출합니다.
- x가 max_debit과 같다면 마찬가지로 Pd를 제외하고, 남은 n-1명에 대해 재귀 호출합니다.
C++ 구현 예제
#include<iostream>
#include<algorithm>
#define N 3
using namespace std;
int getMinIndex(int arr[]) {
int minInd = 0;
for (int i=1; i<N; i++)
if (arr[i] < arr[minInd])
minInd = i;
return minInd;
}
int getMaxIndex(int arr[]) {
int maxInd = 0;
for (int i=1; i<N; i++)
if (arr[i] > arr[maxInd])
maxInd = i;
return maxInd;
}
void cashFlowTask(int amount[]) {
int max_credit = getMaxIndex(amount), max_debit = getMinIndex(amount);
if (amount[max_credit] == 0 && amount[max_debit] == 0)
return;
int min_val = min(-amount[max_debit], amount[max_credit]);
amount[max_credit] -= min_val;
amount[max_debit] += min_val;
cout << "P" << max_debit << " sends " << min_val << " to " << "P" << max_credit << endl;
cashFlowTask(amount);
}
void minCashFlow(int graph[][N]) {
int amount[N] = {0};
for (int p=0; p<N; p++)
for (int i=0; i<N; i++)
amount[p] += (graph[i][p] - graph[p][i]);
cashFlowTask(amount);
}
int main() {
int graph[N][N] = {
{0, 1000, 2000},
{0, 0, 5000},
{0, 0, 0}};
minCashFlow(graph);
}실행 결과
P1 sends 4000 to P2 P0 sends 3000 to P2
즉, P1이 P2에게 4,000을 송금하고 P0이 P2에게 3,000을 송금하면 모든 부채가 정산됩니다.
동작 원리와 시간 복잡도 분석
예제 입력에서 graph[i][j]는 "i번 사람이 j번 사람에게 갚아야 할 금액"을 의미합니다. 초기 거래는 P0→P1 1,000, P0→P2 2,000, P1→P2 5,000으로 총 3건, 8,000이 오갑니다.
minCashFlow 함수가 계산한 각 사람의 순액은 다음과 같습니다.
- P0 : -1,000 - 2,000 = -3,000 (채무자)
- P1 : +1,000 - 5,000 = -4,000 (채무자)
- P2 : +2,000 + 5,000 = +7,000 (채권자)
그리디 정산을 거치면 거래는 2건(P1→P2 4,000, P0→P2 3,000)으로 줄어들고, 총 이동 금액 역시 8,000에서 7,000으로 감소합니다. 이렇게 중간 경유 없이 채권자와 채무자를 직접 연결함으로써 현금 흐름이 최소화됩니다.
시간 복잡도를 살펴보면, 순액 계산에 O(N²), 재귀 호출마다 최대·최솟값 탐색에 O(N)이 소요되므로 전체 시간 복잡도는 O(N²)입니다. 공간 복잡도는 순액을 저장하는 배열 때문에 O(N)입니다.
이처럼 그리디 알고리즘을 활용하면 친구 간에 얽힌 복잡한 부채 관계도 최소한의 거래로 깔끔하게 정산할 수 있습니다.