$O(N^4)$과 같이 탐색해야 하는 사이즈가 너무 클 때, 문제의 조건에 따라 반복을 $O(N^2)$ 2개로 나눠서 중간 결과를 이용해 푸는 방법

ex) 배열에서 합이 W가 되는 원소 4개를 골라야할 때, 직관적으로 해결하면 $O(N^4)$이지만, 반복문을 반으로 나눠서 각각 중간 결과값을 이용해 푼다면 $O(N^2)$로 풀어낼 수 있다.

문제 및 풀이

Parcel (https://www.acmicpc.net/problem/16287)

  1. 처음에는 unordered_map<int, vector<Node>>을 써서 이 값을 Meet in the Middle로 탐색하려 했으나 시간초과. vector<Node>에는 sum에 해당하는 index i, j가 들어간다.

  2. 1.의 vector 탐색을 없앨 수 있을까 생각해보니, vector 내의 원소들 중 그나마 정답에 해당하는 건 미리 구한 합의 인덱스 i, j 중 i가 현재 탐색하고 있는 것보다도 뒤에 나와야만 했다. 그래서 합을 구할 때 맨 뒤의 원소만 기록하는 것으로 vector를 제거했다. → 816ms

  3. 2.에서 인덱스 비교는 Node의 j는 할 필요가 없다. 이미 Node의 i보다 j는 뒤이고, 현재 탐색할 때 Node의 i보다 먼저 탐색하면 되기 때문. → Node의 멤버 하나 제거하는 것으로 메모리 절약.

    1.에서 구현한 unordered_map이 느린 것 같아서 문제를 보니, 무게 합의 최대값이 대략 80만이었다. 그래서 cache 배열로 고쳤다. → 48ms

  4. 이제는 충분히 빠른데, 논리 과정에 개선을 더하는 것으로 메모리 효율을 더 얻을 수 있다(속도 개선을 예상했는데 속도는 크게 차이가 없었다)

    1. i, j를 기준으로 합을 구한다. 그 합이 cache에 있는지 보고 있으면 return한다.
    2. j를 찾는 for문이 끝나면, i, k 반복문으로 A[k] + A[i]를 구해 cache를 갱신한다.

    위 과정으로 a. 탐색하는 동시에 b. cache를 갱신하면, cache는 무조건 항상 새로 탐색하는 i보다 이전 범위의 값이므로 cache가 index를 저장할 필요도 없다. cache는 bool이면 된다.