모두에게 공평한 모임 장소 추천하기 (2) - 후보 탐색 알고리즘 만들기

2026년 8월 18일

들어가며

이전 글에서는 장소 추천의 토대가 되는 경로 조회를 외부 API에서 MOTIS 자체 운영으로 옮기고, 그 엔진을 운영하기 위한 배포와 모니터링을 구성한 과정을 다루었다. 이번 글에서는 그 위에서 실제로 장소 후보를 찾아내는 알고리즘을 서술하고자 한다.

알고리즘의 구상은 내가 맡았고, 초기 구현은 팀원이 진행했다. 그래서 각 단계를 어떻게 구현했는지 먼저 살펴보고, 그 안에서 설계한 의도와 어긋나 있던 부분을 함께 짚어보려 한다.

파이프라인

경로 조회 횟수 제약이 사라지고 나니 파이프라인은 다음과 같이 정리할 수 있었다.

단계	하는 일
1	참여자 출발지 좌표 수집
2	기하중심 계산 (Weiszfeld)
3	기하중심 주변으로 후보 좌표 생성 (Polar Sampling)
4	직선 거리 기반 1차 필터링
5	MOTIS 이동 시간 조회 → 점수 계산 → 상위 3개 선발
6	카카오 POI 매칭 후 POI 좌표 기준으로 재계산 → 최종 순위 확정

위 파이프라인의 경우 먼저 연산 비용이 낮은 계산으로 후보를 최대한 줄이고, 연산 비용이 높은 계산의 경우 살아남은 후보를 대상으로만 쓰는 구조이다. 직선 거리 계산에는 비용이 들지 않지만 경로 조회의 경우 API 호출(네트워크 왕복)이 필요하고 POI 검색은 여전히 외부 API 호출이기 때문이다.

이제 각 단계를 순서대로 살펴보도록 하자.

기하중심 계산

기하중심(Geometric Median)은 모든 참여자 좌표까지의 거리 합이 최소가 되는 점이다. 산술 평균과 달리 한 명이 멀리 떨어져 있어도 크게 끌려가지 않는다. 닫힌 형태의 해가 없어서 Weiszfeld 알고리즘으로 반복 근사한다.

Coordinate current = arithmeticMean(coordinates);

for (int i = 0; i < MAX_ITERATIONS; i++) {
    Coordinate next = weiszfeldStep(current, coordinates);

    if (current.distanceTo(next) < CONVERGENCE_THRESHOLD_KM) {
        return next;
    }
    current = next;
}

여기서 두 가지 문제가 있었다.

첫째, 반복 단계 안에서 단위가 섞여 있었다. Weiszfeld 스텝은 각 좌표까지의 거리의 역수를 가중치로 삼아 가중 평균을 구한다. 그런데 가중치를 만드는 거리는 Haversine 공식으로 구한 구면 거리(km) 였고, 정작 갱신되는 값은 위경도(degree) 공간의 좌표였다. 척도가 다른 두 공간을 섞어 쓰면 Weiszfeld가 전제하는 수렴 성질이 성립하지 않는다.

// 좌표 갱신이 degree 공간에서 이루어지므로 거리도 같은 공간에서 재야 한다
double dLat = coord.latitude() - current.latitude();
double dLon = coord.longitude() - current.longitude();
double distance = Math.sqrt(dLat * dLat + dLon * dLon);

가중치 계산을 좌표 공간과 같은 Euclidean 거리로 통일했다. 서울 정도 범위에서는 degree 공간의 왜곡이 결과에 의미 있는 차이를 만들지 않고, 무엇보다 알고리즘이 전제하는 성질을 지키는 쪽이 맞다고 판단했다.

둘째, 수렴 임계값이 사실상 도달 불가능한 값이었다. 임계값은 1e-7이었고 주석에는 "약 0.01m 수준"이라고 적혀 있었다. 하지만 비교 대상인 distanceTo()가 km를 반환하므로 1e-7 km는 0.0001mm다. 당연히 수렴 판정이 걸릴 리 없었고, 이 함수는 매번 최대 반복 횟수 300회를 전부 돌고 나서 근사값을 반환하고 있었다. 결과 자체는 그럴듯했기 때문에 눈에 띄지 않았을 뿐이다.

이후 1e-4 km, 즉 0.1m로 조정하니 결과가 보통 10~30회 안에 수렴하였다. 이제 수렴 실패는 정상 흐름이 아니라 예외 상황이므로, 300회를 다 돌면 경고 로그를 남기도록 했다.

