1325번 - 효율적인 해킹
메모리는 똑같은 양과 똑같은 접근 횟수라도 어떤 순서로 접근하느냐에 따라 천차만별의 속도 차이가 납니다. 기본적으로 최근에 접근했던 주소와 가까운 주소를 접근하는 것은 빠르고, 반대의 경우는 느립니다. 배열의 경우에는 인덱스 오름차순으로 접근할 때가 가장 빠르고, 멀리 떨어진 인덱스 사이를 왕복하거나 무작위로 접근하면 속도가 느립니다.
올려주신 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년 전
c++보다 c99를 주로 사용하는데 아래 코드의 시간 차이가 왜 많이날까요 c99로는 시간 초과가 나오고 c++로는 통과가 됩니다. 뭐가 문제일까요..?