1. 그래프를 메모리에 표현하는 방법은 크게 두 가지가 있습니다. Adjacent matrix representation과 Adjacency list representation입니다. 전자는 각 (u, v) pair에 대해 인접여부를 저장하므로 말씀하신 것처럼 메모리 초과가 납니다. 하지만 후자는 각 (u, v) pair 중 실제로 존재하는 간선 수만큼만 저장하므로 O(V + E)의 메모리만 사용합니다. V <= 10,000, E <= 100,000이므로 메모리는 128 MB로 충분합니다.
2. 실질적으로 두 가지는 차이가 없습니다. 대신, 전자는 sort(v1, v1 + 10)과 같이 사용해야 하고 후자는 sort(v2.begin(), v2.end())와 같이 사용해야 합니다.
disdong123 3년 전
두가지 질문이 있습니다.
1. 메모리가 128mb이면 총 128 * 1000 * 1000 / 4 = 32,000,000 크기의 배열을 생성할 수 있다고 알고 있습니다.
이 문제를 보면 최대 1만개의 노드가 사용될 수 있는데 그러면 한 노드는 최대 9999개의 노드와 연결될 수 있다고 생각합니다.
그러면 단순히 생각해보면 최대 99,990,000 의 크기를 가진 배열이 필요한데, 이 경우에는 왜 메모리 초과가 발생하지 않는건가요??
2. vector<int> v1[10]과 vector<vector<int>> v2(10)의 정확한 차이가 궁금합니다.
sort(v2)는 정상적으로 동작하지만 sort(v1)는 작동하지 않는 이유가 v2는 vector 안에 vector를 넣은 2차원이고, v1는 vector안에 배열을 넣은 2차원이라 이해해야하는 건가요?