[Algorithm] Meet In The Middle

[Algorithm] 중간에서 만나기 (Meet In The Middle)

중간에서 만나기.
만일 브루트 포스를 써야할 때가 있는데, 데이터의 크기가 너무 클 경우 사용할 수 있다!

---

• 특정 조합의 개수를 찾는 등 브루트 포스 알고리즘을 써야하는 경우가 있다.
• 하지만, 원소의 개수가 너무 많아지면 시간 복잡도가 너무 커질 수 있다!
  • 크기 N의 경우 O($2^N$)만큼 걸리는데, N이 커짐에 따라 기하급수적으로 시간이 늘어난다.
  • N이 30만 돼도 $10^9$번의 연산이 필요하다.
  • 하지만, 이 방법을 쓰면 약 $10^6$번을 줄어든다.
• 이런 경우, 집합을 두 개로 나눠 모든 경우의 수를 구한 다음 이진 탐색을 이용해 조합을 찾을 수 있다.

---

시간 복잡도

• O($log(2^{N/2})2^{N/2}$) ≈ O($N2^{N/2}$)

---

과정

• 크기 N의 배열 arr이 있고, 배열의 원소를 더해 MAX값 이하가 되는 경우의 수를 구한다.
  • arr = {4, 1, 3, 2}이고, MAX = 4라고 하자.
• arr을 절반으로 나눠 만들 수 있는 모든 경우의 수를 arr_left, arr_right에 나눠 담는다.
  • 두 배열 모두 0번째 원소는 0이다!
  • arr_left = {0, 4, 1, 5}, arr_right = {0, 3, 2, 5}
• arr_right를 오름차순으로 정렬한다.
  • arr_left = {0, 4, 1, 5}, arr_right = {0, 2, 3, 5}
• val = MAX - arr_left[i], i = 0 to len(arr_left)와 arr_right의 원소값과 비교한다.
  • val이 음수면 넘어간다.
    • 혹은, 배열을 만드는 과정에서 거를 수도 있다.
  • arr_right[j] <= val, 0 <= j < len(arr_right)를 만족하는 가장 큰 j를 찾는다!
  • j는 이진 탐색을 이용해 찾는다.
• 모든 i에 대해 찾은 j + 1의 값을 모두 더한 것이 조건을 만족하는 모든 경우의 수가 된다!
  • i = 0, j = 2. case += 3
  • i = 1, j = 0. case += 1
  • i = 2, j = 2. case += 3
  • i = 3은 MAX를 넘어가므로 세지 않는다.
  • 모든 경우의 수는 7개가 된다.
    • 찾은 순서대로 { {0}, {2}, {3}, {4}, {1}, {1, 2}, {1, 3} }가 있다.