글 읽기 - [11650] C 언어. 메모리 초과 이유? ++ 시간초과 이유?

jhwan818 4년 전 0

문제는 맞았습니다만... 어째서인지 첫 번째 제출때 메모리 초과가 떳었습니다.

첫 번째 제출때에는 정수를 할당하는 배열을 calloc 함수를 통해 동적 할당 후 문제를 진행 했습니다. 그런데 제출하고 나서 보니 메모리 초과가 떳습니다.

그래서 설마 하는 심정으로 모든 배열을 전역 범위로 옮겨담아 다시 진행했더니 바로 맞았습니다! 라고 나오네요.

어째서 메모리 초과가 뜬거죠?

아래 문제의 코드를 첨부해두겠습니다.

++++++++++++++++++++++

어.. 살펴보다가 free 함수로 배열 해제를 안시켜서 혹시나 하고 넣어보니 이번엔 시간초과가 뜨네요? 시간초과는 왜뜬거죠? 어우야

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef struct Location {
	int x;
	int y;
}loc;

int n;

void merge(loc *v, int s, int e, int m) {
	int i = s, j = m + 1;
    //배열 할당.
	loc* ret = (loc*)calloc(sizeof(loc), n);
	if (ret == NULL) { exit(-1); }
	int count = 0;
	while (i <= m && j <= e) {
		if (v[i].x < v[j].x) { ret[count++] = v[i++]; }
		else if (v[j].x < v[i].x) { ret[count++] = v[j++]; }
		else if (v[i].x == v[j].x) {
			if (v[i].y < v[j].y) { ret[count++] = v[i++]; }
			else { ret[count++] = v[j++]; }
		}
	}
	while (i <= m) { ret[count++] = v[i++]; }
	while (j <= e) { ret[count++] = v[j++]; }
	for (int i = s; i <= e; i++) { v[i] = ret[i - s]; }
}

void mergesort(loc *v, int s, int e) {
	if (s < e) {
		int m = (s + e) / 2;
		mergesort(v, s, m);
		mergesort(v, m + 1, e);
		merge(v, s, e, m);
	}
}

int main() {
	scanf("%d", &n);
    //배열 할당.
	loc* v = (loc*)calloc(sizeof(loc), n);
	if (v == NULL) { return -1; }
	for (int i = 0; i < n; i++) { scanf("%d %d", &v[i].x, &v[i].y); }
	mergesort(v, 0, n - 1);
	for (int i = 0; i < n; i++) { printf("%d %d\n", v[i].x, v[i].y); }
	return 0;
}

seico75 4년 전 0

calloc 은 할당과 함께 초기화도 하는데 여기서는 초기화가 필요가 없으니 malloc 를 사용하시는 것이 시간상 도움이 됩니다.

jhwan818 4년 전 0

malloc 함수를 쓰니깐 맞았습니다 가 뜨네요. 초기화 시키는데 시간이 좀 많이 걸리나보네요. 감사합니다.

gkswns3708 4년 전 0

제대로 된 해결책이 제시되지 않아 코드를 보면서 학습에 있는 사람입니다...

혹시 모든 배열을 전역으로 옮겨 담았다는 뜻이 어떤 뜻인가요..?

jhwan818 4년 전 0

단순히 함수 내에 선언했던 배열을 함수 외부에다가 선언했다는 말이에요. (함수 내 --> 지역변수, 함수 외부 --> 전역변수)

기본적으로 전역변수는 데이터 영역에, 지역변수는 스택영역에 할당하게 되는데 데이터 영역이 크기가 더 커서 배열 크기를 더 크게 할당할 수 있습니다.

제가 겪은 문제는 우선 malloc 함수를 사용할 때 힙 영역에다가 배열을 할당하게 되는데 사용이 끝나면 해제를 해줘야하는 것을 깜빡하고 안해줘서 힙 영역이 꽉 차버린 겁니다.

그래서 문제를 일으켰고요. 기본적으로 힙 영역이 스택영역보다 크기가 큽니다.

gkswns3708 4년 전 0

혹시 질문 하나만 더... ㅠㅠ

어떤식으로 전역변수에 배열을 지정했는지... 제가 무지해서...

위의 함수 형태로 하면

ret과 v가 있을텐데

loc *ret [100000];

loc *v[100000];처럼 했다는 말인가요...?

밑에 현재 저의 코드 현황입니다....

