blackegg   2년 전

런타임오류가 계속되어 원인을 찾다보니 소스가 아래와 같이 남았습니다.

그런데
int[][] map = new int[V+10][V+10];

부분에서 런타임오류가 나네요.

배열에 작은 수를 넣으면 넘어가지만 문제의 V의 한계값인 20000 을 넣어도( int[20000][20000]) 도 런타임오류입니다.

아래 1차원배열은 에러나지 않습니다.

PriorityQueue 사용하지 않고 배열이용해서 풀고자 했는데..로직과는 상관없는데서 넘어가질 않네요.

제가 뭔가 다른 착각을 하고 있는 건지, 배열크기 한계가 있는건지 확인부탁드립니다.



chogahui05   2년 전

V가 2만이군요. V가 2만이면. 배열 map의 크기는

sizeof(int) * 2만 * 2만 = sizeof(int) * 4 * 10^8byte네요.

10^6 = 1Mbyte 이므로, 400 * sizeof(int) Mb만큼 메모리가 할당되겠네요. 

뻗어도 이상하지 않을 만큼 크군요.


V = 2만, E = 30만입니다.

인접 행렬로 표현하시면 4억입니다. 4억개의 정보 중에 단 30만개만 씁니다. 희소 행렬이지요.

차라리 ArrayList나 Vector 같은 걸로 관리하는 게 더 좋지 않을까 싶습니다.

물론, 이 둘은 grow rate 때문에 오버 헤드가 있긴 합니다만.


4억개의 int형 배열을 선언하는 것 보다는 오버헤드가 적겠지요.

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