7453 c++ - 합이 0인 네 정수

이분탐색 문제입니다. 처음엔 해시로 접근했었습니다.

 

해시 적용

첫 풀이. -> 시간초과
map을 사용해서 AB의 합을 먼저 구하고, 이후 CD의 합으로 unordered_map으로 접근 O(1) -> N^2 + N^2의 시간으로 풀 수 있을 거라 판단 최악의 경우 4000^2 + 4000^2으로 32,000,000번의 연산으로 충분히 풀 수 있을 거라 생각했습니다.
시간초과의 이유 : 캐시히트의 시간까지 고려가 되어야함.

#include <iostream>
#include <unordered_map>
#include <vector>

#define FASTIO ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

int main() {
  FASTIO;

  int n;
  cin >> n;

  vector<int> A(n), B(n), C(n), D(n);
  for (int i = 0; i < n; ++i) {
    cin >> A[i] >> B[i] >> C[i] >> D[i];
  }

  unordered_map<int, int> sumAB;

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      sumAB[A[i] + B[j]]++;
    }
  }

  long long count = 0;
  for (int k = 0; k < n; ++k) {
    for (int l = 0; l < n; ++l) {
      int target = -(C[k] + D[l]);
      if (sumAB.find(target) != sumAB.end()) {
        count += sumAB[target];
      }
    }
  }

  cout << count;
  return 0;
}

 

이분탐색 적용

아래 AB합의 배열에서 이분탐색으로 CD합의 배열 차를 구하는 과정이 있는데, 두 배열 모두 정렬을 해주어야 시간을 절약할 수 있습니다. 

이 이유는 캐시 히트의 차이라고 생각되는데,  AB를 정렬할 경우 CD를 이분탐색할 때 연속적으로 이전에 봤던 위치들을 중심으로 다시 탐색하게 될 확률이 높아집니다. CD의 크기가 매우 크다는 것을 감안할 때 대부분의 위치를 매번 메모리로부터 불러오지 않고 캐시에서 찾아낼 수 있으므로 훨씬 시간이 절약됩니다. AB를 정렬하지 않으면 CD에서 찾는 위치가 매번 달라질 확률이 높아지므로 캐시 안에 들어가지 않는 수많은 페이지들을 지속적으로 갈아 끼워야 할 확률이 높아져 시간이 오래 걸리게 됩니다.

1. 캐시 효율성 저하

정렬된 데이터는 CPU 캐시에 잘 맞도록 데이터가 배열됩니다. 하지만 정렬되지 않은 데이터를 반복적으로 액세스 하면, 캐시 미스가 자주 발생하여 메모리 접근 비용이 증가합니다.

해결 방법:

AB 배열을 정렬하여 데이터 접근 패턴을 더 예측 가능하게 만듭니다. 정렬 자체는 연산 비용을 증가시키지만, 이후의 연산에서 캐시 히트율이 높아져 전체적으로 더 빠르게 작동할 수 있습니다.

2. 브랜치 예측 실패

AB 배열이 정렬되지 않은 상태에서는 탐색 대상(-numnumnum)이 sumCD에서 찾을 수 있는 값일지 여부가 불규칙적입니다. 이로 인해 CPU의 브랜치 예측이 실패하여 성능이 저하됩니다.

해결 방법:

정렬된 AB 배열을 사용하면 값의 분포가 더 균등해지고, 브랜치 예측이 더 정확하게 작동할 수 있습니다.

 

#include <iostream>
#include <vector>

#define FASTIO ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

int main() {
  FASTIO;

  int n;
  cin >> n;

  vector<int> A(n), B(n), C(n), D(n);
  for (int i = 0; i < n; ++i) {
    cin >> A[i] >> B[i] >> C[i] >> D[i];
  }

  vector<int> sumAB, sumCD;

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      sumAB.push_back(A[i] + B[j]);
      sumCD.push_back(A[i] + B[j]);
    }
  }

  sort(sumAB.begin(), sumAB.end());
  sort(sumCD.begin(), sumCD.end());

  long long count = 0;
  for (int num : sumAB) {
    int lower = lower_bound(sumCD.begin(), sumCD.end(), -num) - sumCD.begin();
    int upper = upper_bound(sumCD.begin(), sumCD.end(), -num) - sumCD.begin();
    count += (upper - lower);
  }

  cout << count;
  return 0;
}

 

정렬 AB값까지 최적화한 코드

#include <algorithm>
#include <iostream>
#include <vector>

#define FASTIO ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

int main() {
  FASTIO;

  int n;
  cin >> n;

  vector<int> A(n), B(n), C(n), D(n);
  for (int i = 0; i < n; ++i) {
    cin >> A[i] >> B[i] >> C[i] >> D[i];
  }

  vector<int> sumAB, sumCD;

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      sumAB.push_back(A[i] + B[j]);
      sumCD.push_back(C[i] + D[j]);
    }
  }

  sort(sumAB.begin(), sumAB.end());
  sort(sumCD.begin(), sumCD.end());

  long long count = 0;
  for (int i = 0; i < sumAB.size();) {
    int num = sumAB[i];
    int countAB = 0;

    while (i < sumAB.size() && sumAB[i] == num) {
      countAB++;
      i++;
    }

    int lower = lower_bound(sumCD.begin(), sumCD.end(), -num) - sumCD.begin();
    int upper = upper_bound(sumCD.begin(), sumCD.end(), -num) - sumCD.begin();

    count += static_cast<long long>(countAB) * (upper - lower);
  }

  cout << count << "\n";
  return 0;
}

 

첫번째 제출번호 86482837 - A 정렬을 하지 않은 코드
두번째 제출번호 86482828 - A 정렬 코드
세번째 제출번호 86482763 - A 정렬 후 최적화까지한 코드

 

시간초과가 발생하지 않는 이유: 정렬된 데이터의 장점

위 코드는 정렬과 이분 탐색을 통해 데이터 접근 패턴을 최적화하므로, 캐시 효율성이 높아지고 반복적인 연산에서 시간 손실이 발생하지 않습니다.

• 해시맵을 사용하는 방식과 비교:
  • 해시맵: O(1)의 평균 시간복잡도지만 캐시 미스 및 해시 충돌 발생.
  • 정렬 + 이분 탐색: O(logn) 복잡도지만 데이터 접근이 더 예측 가능.

 

---

 

결론

시간 초과의 원인은 단순히 시간복잡도 뿐만 아니라, 캐시 효율성, 해시 충돌, 반복적인 메모리 접근 등의 하드웨어 요인에서 발생할 가능성도 열어 둬야 합니다. 그러기 위해서는

1. 캐시 효율성을 고려한 데이터 구조를 사용해야 합니다.
2. unordered_map 대신 정렬된 벡터와 이분 탐색을 고려할 수 있습니다.
3. 더 나은 해싱 함수나 메모리 효율적인 자료 구조를 선택해야 합니다.