log.warn("Geometric median did not converge after {} iterations, returning approximation",
        MAX_ITERATIONS);

후보 좌표 생성

후보 위치를 기하중심 하나만 놓고 판단할 수는 없었다. 그 지점이 하필 강 위이거나, 역에서 한참 떨어진 골목일 수 있기 때문이다. 그래서 중심을 기준으로 반경(r)과 각도(θ)를 조합해 방사형으로 후보 좌표를 만들었다.

private static final double ALPHA = 0.6;
private static final double R_MIN_KM = 0.6;
private static final double[] RADIUS_RATIOS = {0.25, 0.5, 0.75, 1.0};

탐색 반경은 max(dMax × 0.6, 0.6km)로 잡는다. 여기서 dMax는 기하중심에서 가장 멀리 있는 참여자까지의 거리다. 참여자들이 멀리 흩어져 있으면 넓게, 가까이 모여 있으면 좁게 보되 최소 반경은 보장한다.

생성 자체는 단순하다. 중심 좌표를 후보에 하나 넣고, 반경을 네 단계로 나눈 뒤 각 단계마다 정해진 각도 간격으로 한 바퀴 돌며 좌표를 만든다.

candidates.add(center);

for (double ratio : RADIUS_RATIOS) {
    double r = radius * ratio;
    for (int angle = 0; angle < 360; angle += angleStep) {
        candidates.add(center.move(r, angle));
    }
}

기준 좌표에서 거리와 각도만큼 이동한 좌표를 구하는 일은 Coordinate.move()가 맡는다. 지구를 구로 보고 계산하기 때문에, 위경도에 단순히 값을 더하는 방식과 달리 위도에 따라 경도 간격이 달라지는 것까지 반영된다.

문제는 각도 간격이었다. 목표 후보 수(30개 내외)를 맞추기 위해 각도 간격을 계산하는데, 기존 방식은 목표 후보 수에서 중심 좌표 하나를 뺀 29개를 반경 네 단계에 나눠 담는다고 보고, ceil(360 × 4 / 29) = 50처럼 나눗셈으로 간격을 구하고 있었다. 그런데 50은 360의 약수가 아니다. 360 / 50이 정수 나눗셈으로 7이 되면서 실제 생성 개수가 목표에 못 미쳤고, 더 큰 문제는 마지막 구간의 각도가 잘려 후보의 방향이 고르게 분포하지 않는다는 점이었다. 특정 방향이 다른 방향보다 촘촘하게 탐색되는 셈이다.

그래서 360의 약수만 후보로 두고, 그중 목표 개수에 가장 가까운 값을 고르도록 변경하였다.

for (int step = 1; step <= 360; step++) {
    if (360 % step != 0) continue; // 균등 각도 분할을 위해 360의 약수만 허용
    int count = radiusDivisions * (360 / step) + 1;
    if (count < MIN_CANDIDATES || count > MAX_CANDIDATES) continue;
    int diff = Math.abs(count - TARGET_CANDIDATES);
    if (diff < bestDiff) {
        bestDiff = diff;
        bestStep = step;
    }
}

이 조건을 만족하는 값은 45도다. 반경 네 단계에 각 단계마다 여덟 방향(360 ÷ 45)이므로 32개, 여기에 중심 좌표 하나를 더해 후보는 33개가 된다. 목표치 30개에 가장 가까우면서 360도를 균등하게 나누는 조합이다.

직선 거리로 걸러내기

앞서 말한 대로 직선 거리 계산에는 비용이 들지 않는다. 그래서 경로 조회로 넘어가기 전에 명백히 나쁜 후보는 이 단계에서 걸러낸다.

public List<Coordinate> filterByDistance(
        List<Coordinate> candidates, List<Coordinate> participants, double dMax) {

    double threshold = dMax * DISTANCE_THRESHOLD_FACTOR;

    return candidates.stream()
            .filter(candidate -> participants.stream()
                    .allMatch(p -> candidate.distanceTo(p) <= threshold))
            .collect(Collectors.toList());
}

어떤 참여자에게든 dMax × 1.2보다 멀면 제거한다. 여기서 dMax는 앞서 탐색 반경을 정할 때 쓴 값과 같다. 초기에는 이 임계값을 작게 잡아 후보가 하나도 남지 않는 경우가 있었다. 참여자들이 얼마나 흩어져 있는지에 따라 적정 반경이 완전히 달라지기 때문에, 절대값이 아니라 입력에서 유도된 값을 써야 했다.

