avoid 메모리 초과 런타임에러가 발생합니다 GilDong http://algospot.com/judge/problem/read/AVOID #include <stdio.h> #include <stdlib.h> #define SWAP(x,y,t) ((t)=(x),(x)=(y),(y)=(t)) int repeat=0; int spotAmount=0; int wayAmount=0; int destAmount=0; int ptFrom[4950]={}; int ptTo[4950]={}; int weight[4950]={}; int destPt[4950]={}; int temp=0; typedef struct stor { int sum; int step; int dir[4950]; }stor; typedef struct link //연결리스트 사용 { stor memoPt; struct link* next; }link; link* startLink=NULL; link* lastLink=NULL; int storAmount=0; int partition(int list[],int left,int right) //퀵정렬 { int pivot,temp; int low,high; low=left; high=right+1; pivot=list[left]; do{ do { low+=1; }while(low<=right&&list[low]<pivot); do { high-=1; }while(high>=left&&list[high]>pivot); if(low<high) { SWAP(list[low],list[high],temp); SWAP(ptTo[low],ptTo[high],temp); SWAP(weight[low],weight[high],temp); } }while(low<high); SWAP(list[left],list[high],temp); SWAP(ptTo[left],ptTo[high],temp); SWAP(weight[left],weight[high],temp); return high; } void quick_sort(int list[],int left,int right) //퀵정렬 { if(left<right) { int q=partition(list,left,right); quick_sort(list,left,q-1); quick_sort(list,q+1,right); } } void func(int curNum,int loopNum,long long sum,stor memo) //재귀함수 { if(curNum==ptTo[wayAmount-1]) { memo.dir[memo.step++]=curNum; memo.sum=sum; link* newLink=(link*)malloc(sizeof(link)); //메모리 할당하는 부분!! newLink->memoPt=memo; newLink->next=NULL; if(storAmount==0) { startLink=newLink; lastLink=newLink; } else { lastLink->next=newLink; lastLink=newLink; } storAmount++; return; } for(int i=loopNum+1;i<wayAmount;i++) { if(curNum==ptFrom[i]) { stor tempMemo=memo; tempMemo.dir[(tempMemo.step)++]=curNum; func(ptTo[i],i,sum+weight[i],tempMemo); continue; } else if(curNum<ptFrom[i]) break; } } int main() { long long allWay=0; long long findNum=0; scanf("%d",&repeat); while(repeat--) { startLink=NULL; lastLink=NULL; storAmount=0; spotAmount=wayAmount=destAmount=0; scanf("%d %d %d",&spotAmount,&wayAmount,&destAmount); for(int i=0;i<wayAmount;i++) { scanf("%d %d %d",&ptFrom[i],&ptTo[i],&weight[i]); if(ptFrom[i]>ptTo[i]) { temp=ptTo[i]; ptTo[i]=ptFrom[i]; ptFrom[i]=temp; } } for(int i=0;i<destAmount;i++) scanf("%d",&destPt[i]); quick_sort(ptFrom,0,wayAmount-1); stor memo; memo.sum=0; memo.step=1; memo.dir[0]=1; for(int i=0;ptFrom[0]==ptFrom[i];i++) func(ptTo[i],i,weight[i],memo); link* findLink=startLink; if(storAmount>0) { int min=startLink->memoPt.sum; for(;findLink->next!=NULL;) { if(min>findLink->memoPt.sum) min=findLink->memoPt.sum; findLink=findLink->next; } for(int k=0;k<destAmount;k++) { allWay=0; findNum=0; findLink=startLink; link* nextLink=startLink; for(;findLink->next!=NULL;) { findLink=nextLink; if(min==findLink->memoPt.sum) { allWay++; for(int j=0;j<findLink->memoPt.step;j++) { if(findLink->memoPt.dir[j]==destPt[k]) { findNum++; break; } } } nextLink=findLink->next; } if(allWay==0||findNum==0) { printf("0/1\n"); continue; } long long finalFindNum=findNum; long long finalAllWay=allWay; for(long long i=2;i<=finalFindNum;i++) { if(finalFindNum%i==0&&finalAllWay%i==0) { finalFindNum/=i; finalAllWay/=i; } } findNum=finalFindNum; allWay=finalAllWay; printf("%lld/%lld\n",findNum,allWay); } link* nextLink=startLink; for(findLink=startLink;findLink!=NULL;) { nextLink=findLink->next; free(findLink); //메모리 제거하는부분 findLink=nextLink; } } else { printf("0/1\n"); continue; } } return 0; } 위에 주석달아놓은 부분에서 메모리 할당과 제거가 실행되고 누수는 발생하지 않게했습니다. 그런데 제출하면 메모리 초과했다고 오류를 보내주네요. 혹시 같은 경험하신분 조언부탁드려요 10년 전
2개의 댓글이 있습니다. Being 메모리 할당 해제 문제를 떠나, 그냥 메모리 사용량이 지나치게 많은 것 같습니다. stor 구조체가 int를 대략 5000개 가졌으므로 20kb를 차지하는데, link 구조체가 이것을 하나씩 가지면서 리스트로 보관하므로 대략 100MB 근처까지 갈 것 같네요. 10년 전 link GilDong 발코딩 ㅜㅜ 10년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
GilDong
http://algospot.com/judge/problem/read/AVOID
위에 주석달아놓은 부분에서 메모리 할당과 제거가 실행되고 누수는 발생하지 않게했습니다. 그런데 제출하면 메모리 초과했다고 오류를 보내주네요. 혹시 같은 경험하신분 조언부탁드려요
10년 전