글 읽기 - vector와 pair 사용에 따른 처리 시간 차이

minkyu4626 2년 전 0

일단 문제는 성공하였습니다.

처음에는 사람들의 입사 성적 정보를 받아 저장하는 컨테이너를 vector<vector<int>> v(MAX, vector<int>(2))로

지정하여 사용하였습니다. 이 경우에는 채점 결과가 시간초과였습니다.

동일한 코드에서 컨테이너만 vector<pair<int,int>> v(MAX)를 사용하니 시간초과 문제 없이 정답으로 채점되었습니다.

두 자료구조의 구현의 차이에서 오는 접근 시간의 차이 때문에 이런 결과가 도출된 것인지,

아니면 다른 이유 때문에 이런 결과를 얻게 되는 것인지 궁금합니다.

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

#define MAX 100000

using namespace std;

int tc;
int n;
vector<pair<int,int>> v(MAX);

int compare(pair<int,int> p1, pair<int,int> p2) {
    if (p1.first < p2.first)
        return 1;
    else
        return 0;
}

int main() {
    cin >> tc;
    for (int i = 0; i < tc; i++) {
        int solution = 0;
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> v[i].first >> v[i].second;
        }

        sort(v.begin(), v.begin()+n, compare);
        
        int temp = v[0].second;
        for (int i = 0; i < n; i++) {
            if (temp >= v[i].second) {
                solution++;
                temp = v[i].second;
            }
        }
        cout << solution << "\n";
    }
    return 0;
}

vector는 pair보다는 훨씬 무거운 객체입니다. 내부 구조를 보더라도 pair는 그냥 두 개의 변수가 붙어있는 것에 불과하다면, vector는 내부적으로 포인터와 벡터의 크기를 가지고 있고 벡터 생성 시에 동적 할당으로 메모리를 할당받는 구조입니다. 할당받는 메모리 양도 많을 뿐만 아니라, 접근할 때마다 포인터를 사용하기 때문에 지역성 등의 효율성에서 큰 차이가 발생합니다.

이 비효율성을 극대화시키고 있는 곳은 compare 함수입니다. 인자를 전부 vector형 그대로 받아오고 있기 때문에, 함수가 호출될 때마다 새로운 벡터가 만들어지고, 새로 공간이 할당되고, 원소들이 전부 복사되어 들어간 뒤, 함수가 끝나면 이 메모리가 해제되는 작업이 계속 반복됩니다. sort는 O(nlogn)번 비교를 하므로 메모리 할당 / 해제와 같은 무거운 연산이 O(nlogn)번이나 일어나고 있는 것입니다. 인자들을 &를 붙여 참조형으로만 만들어줘도 비약적인 속도 향상이 생깁니다.

minkyu4626 2년 전 0

전공 수업시간에 배웠던 기초적인 내용인데 깜박했네요!! 다시 기억나게 해주셔서 감사합니다!!

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

문제

문제

출처

ICPC

vector와 pair 사용에 따른 처리 시간 차이

minkyu4626 2년 전 0

djm03178 2년 전 2

minkyu4626 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말