그냥 처음의 코드에서 calloc함수 대신 malloc함수를 사용한 것 말고는 다른게 없습니다.

댓글 달아주시면 감사합니다!

#include <stdio.h>
#include <stdlib.h> 
int n;
typedef struct Location{
	int x;
	int y;
}loc;
//loc *arr[100000];
//loc *ret[100000];
void merge(loc *arr,int start,int end,int mid){
	int i = start, j = mid+1;
	loc *ret = (loc*)malloc(sizeof(loc)*n);//채워 넣을 빈 구조체 배열 
	if(ret == NULL) { exit(-1);}
	int count = 0;
	while(i<=mid && j <=end){
		if(arr[i].x < arr[j].x){ret[count++] = arr[i++];}
		else if (arr[i].x > arr[j].x){ret[count++] = arr[j++];}
		else if (arr[i].x == arr[j].x){
			if(arr[i].y < arr[j].y) {
				ret[count++] = arr[i++];
			}
			else {
				ret[count++] = arr[j++];
			}
		} 
	}
	while(i<=mid){ ret[count++] = arr[i++];	}
	while(j<=end){ ret[count++] = arr[j++]; }
	for(int i = start; i<=end;i++){ arr[i]= ret[i-start];}
}
void mergesort(loc *arr,int s, int e){
	if(s<e){
		int m = (s+e) /2;
		mergesort(arr,s,m);
		mergesort(arr,m+1,e);
		merge(arr,s,e,m);
	}
}
int main(){
	scanf("%d",&n);
	loc *arr = (loc*)malloc(sizeof(loc)*n);
	if( arr == NULL){return -1;	}
	for(int i = 0 ; i < n; i++){
		scanf("%d %d",&arr[i].x,&arr[i].y);
	}	
	mergesort(arr,0,n-1);
	for(int i = 0 ; i < n; i++){
		printf("%d %d\n",arr[i].x,arr[i].y);
	}
	return 0;
}

jhwan818 4년 전 0

그냥 일반 배열 선언할 때 처럼 하시면 됩니다. 단지 위치만 조금 다를 뿐이에요.

그리고 동적 할당 하실 때에도 마찬가지로 일반 배열 선언하듯이 하면 됩니다.

아래에 두 예시 놔뒀어요.

전역변수를 사용할때에는 동적할당을 안하는 편이에요. 코드 꼬일때가 많아요.

그리고 가급적이면 전역변수는 사용하지 말라고 배웠어요. 지역변수랑 전역변수랑 변수 이름이 같으면 전역변수가 씹히거든요.

그런데 코드는 "일단은" 정상적으로 작동되니깐 코드가 꼬여요.

전역변수는 프로그램의 시작부터 끝까지 변하지 않는것들만 하는게 좋아요. 안그러면 귀찮아져요.

typedef struct Location {
	int x;
	int y;
}loc;

loc v[100000];
loc ret[100000];
int n;

----------------------------
    
#include <stdio.h>
#include <stdlib.h>

int* arr;

int main(void) {
	arr = (int*)malloc(sizeof(int) * 5);
	if (arr == NULL) { return -1; } //arr 배열 할당 실패했을 때. 프로그램 종료.
	for (int i = 0; i < 5; i++) {
		arr[i] = i;
		printf("%d\n", arr[i]);
	}
	return 0;
}

jhwan818 4년 전 0

추가로 loc*arr[100000]; 이라고 하셨는데 이거는 loc 타입의 변수의 "주소"를 저장하는 "배열"을 선언하신겁니다.

그러면 동적할당 할때에 arr[0] = (loc*)malloc(sizeof(loc) * 5) 이런식으로 하시면 됩니다. 그러면 일종의 2차원 배열이 만들어진거죠.

그리고 끝날때 free 함수 꼭 써주셔야해요. 안그러면 메모리 꼬입니다!

gkswns3708 4년 전 0

아 왜 포인터를 붙일 생각을 했을까요....

매번 알면서도 습관적으로 붙이고 있네요.....

귀중한 시간이셨을 텐데 감사합니다... 많은 공부가 되었습니다.

♥

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[11650] C 언어. 메모리 초과 이유? ++ 시간초과 이유?

jhwan818 4년 전 0

seico75 4년 전 0

jhwan818 4년 전 0

gkswns3708 4년 전 0

jhwan818 4년 전 0

gkswns3708 4년 전 0

jhwan818 4년 전 0

jhwan818 4년 전 0

gkswns3708 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말