Meet In The Middle

MITM 알고리즘주어진 문제를 절반으로 나누어서 부분 문제를 해결한 다음에 결과를 조합하여서 전체를 해결하는 알고리즘을 의미한다.예를 들어서 브루트 포스 알고리즘을 사용할 때 완전 탐색을 한다면 시간 복잡도가 O(2^N)이지만 Meet In The Middle을 활용하면 O(2^(N/2))로 줄일 수 있다!활용해 보기1. 문제를 절반으로 나눈다!.N/2인 두 개의 부분으로 나눈다.2. 각각의 부분을 알고리즘을 활용하여 해결한다.각각의 부분의 경우의 수를 구해주고 저장해 준다.3. 두 부분을 합쳐서 문제를 해결한다.이분탐색 혹은 정렬 등을 활용하여서 빠르게 조합을 찾아낸다.예시(배냥 문제)#include using ll = long long;using namespace std;// (무게, 가치) 리스트에..

2025.02.12