글 읽기 - 런타임 오류 문의

blackegg 6년 전 0

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

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

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

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

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

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

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

import java.io.FileInputStream; 
import java.io.FileNotFoundException; 
import java.util.Scanner;

public class Main {  

      public static void main(String[] args) throws FileNotFoundException {

          //System.setIn(new FileInputStream("1753.txt"));   
          Scanner sc = new Scanner(System.in);             
          int V = sc.nextInt();   
          int E = sc.nextInt();   
          int K = sc.nextInt();       

          int[][] map = new int[V+10][V+10];    
          int[] d = new int[V+1];
          int[] chk= new int[V+1];
      }  

}

chogahui05 6년 전 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형 배열을 선언하는 것 보다는 오버헤드가 적겠지요.

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

문제

문제

출처

ICPC

런타임 오류 문의

blackegg 6년 전 0

chogahui05 6년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말