gks10101   1년 전

c++보다 c99를 주로 사용하는데 아래 코드의 시간 차이가 왜 많이날까요 c99로는 시간 초과가 나오고 c++로는 통과가 됩니다. 뭐가 문제일까요..?

zenith82114   1년 전

C/C++는 컴파일되는 언어이기 때문에 코드의 극히 일부라도 생략하시면 안 됩니다. 가령 include가 빠져 있으며 check, cnt 등이 선언되어 있지 않습니다.

gks10101   1년 전

zenith82114 감사합니다.  

가령 include가 빠져 있으며 check, cnt 등이 선언되어 있지 않습니다.
실제 제출에서는 다 작성하였습니다. 코드길이때문에 글 올릴때는 겹치는부분은 생략하고 올렸습니다

zenith82114   1년 전

제출할 때가 문제가 아니라 답변을 못 합니다. 코드가 아무리 길어도 복붙해서 그대로 돌릴 수 있도록 전체를 보여주셔야 합니다. 그래야 다른 사람들이 실험을 하죠. 한 줄만 달라져도 컴파일러 최적화가 들어갔다 빠졌다 하는 게 C/C++이라서 부분적인 코드로는 할 수 있는 게 없습니다.

gks10101   1년 전

이거에요

zenith82114   1년 전

메모리는 똑같은 양과 똑같은 접근 횟수라도 어떤 순서로 접근하느냐에 따라 천차만별의 속도 차이가 납니다. 기본적으로 최근에 접근했던 주소와 가까운 주소를 접근하는 것은 빠르고, 반대의 경우는 느립니다. 배열의 경우에는 인덱스 오름차순으로 접근할 때가 가장 빠르고, 멀리 떨어진 인덱스 사이를 왕복하거나 무작위로 접근하면 속도가 느립니다.

올려주신 C++ 코드는 vector를 사용하여 인접 리스트를 만들기에 같은 정점에서 뻗어나오는 간선들이 연속한 주소에 배치됩니다. 반면 C 코드는 간선이 입력되는 순서대로 nodepool에 이어붙이기 때문에 위에서 말한 무작위 접근에 훨씬 가까운 양상이 됩니다. 제 테스트 결과 N=4,500, M=30,000 정도의 케이스에서 C++ 코드는 0.6초, C 코드는 1초를 소요합니다.

하지만 vector가 없는 C에서도 C++과 비슷한 성능의 인접 리스트를 만들 수 있습니다. 모든 정점들의 인접 vector를 하나로 이어붙인 것과 같은 큰 배열을 만들면 되는데, 일단 임시 배열에 간선 입력을 받으면서 정점별 간선 개수를 세고, 임시 배열을 다시 한 번 보면서 같은 정점에서 나오는 간선들을 연속하게 모아주면 됩니다. 이 방법을 구현한 제 코드는 여기서 보실 수 있습니다: https://www.acmicpc.net/source...

gks10101   1년 전

아.. 주소가 가까운게 훨씬 시간이 적게드는 군요.. 많이 배웠습니다.. 감사합니다!! 연결리스트는 벡터만 쓰는게 낫겠네요

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