점수 계산

살아남은 후보에 대해 참여자별 이동 시간을 조회하고, 세 지표를 조합해 점수를 매긴다. 낮을수록 좋은 점수다.

private static final double W_AVG = 0.4;
private static final double W_MAX = 0.4;
private static final double W_STDDEV = 0.2;

double score = W_AVG * avg + W_MAX * max + W_STDDEV * stddev;

평균 — 전체적으로 가까울수록 좋다.
최대 — 가장 오래 걸리는 한 명을 보호한다.
표준편차 — 특정 한 명에게만 부담이 쏠리지 않는다.

초기 가중치는 표준편차가 0.4로 가장 컸다. "공평함"이 이 기능의 핵심이니 편차를 가장 중요하게 보자는 취지였다. 그런데 이 배분에는 함정이 있다. 편차만 강조하면 모두가 똑같이 오래 걸리는 장소가 좋은 점수를 받는다. 전원이 40분씩 걸리는 곳과 대부분 15분이고 한 명만 30분인 곳을 비교하면 전자가 이겨버린다.

그래서 평균과 최대의 비중을 올리고 표준편차를 낮췄다. 표준편차는 비슷한 후보들 사이의 순위를 가르는 역할로 두는 편이 의도에 맞았다.

실제 장소 매칭

알고리즘이 찾아내는 것은 결국 위경도 한 쌍이다. 사용자에게 "위도 37.49, 경도 127.02에서 만나세요"라고 할 수는 없으므로, 후보 좌표 주변의 실제 장소, 즉 POI(Point of Interest)를 찾아 이름을 붙여야 한다.

private static final int DEFAULT_SEARCH_RADIUS_METERS = 300;
private static final String CATEGORY_GROUP_CODE = "CE7"; // 카페

카카오맵 REST API로 반경 300m 내 카페를 거리순으로 가져온다. 카페로 고정한 것은 모임의 성격을 모르는 상태에서 가장 무난한 선택지라고 판단했기 때문이다.

여기서 초기 구현이 남겨둔 문제가 하나 있었다. 쿼터를 아끼기 위해 POI를 찾은 뒤 그 장소의 좌표로 경로를 다시 계산하지 않고, 후보 좌표에서 구한 이동 시간을 그대로 표시하고 있었다. 하지만 300m 떨어진 지점은 대중교통 관점에서 전혀 다른 곳일 수 있다. 역 출구 반대편이라는 이유로 도보 시간이 붙거나, 다른 정류장을 써야 해서 환승이 하나 더 생기기도 한다. 점수를 매긴 좌표와 사용자에게 보여주는 장소가 서로 다른 지점인 셈이다.

MOTIS로 옮기고 나서는 이 재계산을 감당할 수 있게 되었다. POI 좌표를 기준으로 참여자별 경로를 다시 받아오고, 그 값으로 점수를 다시 계산한 뒤 최종 순위를 확정한다.

List<RouteInfo> routes = fetchRoutes(originalTimes, poiCoord);
List<Double> travelTimes =
        IntStream.range(0, routes.size())
                .mapToObj(j -> routes.get(j) != null
                        ? routes.get(j).travelTime()
                        : originalTimes.get(j).travelTimeSeconds())
                .toList();

ScoreResult scoreResult = scoreCalculator.calculate(travelTimes);

재계산이 실패한 참여자에 대해서는 후보 좌표의 값으로 대체한다. 한 명의 경로 조회 실패 때문에 좋은 후보 전체를 버리는 것보다는 근사값을 쓰는 편이 낫다고 보았다.

경로 조회 병렬화

여기까지 했을 때 정확도 문제는 대부분 해결할 수 있었다. 남은 것은 속도였다.

후보 30개에 참여자 5명이면 경로 조회가 150번이다. 자체 호스팅이라 개별 응답은 빠르지만, 이걸 순차로 돌면 왕복 시간이 그대로 누적된다. 그동안 사용자는 결과를 기다리고 있다.

