글 읽기 - 왜 이분 탐색을 쓰는 것이 unordered

mhkim4886 2년 전 1

코드 1은 11.992ms, 코드 2는 7.612ms가 나왔습니다.

코드 1의 경우는 unordered_map을 사용해서, O(n^2)에 a, b 배열에서의 합을 모두 저장한 후 O(n^2)에 c, d 배열의 합을 구해 -(c+d)의 갯수를 unordered_map에서 찾아서 합합니다.

코드 2의 경우는 vector를 사용해서, O(n^2)에 a, b 배열에서의 합을 모두 저장한 후 이것을 정렬한 후에, O(n^2logn)에 c, d 배열의 합을 구해서 -(c+d)의 갯수를 찾아서 합합니다.

시간복잡도 상으로는 코드 1이 당연히 빨라야 하는데 코드 2가 더 빨라서 질문을 올립니다.

unordered_map은 해시 테이블이라 O(1)일텐데 이 친구도 상수가 너무 커서 이러는 걸까요 :(

// CODE 1
int n;
lli ans;
unordered_map<int, int> m;

void s1(vector<int> &a, vector<int> &b) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            m[a[i] + b[j]]++;
        }
    }
}

void s2(vector<int> &c, vector<int> &d) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int cc = c[i], dd = d[j];
            if (m.find(-(cc + dd)) != m.end()) ans += m[-(cc + dd)];
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    scanf("%d", &n);
    vector<int> a(n), b(n), c(n), d(n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);
    }
    s1(a, b);
    s2(c, d);
    printf("%lld\n", ans);
}



// CODE 2
int n;
lli ans;
vector<int> sums;
void s1(vector<int> &a, vector<int> &b) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            sums.push_back(a[i] + b[j]);
        }
    }
}

void s2(vector<int> &c, vector<int> &d) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int cc = c[i], dd = d[j];
            auto [left, right] = equal_range(sums.begin(), sums.end(), -(cc + dd));
            ans += (right - left);
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    scanf("%d", &n);
    vector<int> a(n), b(n), c(n), d(n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);
    }
    s1(a, b);
    sort(sums.begin(), sums.end());
    s2(c, d);
    printf("%lld\n", ans);
}

Green55 2년 전 5

네. unordered_map은 꽤 상수가 큽니다

WeissBlume 2년 전 2

그래서 (딱히 실제 대회에서 쓸 일은 거의 없지만) gcc의 gp_hash_table 확장을 이용하면 실제로 해시 테이블을 이용한 해법이 훨씬 빠르게 동작합니다(코드, 참고한 코포 블로그).

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜 이분 탐색을 쓰는 것이 unordered_map보다 빠른가요?

mhkim4886 2년 전 1

Green55 2년 전 5

WeissBlume 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말