ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 1931
    알고리즘/acmicpc 2015. 10. 14. 20:40

    mergesort를 직접 구현해서 풀어보려고했는데 stack overflow문제가 계속 났었다.


    나는 무한루프 때문인가 생각했는데 알고보니 함수 내에 지역변수를 너무 크게 잡은 메모리 초과가 원인이었다.


    recursion 할 때 stack 메모리에 어떻게 쌓이는지 다시 한 번 복습하는 기분이었다.


    해결방법은

    지역변수를 크게 안잡고 전역 변수로 두면 된다. 어차피 한 번의 recursive한 함수가 한 번만 접근하니까. 여기서 여러개의 thread돌리는 것이 아니기 때문에 공유 문제는 걱정 안해도 된다.


     
    #include<cstdio>
    
    using namespace std;
    struct course{
    	int start, end;
    };
    
    course c[100005];
    course tmp[100005];
    
    int mySort(int start, int end){
    	if(start==end)
    		return 0;
    
    	int mid = (start+end)/2;
    
    	mySort(start, mid);
    	mySort(mid+1, end);
    
    	int piv_a=start, piv_b=mid+1;
    
    	int cur=0;
    	while(1){
    		if(piv_a==mid+1 && piv_b == end+1)
    			break;
    		else if(piv_a==mid+1)
    			tmp[cur++]=c[piv_b++];
    		else if(piv_b==end+1)
    			tmp[cur++]=c[piv_a++];
    		else{
    			if(c[piv_a].end < c[piv_b].end)
    				tmp[cur++] = c[piv_a++];
    			else if(c[piv_a].end > c[piv_b].end) 
    				tmp[cur++] = c[piv_b++];
    			else{
    				if(c[piv_a].start < c[piv_b].start)
    					tmp[cur++] = c[piv_a++];
    				else
    					tmp[cur++] = c[piv_b++];
    			}
    		}
    	}
    
    	for(int i=0; i<cur; i++)
    		c[start+i]=tmp[i];
    	
    	return 0;
    }
    
    
    int main(){
    
    	int n;
    	scanf("%d", &n);
    
    	for(int i=0; i<n; i++)
    		scanf("%d %d", &c[i].start, &c[i].end);
    
    	mySort(0, n-1);
    
    	int cur_end = c[0].end;
    	int res=1;
    
    	for(int piv=1; piv<n; piv++){
    		if(c[piv].start >= cur_end){
    			res++;
    			cur_end = c[piv].end;
    		}
    	}
    
    	printf("%d\n", res);
    
    	return 0;
    }
    

    '알고리즘 > acmicpc' 카테고리의 다른 글

    1946  (0) 2015.10.16
    2590  (0) 2015.10.15
    1931  (0) 2015.10.14
    11000  (0) 2015.10.11
    2405  (0) 2015.10.09
    2437  (0) 2015.10.09

    댓글 0

Designed by Tistory.