이 작업은 전형적인 I/O 대기라고 볼 수 있다. CPU를 쓰는 게 아니라 응답을 기다리기만 한다. 그래서 Virtual Thread 기반 executor를 쓰기로 했다. 플랫폼 스레드 풀(Executors.newFixedThreadPool() 같은 기존 방식)은 크게 잡으면 메모리를 낭비하고 작게 잡으면 병렬성이 손해인데, Virtual Thread는 이런 대기 위주 작업에서 스레드 개수를 고민하지 않아도 된다.

@Bean
public Executor candidateCalculationExecutor() {
    return Executors.newVirtualThreadPerTaskExecutor();
}

호출부는 후보별로도, 참여자별로도 전부 동시에 던지고 결과를 모으는 형태로 바꿨다. 후보 30개에 참여자 5명이라면 150개의 요청이 한꺼번에 나가고, 전체 소요 시간은 150번의 합이 아니라 가장 오래 걸린 한 번에 가까워진다.

List<CompletableFuture<Double>> travelTimeFutures =
        participants.stream()
                .map(p -> CompletableFuture.supplyAsync(
                        () -> transitClient.getTravelTime(
                                p.latitude(), p.longitude(),
                                candidate.latitude(), candidate.longitude()),
                        executor))
                .toList();

한 참여자의 경로라도 조회되지 않으면 그 후보는 점수를 매길 수 없으므로 결과에서 제외한다.

다만 동시 호출을 늘리면 병목은 스레드에서 HTTP 커넥션으로 옮겨간다. 커넥션 풀링을 적용하고, 응답 없는 요청이 전체를 붙잡지 않도록 타임아웃을 걸었다.

PoolingHttpClientConnectionManagerBuilder.create()
        .setDefaultConnectionConfig(
                ConnectionConfig.custom()
                        .setConnectTimeout(Timeout.ofSeconds(5))
                        .setSocketTimeout(Timeout.ofSeconds(5))
                        .build())
        .build();

병렬화와 별개로, 요청 자체에서도 낭비를 줄일 수 있는 지점이 세 군데 있었다.

첫째, 점수 계산 단계는 이동 시간만 필요하다. 그런데 기존 코드는 점수를 매길 때도 전체 경로 정보를 받아 polyline을 디코딩하고 있었다. 지도에 그릴 경로가 필요한 것은 최종 후보 3개뿐인데, 30개 후보 전부에 대해 그 작업을 하고 있었다. 이동 시간만 반환하는 getTravelTime()을 분리했다.

public interface TransitClient {
    RouteInfo getPlan(double originLat, double originLon, double destLat, double destLon);

    default Double getTravelTime(
            double originLat, double originLon, double destLat, double destLon) {
        RouteInfo plan = getPlan(originLat, originLon, destLat, destLon);
        return plan != null ? plan.travelTime() : null;
    }
}

둘째, 대안 경로까지 받아올 필요가 없다. MOTIS는 기본적으로 여러 출발 시각에 대한 대안 경로들을 함께 돌려준다. 우리에게는 소요 시간 하나만 있으면 되므로 timetableView=false를 주어 단일 최적 경로만 탐색하도록 했다.

셋째, 기준 시각을 고정했다. 이건 성능보다 결과 안정성 문제에 가깝다. 경로를 조회하려면 출발 시각이 필요한데, 처음에는 현재 시각을 넘기고 있었다. 그러면 새벽에 계산한 결과와 낮에 계산한 결과가 달라진다. 새벽에는 첫차를 기다리는 시간이 소요 시간에 포함되어 순위에 영향이 있었다. 사용자가 실제로 모일 시각은 대체로 낮이므로, 기준 시각을 평일 정오(KST)로 고정했다.

private static final String WEEKDAY_NOON = "2026-03-09T03:00:00.000Z"; // 월요일 12:00 (KST)

이 결정에는 한계가 있다. 모임 시간이 새벽이나 주말이면 실제와 다른 기준으로 계산된다. 다만 같은 입력에 대해 항상 같은 결과가 나온다는 성질이 사용자 입장에서 더 중요하다고 판단했다.

계산 실행 흐름

알고리즘 자체와 별개로, 이 계산을 언제 시작할지와 계산이 도는 도중에 상황이 바뀌면 어떻게 할지도 정해야 했다.

계산 시점 정하기

처음에는 별도의 POST 엔드포인트로 계산을 수동 트리거했지만, 사용자가 "계산하기"를 눌러야 하는 흐름은 어색했다. 그래서 참여자가 위치를 제출하면 자동으로 계산이 돌도록 바꿨다. 트랜잭션 커밋 이후에 이벤트를 받아 처리하도록 구현했다.

