**🔗 참고 문제** → [<https://www.acmicpc.net/problem/7453>](<https://www.acmicpc.net/problem/7453>)      // 클릭 시 이동

• Meet-in-the-middle (MITM)
• 큰 탐색을 반으로 쪼개서 각각을 미리 계산해두고, 두 결과를 합쳐 정답을 만드는 기법
• 일반적으로 ‘합’ 형태에서 다음과 같이 나타남
  • A + B + C + D = K → (A+B) + (C+D) = K
  • K중 루프 → (K/2) 중 루프 로 낮추는 발상

🚮 선입견을 버리자

• K개 항의 합을 그대로 K중 루프로 돌리면 시간 초과 발생 확률 높음
  • N이 수천이면 3중 루프부터 위험
• 이를 해결하기 위해, “2개씩 묶어서 합 배열 만들기” 방식 사용
• 이후 투포인터를 통해 문제 풀이 진행

💭 어떻게 떠올릴까

1. 트리거
   • 항이 4개: A[a] + B[b] + C[c] + D[d] = 0
   • N이 4000: 4중 루프 불가능
   • 존재 여부가 아니라 개수 카운팅
2. 한 줄로 변형
   • A + B + C + D = 0 == (A + B) = -(C + D)
   • 이렇게 하면, AB 합들과 CD 합들 사이에서 ‘서로 보수인 값이 몇 개인가’ 로 관점 변경

✏️ 시간 복잡도 (4SUM 기준)

M = N² 로 설정

• 시간복잡도: O(M × log M)
  • 정렬: O(M × log M) ← 지배적
  • 합 배열 생성: O(M)

📒 kSUM 풀이 방법

• kSUM 일반화 아이디어
  • x1 + x2 + ... + xk = K 일 때, 반으로 분할
  • 왼쪽 그룹 크기 p , 오른쪽 크기 k - p
  • sumLeft = K - sumRight 형태로 매칭