kdhsong   9년 전

메모리를 잡아야하는데

20001 X 20001 이 안되잖아요

예제나 작은 숫자는 잘돌아가는데

메모리초과로 계속 에러가뜨는데 어떻게 잡나요 ?ㅠ

h0ngjun7   9년 전

C++ STL vector나 연결리스트로 정점 v에서 뻗어나가는 간선의 정보를 저장해야합니다.

또는 1~e번 간선을 자체적으로 정점 번호순으로 정렬해서 '정점 v에서 뻗어나가는 간선 집합은, 정렬된 간선 집합에서 L(v)~R(v)번까지이다'처럼 저장하는 방법도 있습니다.

h0ngjun7   9년 전

그리고 위의 문제는 힙(heap)과 같은 자료구조를 이용한 다익스트라 알고리즘을 사용하여야 제한 시간 내에 맞힐 수 있는 문제입니다. 참고하세요.

Hibbah   9년 전

우선, long long int (8byte)로 20000X20000 크기의 배열이면 약 3000MB라는 어마어마한 용량을 사용하게 됩니다.

문제에서 요구하는 메모리(128MB)제한을 훌쩍 넘어버리는 크기네요

그리고, 함수 DJ가 DiJkstra를 의미하는지는 모르겠지만..

다익스트라라는 알고리즘의 논리적인 과정과 정당성을 이해하는것이 첫번째이고,

두번째로, 어떻게 구현할지도 생각해보셔야 됩니다

일반적으로 기본연산(덧셈, 곱셈, 할당, 비교....)을 1억 번 수행하는데 1초 미만의 시간이 걸린다고 가정하고

알고리즘의 수행시간을 빅오표기법(Big-O notaion)으로 계산했을 때, 문제에서 요구하는 제한시간(1초)에 가능한지를 분석해보셔야 하는데,

논리적 과정이 동일한 알고리즘이라도 구현하는 방식에 따라 O(n^2)이 될수도 있고 O(nlogn)이 될 수 있으므로 구현 방법도 고민을 해보셔야됩니당

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