@TransactionalEventListener(phase = TransactionPhase.AFTER_COMMIT)
void onLocationSubmitted(LocationAvailabilitySubmittedEvent e) { ... }

커밋 이후로 미룬 이유는, 계산이 참여자의 위치 데이터를 다시 읽기 때문이다. 커밋 전에 계산을 시작하면 아직 반영되지 않은 데이터를 보게 된다.

문제는 제출이 몰릴 때다. 다섯 명이 링크를 받고 비슷한 시점에 위치를 입력하면 계산이 다섯 번 돌고, 앞선 네 번의 결과는 어차피 마지막 계산에 덮이게 된다. 그래서 3초 debounce를 넣어, 새 제출이 들어오면 예약된 계산을 취소하고 다시 예약하도록 했다.

pendingLocationTasks.compute(
        e.meetingCode(),
        (key, existing) -> {
            if (existing != null && !existing.isDone()) {
                existing.cancel(false);
                log.debug("Location calculation debounced: meeting={}", key);
            }
            return locationCandidateScheduler.schedule(
                    () -> {
                        pendingLocationTasks.remove(key);
                        placeCandidateService.calculatePlaceCandidates(key);
                    },
                    Instant.now().plusSeconds(DEBOUNCE_DELAY_SECONDS));
        });

이 debounce는 의도한 대로 잘 동작했지만, 인스턴스가 하나일 때까지만 그랬다. 카나리 배포로 인스턴스가 둘이 되면서 이 인메모리 상태가 문제를 일으켰는데, 해당 이야기는 이전 글에 적어두었다.

계산 도중 참여자가 나갈 때

경로 조회를 병렬화했어도 계산에는 여전히 수 초가 걸린다. 그 사이에 참여자가 모임을 나갈 수 있다.

그러면 계산은 이미 사라진 참여자의 좌표를 포함한 채 끝나고, 결과를 저장하는 시점에 존재하지 않는 참여자를 참조하는 FK 예외가 발생한다.

계산 전체를 트랜잭션으로 감싸 참여자 이탈을 막는 방법도 생각해봤지만, 수 초 동안 외부 호출을 하는 작업을 위해 다른 사용자의 동작을 붙잡아두는 건 과하다고 판단했다. 대신 계산이 끝나고 DB에 반영하기 직전에, 시작 시점의 참여자 집합과 현재 참여자 집합을 비교해서 다르면 결과를 버리도록 했다.

if (!currentIds.equals(originalIds)) {
    log.warn("Participants changed during calculation for meeting {}, aborting", code);
    return;
}

버려도 안전한 이유는, 참여자 이탈 자체가 재계산을 트리거하는 이벤트이기 때문이다. 어차피 바뀐 구성으로 다시 계산된다. 이미 무효가 된 결과를 억지로 저장하는 것보다 깔끔하게 버리는 편이 낫다고 생각했다.

남은 것들

기준 시각 — 평일 정오 기준이라 새벽이나 주말 모임에는 실제와 다른 경로가 나올 수 있다. 추천 시간이 확정된 뒤 그 시각으로 재계산하는 흐름이 필요하다.

POI 카테고리 — 카페로 고정되어 있어, 식사 모임인지 스터디인지에 따라 원하는 장소가 달라도 선택할 방법이 없다.

후보 탐색 범위 — 기하중심 주변으로 한정된다. 방사형으로 배치한 후보들 사이에 더 나은 장소가 있어도 격자에 걸리지 않으면 발견되지 않는다.

마무리

돌아보면 이 기능에서 가장 오래 고민한 건 수식이 아니라 무엇을 공평하다고 부를 것인가였다. 편차를 가장 무겁게 두면 모두가 똑같이 불편한 장소가 1위로 올라온다. 계산은 정확하지만 그건 우리가 원하던 공평함이 아니었다.

결국 가중치 세 개를 조정하는 일은 이 서비스가 무엇을 좋다고 볼 것인지를 정하는 일이었다. 알고리즘은 정해준 기준에 따라 가장 나은 후보를 찾아줄 뿐, 그 기준이 옳은지는 답해주지 않는다. 추천처럼 정답이 없는 기능에서는 그 기준을 얼마나 분명하게 정해두었는지가 결과의 품질을 가른다고 생각한다.

이름

내용

비밀번호