kisrin4319   2년 전

최단경로 문제를 우선순위큐를 사용한 다익스트라 알고리즘으로 해결하려고 하는데 자꾸 런타임 에러가 발생합니다.

다른 분들의 질문도 읽어보았고, 역시 마찬가지로 메모리 폭발이 문제가 아닐까 추측하고 있습니다.

제 생각은 대략 40~50 라인에서 메모리가 초과 나는것 같은데 도저히 해결 방법을 모르겠어서 도움을 부탁드립니다 

chogahui05   2년 전

16번째 줄이 메모리 초과 원인입니다.

2차원 배열을 선언하시지 마시고 Vector라던지, 희소 행렬을 선언해서 관리하는 게 어떨까요?

kisrin4319   2년 전

조언 감사합니다. 다른 분의 코드를 참조하여 ArrayList 로 구현해서 통과했습니다.(이것도 약간 어거지로 통과한 느낌)

하지만 Vector 라던가, 희소행렬로 구현하려고 하니 응용력이 부족한건지 잘 모르겠네요 ㅠ.ㅠ

chogahui05   2년 전

ArrayList나 Vector로 구현하는 게 쉽습니다. 코드도 간결하고요.

c++엔 대표적인 클래스 중 하나가 vector가 있는데요. 

java의 ArrayList랑 비슷하다고 보시면 됩니다.


어짜피, 다익스트라에 들어가는 건 가중치 합에 대한 것이니까요.

c로 구현하지 않는 이상 굳이 어렵게 희소행렬까지 생각하실 필요는..


희소 행렬은 단순히 공간 아끼기 위해서

counting sort 방식 + a를 이용해서 구현한다고 보시면 됩니다.

kisrin4319   2년 전

쉬운 dfs,bfs 문제를 접하고 해결법을 알았을때 이젠 다 풀수 있겠구나 했는데 배우면 배울수록 더 많이 알고 깊이 공부해야되는 느낌이네요 

chogahui05   2년 전

자바에 있는 자료구조가 어떻게 구현되어 있는지만 공부하셔도

여기에 나온 알고리즘의 70% 이상을 공부하실 거 같네요. 오버일려나요..?


근데 사실 ArrayList를 안다면 동적 배열에 대해서 공부를 하신 거고..

Map을 공부하신다면 해싱도 공부하신 거고.. (간혹 가다 Map으로 풀리는 경우도 있습니다. 어려운 것 중에서는요.)

레드 블랙 트리도 공부하신 거고..


간혹 가다가 원형 큐 같은 걸 써야 하는 문제가 나오긴 하지만..

그래도 기본적인 자료구조는 java에 나온 것들만 잘 공부하셔도 무난하게 소화 가능하실 겁니다.

고급 알고리즘은 기초가 탄탄해야 소화 가능하신 거니..

chogahui05   2년 전

bfs, dfs 문제가 한없이 어려워 지면

이런 괴물 문제가 됩니다.


https://www.acmicpc.net/proble...

이 문제는 머릿속이 계속 교환되는 느낌을 받으실 겁니다.

이런 기초 알고리즘도 어려워 지면 넘넘 어려워 지는 지라..

kisrin4319   2년 전

혹시 괜찮으시다면 2589번의 제 질문도 한번 봐주실수 있을까요?

https://www.acmicpc.net/board/...

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