안녕하세요 한창 배워가는 개발자입니다.
위 문제는 '정답' 을 받기는 했지만, 성능상 이해가 되지 않는 부분이 있어 이렇게 문의를 드리게 되었습니다.
고수님들의 고견 부탁드립니다.
<궁금한점>
메모이제이션으로 최대 97% 정도 sqrt() 연산을 줄였음에도 수행시간은 미묘하게 더 걸리는 것 같습니다. 어떤 이유 때문일까요? (참고로, 제가 LOCAL 에서 테스트 했을때는 2배 가량 수행속도가 빨랐습니다.)
<비교가 필요한 함수>
getDistance1() : 그냥 코드
getDistance() : 메모이제이션 고려한 코드
/*1) A = {본부}2) A 집합의 각 원소와 가장 근접한 기지 탐색3) 탐색된 기지를 A에 추가4) 추가할때 A 집합에 속한 기지와 탐색된 기지의 거리를 구하여, 최대가 되는 값이 정답임5) 2,3 반복6) memoization 으로 거리 계산 중복 연산 제거*/#include <stdio.h>#include <math.h>#include <time.h>unsignedlongcalled;intTC;intposN;floatpos[100][3];intsetN;floatset[100][2];floatsetmemo[100][100];floatanswer;floatdist;floatjmin,kmin;intjidx,kidx;intinsertSet(intidx){set[setN][0]=pos[idx][0];set[setN][1]=pos[idx][1];pos[idx][2]=1;return++setN;}floatgetDistance1(floatx1,floaty1,floatx2,floaty2){called++;returnsqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}floatgetDistance(intj,intk){if(setmemo[j][k]!=0){returnsetmemo[j][k];}else{called++;setmemo[j][k]=sqrt((set[j][0]-pos[k][0])*(set[j][0]-pos[k][0])+(set[j][1]-pos[k][1])*(set[j][1]-pos[k][1]));}returnsetmemo[j][k];}intmain(void){clock_tstart=clock();freopen("input.txt","r",stdin);setbuf(stdout,NULL);scanf("%d",&TC);for(inti=0;i<TC;i++){// inputscanf("%d",&posN);for(intj=0;j<posN;j++){scanf("%f %f",&pos[j][0],&pos[j][1]);pos[j][2]=0;}// initanswer=0;setN=0;for(intj=0;j<posN;j++)for(intk=0;k<posN;k++)setmemo[j][k]=0;// codeinsertSet(0);// 본부를 집합에 포함시킨다.while(setN<posN){jmin=2000;kmin=2000;for(intj=0;j<setN;j++){for(intk=0;k<posN;k++){if(pos[k][2]==1)continue;// 이미 set 에 포함되었으면 continue//dist = getDistance1(set[j][0], set[j][1], pos[k][0], pos[k][1]);dist=getDistance(j,k);// memoizationif(kmin>dist){kmin=dist;kidx=k;}}if(jmin>kmin){jmin=kmin;jidx=kidx;}}insertSet(jidx);// 선택된 집합과 가장 거리가 가까운 기지를 포함시킨다.if(answer<jmin)answer=jmin;}// outputprintf("%.2f\n",answer);}printf("\ntime : %d %ld\n",clock()-start,called);return0;}
gloryof11
ARCTIC
안녕하세요 한창 배워가는 개발자입니다.
위 문제는 '정답' 을 받기는 했지만, 성능상 이해가 되지 않는 부분이 있어 이렇게 문의를 드리게 되었습니다.
고수님들의 고견 부탁드립니다.
<궁금한점>
메모이제이션으로 최대 97% 정도 sqrt() 연산을 줄였음에도 수행시간은 미묘하게 더 걸리는 것 같습니다. 어떤 이유 때문일까요? (참고로, 제가 LOCAL 에서 테스트 했을때는 2배 가량 수행속도가 빨랐습니다.)
<비교가 필요한 함수>
10년 전