didzl1231   1년 전

문제는 크루스칼 알고리즘을 사용해서 AC를 받았습니다.

처음엔 vector<tuple<int,int,int>>를 이용하였습니다. (각 시작점, 종점, 가중치) 

타 사이트에서 간선정보를 아래와 같이 2차원 배열로 주고 받길래 이와 다시  구현해서 AC를 받았습니다.

그런데 시간과 메모리가 차이가 꽤 많이나서, 사이즈를 출력하는 코드도 작성해 봤습니다.

심지어 간선을 순회하는 반복문에서는 튜플이 4개의 변수를 사용하고(auto도 사용함), 이차원 벡터는 3개만 사용하고 있습니다.

이차원 벡터가 3개가 가득 차서 내부적으로 사이즈를 늘리려고 새로 변수를 선언하고 복사하는 과정에서 메모리와 시간을 많이 잡아먹는 것이라고 생각해도 괜찮을까요? 

아니라면 이런 차이가 왜 생기는지 알려주시면 감사하겠습니다.. (--)(__)

(2D벡터) 42529678

(튜플) 42529404

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