여행 정산 앱을 만들면서 참가자들이 마지막에 주고받아야 할 송금 횟수를 줄이는 기능을 구현했습니다.

누가 얼마를 보내고 받아야 하는지는 각자의 잔액으로 계산할 수 있었습니다. 하지만 같은 잔액이라도 사람을 연결하는 방법에 따라 송금 횟수는 달라질 수 있었습니다. 단순히 보낼 사람과 받을 사람을 순서대로 연결하는 것을 넘어, 가능한 조합 중 송금 횟수가 가장 적은 계획을 찾아야 했습니다.

처음 구현은 AI가 작성한 재귀 탐색 알고리즘이었습니다.

잘 읽히지 않던 재귀 탐색

재귀 탐색은 참가자 한 명의 잔액을 다른 참가자의 잔액과 맞추고, 남은 잔액으로 다음 경우를 계속 탐색하는 구조였습니다. 작은 입력에서는 결과가 나왔고 테스트도 통과했습니다.

다만 코드를 읽었을 때 탐색이 어떤 순서로 진행되는지 바로 이해하기 어려웠습니다. 어떤 경우를 이미 확인했는지, 참가자가 늘어나면 탐색 범위가 어느 정도까지 커지는지도 판단하기 쉽지 않았습니다.

AI가 작성한 코드였기 때문에 동작 결과만 확인하고 넘어갈 수도 있었습니다. 하지만 이후에 문제가 생겼을 때 제가 수정 범위를 정하기 어렵겠다는 생각이 들었습니다.

처음에는 재귀로 동작하는 작업을 병렬로 나누면 더 빠르게 처리할 수 있는지 물어봤습니다. 성능을 개선하려는 질문이기도 했지만, 실제로는 알고리즘의 실행 구조를 조금 더 이해하기 위한 질문에 가까웠습니다.

병렬화 질문에서 발견한 문제

병렬 처리를 검토하면서 어려운 20명 입력을 실행해봤습니다. 이 과정에서 프로세스가 OOMKilled로 종료됐습니다.

문제는 작업을 하나씩 처리하는 속도만이 아니었습니다. 참가자가 늘어나면서 확인해야 할 조합과 중간 상태가 빠르게 증가하고 있었습니다. 이를 병렬로 실행하면 전체 상태 수가 줄어드는 것이 아니라, 여러 탐색이 동시에 메모리를 사용할 가능성이 있었습니다.

처음에 생각했던 병렬화는 근본적인 해결책이 아니었습니다. 알고리즘이 다루는 상태의 범위를 먼저 제한할 수 있어야 했습니다.

이 문제는 평소 사용하던 적은 인원의 예시만 확인했다면 발견하기 어려웠을 것입니다. 코드가 잘 읽히지 않아 질문을 이어가다 보니, 실제로 어느 정도의 입력까지 안전하게 처리할 수 있는지도 확인하게 됐습니다.

상태 수를 설명할 수 있는 구조로 바꾸기

재귀 탐색은 참가자 부분집합을 이용한 동적 계획법으로 교체했습니다.

각 참가자의 잔액을 더했을 때 합계가 0이 되는 그룹을 많이 만들수록, 그룹 사이에 추가 송금이 필요하지 않습니다. 전체 참가자가 n명이고 서로 독립적인 0원 그룹이 g개라면 최소 송금 수는 n - g로 계산할 수 있었습니다.

새 알고리즘은 참가자의 포함 여부를 비트로 표현하고, 각 부분집합의 잔액 합과 만들 수 있는 0원 그룹의 최대 개수를 저장합니다. 재귀적으로 같은 상태를 여러 경로에서 탐색하는 대신, 참가자 부분집합마다 하나의 상태를 계산하는 방식입니다.

시간 복잡도는 O(n × 2ⁿ), 공간 복잡도는 O(2ⁿ)이었습니다. 여전히 참가자가 많아지면 비용이 빠르게 증가하지만, 필요한 상태 수를 미리 계산할 수 있었습니다.

현재는 잔액이 남은 참가자를 최대 20명으로 제한했습니다. 이 경우 부분집합은 최대 1,048,576개가 됩니다. 같은 금액끼리 바로 짝지어지지 않는 20명 입력도 회귀 테스트에 추가했습니다.

지원 범위를 무제한으로 열어두기보다, 앱에서 감당할 수 있는 입력 범위와 그때 필요한 자원을 함께 정한 셈입니다.

이해할 수 있어야 확인할 수 있었던 것

새 알고리즘 역시 AI가 작성했습니다. 다만 이번에는 결과만 받아들이지 않고 비트마스크가 참가자 부분집합을 표현하는 방법, 부분집합의 합을 재사용하는 과정과 최종 송금 순서를 복원하는 흐름을 따라가며 확인했습니다.

이 과정에서 알고리즘을 직접 처음부터 작성하는 것과, 작성된 알고리즘을 이해하고 제품의 조건에 맞게 검증하는 것은 서로 다른 작업이라는 생각이 들었습니다.

코드가 잘 읽히지 않는다는 사실이 항상 잘못된 구현을 의미하지는 않습니다. 하지만 실행 범위와 변경 영향을 설명하기 어렵다면, 어떤 입력까지 안전한지 판단하기도 어려웠습니다.

이번에는 “재귀를 병렬로 실행하면 나아질까?”라는 작은 질문이 메모리 문제를 발견하는 계기가 됐습니다. 질문하지 않았다면 정상적인 예시에서 결과가 나온다는 이유로 기존 구현을 그대로 둘 수도 있었습니다.

알고리즘을 완전히 익숙한 코드로 바꾸는 것보다, 적어도 왜 이 구조를 선택했고 어디까지 동작하도록 만들었는지를 설명할 수 있는 상태로 두는 편이 이후의 변경과 검토에 도움이 됐습니다.