aliceshard   2년 전

일단 정답은 맞췄습니다만... 수행시간이 6000ms 전후로 나옵니다.


 다른 분들과 로직에서 큰 차이는 없어 보이는데 어디서 시간 소모가 크게 되는지 모르겠습니다.

zenith82114   2년 전

실험해 보고 대답을 드리는 건 아닙니다만

테스트 케이스 크기에 관계없이 무조건 101*10001 초기화를 도는 게 bottleneck인 것 같고

(node, 요금, 거리) 정보 단위가 동적 메모리(vector)인 점,

compare가 비교할 vector들을 copy해서 가져가는 점 등도 소소하게 시간을 먹을 것 같네요.

aliceshard   2년 전

preview

최적화전: 6848ms

1) compare 비교를 참조로 하도록 변경: 6308ms

2) compare 참조 + 테스트 크기에 맞춰 초기화를 하도록 변경: 6316ms

(node, 요금, 거리)를 벡터가 아닌 다른 형태로 쓰는 것도 시도해보고 싶은데, 혹시 괜찮은 방법이 있을까요?

graph는 동적 자료형을 유지해야 하는 이상 크기가 고정된 (node, 요금, 거리)만이라도 일반 배열로 써야할 것 같은데, 벡터 내부에 array를 저장하는건 어려워보이네요...

(c++ - Correct way to work with vector of arrays - Stack Overflow) - 

You cannot store arrays in a vector or any other container. The type of the elements to be stored in a container (called the container's value type) must be both copy constructible and assignable. Arrays are neither.

zenith82114   2년 전

이 문제의 (node, 요금, 거리) 같은 단위는 vector보다 구조체로 다루는 게 크게 유리합니다.

동적 메모리를 관리하는 데 들던 시간이 아껴지는 데다

언제나 int 3개로 크기가 고정돼 있기 때문에 메모리 측면에서도 경제적입니다.

(word alignment로 인해 실제로는 16바이트씩 들겠지만 그래도 여전히)

vector는 크기가 변할 때마다 매번 해제+재할당을 반복하는 걸 피하기 위해

항상 실제 차 있는 size보다 좀 더 큰 메모리(capacity)를 내부적으로 잡고 있기 때문입니다.

만일 vector이 가능하더라도 저는 코드의 가독성을 위해 구조체를 쓸 것 같습니다.

info[0], info[1], info[2]보다 struct Info { int idx, cost, dist; }; 가 그 의도가 훨씬 잘 드러나니까요.

zenith82114   2년 전

만일 vector이 가능하더라도 = 만일 vector<int[3]>이 가능하더라도
입니다.

aliceshard   2년 전

preview

말씀하신대로 struct로 새롭게 정의하니 절반 가량이 줄어드네요.

오랫동안 파이썬만 하다가 다시 C++를 잡으니 너무 편하게 접근했던 것 같습니다.

도와주셔서 감사드립니다!

게시글을 보실 다른 분들을 위해 변경된 코드를 첨부합니다.

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