SORTGAME 질문입니다~! Signin 안녕하세요~ 문제 SORTGAME 을 풀다가, 질문이 있어서 올리게 되었습니다. JMBOOK의 모범 코드를 가지고 테스트를 해 봤는데요, 저의 컴퓨터에서는 실행시간이 8초를 훨씬 웃도는데 Online Judge에서는 이렇게 간단히 500ms만에 답이 나오는게 신기해서 여쭈어보게 되었습니다. 저의 노트북 성능이 안 좋은 것인가요~? (CPU는 2117u, 램은 4GB 입니다.ㅠㅠ) 아니면 뭔가 운영체제나 컴파일러에 따른 속도 차이가 나는 것인가요~? 소스코드는 다음과 같습니다.(책과 90% 똑같습니다.) #include <iostream> #include <vector> #include <map> #include <queue> #include <algorithm> using namespace std; map<vector<int>, int> dist; void printVector(vector<int> &v) { int i=0; for(i=0; i<v.size(); i++) cout << v[i] << " "; cout << endl; } void precalc(int n) { vector<int> start(n); for(int i=0; i<n; i++) start[i] = i; queue< vector<int> > q; q.push(start); dist[start] = 0; while(!q.empty()) { vector<int> here = q.front(); q.pop(); int cost = dist[here]; for(int i = 0; i < n; i++) { for(int j = i+2; j <= n; j++) { reverse(here.begin() + i, here.begin() + j); if(dist.count(here) == 0) { dist[here] = cost + 1; q.push(here); //cout << "성공!" << endl; } //printVector(here); reverse(here.begin() + i, here.begin() + j); } } } } int solve(const vector<int>& perm) { int n = perm.size(); //vector<int> fixed(n, 0); vector<int> fixed(n); for(int i = 0; i < n; i++) { int smaller = 0; for(int j = 0; j < n; j++) if(perm[j] < perm[i]) smaller++; fixed[i] = smaller; } return dist[fixed]; } int main() { for(int i=1; i<=8; i++) precalc(i); int tc; cin >> tc; while(tc--) { int n; cin >> n; vector<int> in; for(int i=0; i<n; i++) { int temp; cin >> temp; in.push_back(temp); } // 결과 출력 cout << solve(in) << endl; } return 0; } 11년 전
9개의 댓글이 있습니다. Being 어떤 환경에서 빌드하셨는지는 모르겠으나 최적화 옵션에 따른 차이가 매우 큰데요, 범인은 map<vector<int>, int>일 확률이 매우 높습니다. 11년 전 link Being 제가 표준 라이브러리 구현체들의 컴파일 옵션에 따른 map<vector<int>, int>의 퍼포먼스에 대해 설명할 정도로 지식이 깊지는 않아서 전문가 찬스 쓰겠습니다. 아래 분이 대답해주실 거예요 :) 11년 전 link JongMan 어떤 컴파일러를 쓰고 계신가요? 11년 전 link Signin 개발 환경은 Visual Studio 2010를 사용하고 있습니다! 11년 전 link xesmaster 디버그모드라 그런거같네여 11년 전 link Being 아무튼 간에 map에 키를 컨테이너로 쓰는 건 빠르게 구현할 수는 있으나 내부에서 발생하는 각종 복사로 속도 측면에서 큰 페널티를 받게 됩니다. 궁금하시다면 키로 쓰이는 vector<int> 대신에 임의의 정수 값으로 대응시키는 함수를 작성해서 풀어 보시면 확실히 비교가 될 것 같네요. 11년 전 link Signin xesmaster // 디버그 모드라면 한 step씩 실행시키는 모드 말씀이신가요? Being // 좋은 댓글 감사합니다. map의 구조상 오래 걸리게 되어있군요. 11년 전 link kcm1700 Signin // Debug 빌드가 있고 Release 빌드가 있습니다. Debug 빌드는 standard container를 사용할 경우 많이 느리지만, Release로 빌드할 경우 속도가 정상적으로 나옵니다. 11년 전 link Signin kcm1700 // 그렇군요!! 빌드 옵션을 Release모드로 바꿨더니 속도가 정말 빨라졌네요... Debug 빌드라는 것을 처음 들었는데, 좋은 걸 배워갑니다^_^!! 11년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
Signin
안녕하세요~
문제 SORTGAME 을 풀다가,
질문이 있어서 올리게 되었습니다.
JMBOOK의 모범 코드를 가지고 테스트를 해 봤는데요,
저의 컴퓨터에서는 실행시간이 8초를 훨씬 웃도는데
Online Judge에서는 이렇게 간단히 500ms만에 답이 나오는게
신기해서 여쭈어보게 되었습니다.
저의 노트북 성능이 안 좋은 것인가요~?
(CPU는 2117u, 램은 4GB 입니다.ㅠㅠ)아니면 뭔가 운영체제나 컴파일러에 따른 속도 차이가 나는 것인가요~?
소스코드는 다음과 같습니다.(책과 90% 똑같습니다.)
11년 전