중간 만남
Meet-in-the-middle - 최적화 방법 솔루션은 원래 문제를 두 부분으로 나누고 각각을 독립적으로 해결한 다음 두 부분의 솔루션을 결합하여 원래 문제에 대한 솔루션을 얻는 것으로 구성됩니다.
따라서 두 가지 조건이 충족되면
meet-in-the-middle을 사용하는 것이 좋습니다.
1) 문제의 절반을 해결하는 데 필요한 시간은 전체 문제를 해결하는 데 걸리는 시간보다 점근적으로 적습니다.
2) 절반의 문제를 풀면 원래의 전체 문제에 대한 해결책을 얻을 수 있으며 동시에 전체 문제를 푸는 것보다 점근적으로 더 빠릅니다.
예시
정수
A,
B,
C 및
D의 네 가지 배열이 있다고 가정합니다. 이러한 숫자의 합이 0이 되도록 각 배열에서 정확히 하나의 숫자를 선택해야 합니다. 순진한 솔루션을 사용할 수 있습니다. 즉, 가능한 모든 옵션을 간단히 열거하는 것입니다. 이것은
O(n4)에서 작동합니다.
그러나
meet-in-the-middle을 사용할 수 있습니다.
a + b + c + d = 0은
(a + b) = -(c + d)와 같습니다.
작업을 두 부분으로 나누겠습니다. 즉, 전반부에서는 배열
A 및
B만 사용하고 후반부에서는
C 및 <코드 >D.
전반부에 가능한 모든 (a + b) 옵션을 반복하고 모든 값을 해시 테이블(unordered_map, HashMap 등). 이것은 O(n2)에서 작동합니다.
이제 우리는 후반부에서 가능한 모든 옵션 (c + d)에 대해 반복할 것입니다. 특정 옵션을 고려할 때 반대 기호의 현재 합과 연결된 해시 테이블에 값이 있는지 확인합니다(그런 다음 합이 0이 되는 두 개의 역수를 찾았습니다). 이 부분은 O(n2)에서도 작동합니다.
여기에는 별도의 "답변 병합" 단계가 없습니다. 하나에서, 우리는 각 절반을 해결하는 과정에서 이것을 했습니다. 대부분의 작업은 비슷한 상황을 겪게 됩니다.
우리는 meet-in-the-middle을 사용하여 O(n2)에서 해결책을 찾았습니다.
meet-in-the-middle은 실행 시간에 상당한 영향을 미치는 기하급수적 솔루션을 최적화할 때 가장 자주 사용된다는 점은 주목할 가치가 있습니다.