kkwandy   1년 전

아래는 제 제출코드 그대로 입니다.

다익스트라를 3번 써서 s -> g -> h -> e인 경우 / s ->h->g->e인 경우 + 기본 distance 구하기 위한 1번 해서, 각 테케마다 다익스트라 3번 하여 제출했더니 맞았습니다 가 뜨더군요
사실 무지성으로 구현한거라 시간 초과날 수도 있을거같다 생각했었습니다. 근데 생각보다 메모리랑 시간을 많이 안잡아먹네요??

1. 정해가 무엇인가요? 그리고 제 풀이가 시간이 생각보다 많이 걸리지 않는 이유가 무엇인가요?

2. 이건 별개 질문인데, 평소 시간복잡도 위주로 고려하여 풀다보니 예상 메모리 소모 계산이 시간복잡도 유추만큼 익숙하지가 않네요. 여러분들만의 메모리 예상 팁? 같은것이 있을까요?

감사합니다.

leeingyun96   1년 전

정해인지는 모르겠지만 다익스트라 1번으로 풀 수 있기는 합니다. 대략적으로 아래와 같고 저는 set를 쓴 뒤 마지막에 (g, h) in set을 했고 다른 분 풀이는 미리 (g, h) == (now, nxt)를 한 뒤 True, False 값이 다음으로 전이되도록 불리언 배열로 푼 분도 있네요. 시간 차이가 상수배 3배 정도는 차이나야 할 텐데 별 차이가 안 나는 건 신기하긴 하네요.

저도 메모리 초과는 별로 본 적, 신경쓴 적 없는 것 같습니다. 계수 정렬 딱 1문제만 생각나네요.

 

여담으로 그냥 다익스트라 여러 번 돌리는 것도 충분히 좋은 풀이 아닐까 싶긴 합니다. 차라리 중복되는 함수 부분을 하나로 처리하고 반복문으로 한 번에 돌린다든지요.

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