헝가리안 기법 (Hungarian Method)
한 줄 정의: 비용행렬을 행·열 차감으로 변형해 할당문제의 최적 배정을 찾는 다항시간 알고리즘입니다.
쉽게 풀면
할당문제의 비용표에서 각 행과 각 열의 최솟값을 빼 주면, 표 안에 0이 여러 개 생깁니다. 서로 겹치지 않는 0들만으로 한 사람당 한 작업씩 배정할 수 있으면 그 배정이 최적입니다. 아직 안 되면 0을 덮는 선을 긋고 숫자를 조정하는 과정을 반복합니다.
왜 중요한가
손으로도 따라 할 수 있을 만큼 절차가 명확해 산업공학 수리계획법 수업에서 할당문제 해법으로 표준처럼 가르칩니다. 또 대규모 매칭·추적(예: 영상 속 객체 매칭) 알고리즘의 부품으로 널리 쓰여 다른 분야 논문에서도 자주 인용됩니다.
논문에서는 이렇게 쓰입니다
"프레임 간 객체 대응은 거리 기반 비용행렬에 헝가리안 기법을 적용하여 결정하였다."
두 프레임의 객체 쌍마다 거리를 비용으로 두고 최적 1대1 매칭을 구했다는 뜻입니다.
조금 더 깊게 보면
이 기법은 1955년 해럴드 쿤(Harold Kuhn)이 헝가리 수학자 쾨니그와 에게르바리의 결과를 바탕으로 정리해 이런 이름이 붙었고, 이후 먼크레스(James Munkres)가 다항시간임을 보였습니다. 현재 흔히 쓰이는 구현은 O(n³) 시간에 동작합니다. 이론적으로는 선형계획의 쌍대 변수를 조정해 가며 원문제와 쌍대문제의 조건을 함께 맞춰 가는 원-쌍대(primal-dual) 방법으로 해석됩니다.
주의할 점
헝가리안 기법은 할당문제를 푸는 '해법'이고, 할당문제는 '문제 자체'이므로 두 용어를 구분해 써야 합니다. 이익을 최대화하는 경우에는 비용으로 바꾸는 변환(예: 최댓값에서 빼기)을 먼저 해야 합니다.