his130   3년 전

제가 그래프를 푸는데

노드가 최대 만개 있다고 하면

vector<int> node[10000] 

이런식으로 선언을 하거든요 리스트로

근데 node[100000] 개 하면 오류가 뜨는데 이게 너무 커서 그런건가요?

혹시 어느정도가 맥시멈인지 아시나요..?


코딩 중 궁금해서 여쭤봅니다!


이럴때는 그냥 배열을 써야하는건가요??

djm03178   3년 전

메모리 할당은 크게 두 종류가 있습니다. 스택에 할당되는 것과, 힙에 할당되는 것입니다.

지역 변수의 경우 스택 영역에 할당되는데, 스택 영역은 일반적으로 8MB 정도에 제한이 걸려있습니다. 그래서 지역 변수로 너무 많은 메모리를 잡으려고 하면 이 크기를 초과하여 런타임 에러가 발생하게 됩니다.

반면에 전역변수나 동적할당의 경우 힙 영역에 할당되는데 이는 따로 메모리의 제한이 없습니다. 문제에서 주어진 크기만 초과하지 않으면 됩니다.

chogahui05   3년 전

node [10000] 한다고 오류가 뜨지는 않을텐데요..

혹시 node[10000][10000] 이런 식으로 선언하시지 않으셨나요?


보통 그래프를 다룰 때는

저 같은 경우 이렇게 씁니다.

vector <int> con[노드의 갯수]


희소행렬인 경우에 일일히 node[10000][10000] 하기에는 너무 큰 낭비입니다..


ps. 벡터하고 리스트하고는 다릅니다.

벡터 같은 경우, 중간에 삽입, 삭제가 일어나는 경우 최악의 경우 O(n)만치 걸립니다. --- (1)

http://www.cplusplus.com/refer...


하지만 i번째 원소에 접근하는 연산은 O(1)입니다. --- (2)

http://www.cplusplus.com/refer...


반면에 리스트는 바로 랜덤 접근이 되지 않아요. 순차적으로 접근해야 하죠..

his130   3년 전

댓글 너무 감사합니다! ㅠㅠ


아마 지역변수로 vector<int> 노드[100000] 으로 해서 그랬나봐요...

그걸 배열로 바꿔주니까 그냥 실행이되더라구요..

vecotr 로 했을 때는 뻗더니..

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