글 읽기 - C언어) 메모리 초과가 왜 나오는지 모르겠습니다.

0207free 2년 전 0

힙소트로 주어진 배열을 정렬한 후

정렬된 배열에서 중복된 수를 제거하고

이진탐색으로 크기 순서를 받아와 출력했습니다.

지금 이 코드는 '메모리 초과'가 뜨고 있는데

문제의 N의 최대값이 1,000,000이므로

int 배열 3개를 동적할당 시켰다고 하더라도

4 x 1,000,000 x 3 = 12MB니까

512MB인 메모리 조건보단 훨씬 작은것 아닌가요?

메모리 초과가 왜 나는지 알려주시면 정말 감사하겠습니다.

#include<stdio.h>
#include<stdlib.h>
#pragma warning(disable : 4996)

void HeapSort(int*, int);
void BuildHeap(int*, int);
void Heapify(int*, int, int);
void Swap(int*, int*);
int BinarySearch(int*, int, int, int);

int main() {
	int n;
	scanf("%d", &n);

	int* arr = (int*)malloc(sizeof(int) * n); //기본 배열
	int* arr2 = (int*)malloc(sizeof(int) * n); //힙소트로 정렬 할 배열
	int* arr3 = (int*)malloc(sizeof(int) * n); //중복을 제거한 배열

	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
		arr2[i] = arr[i];
	} // 기본 배열을 복사

	HeapSort(arr2, n - 1);

	int j = 0;
	for (int i = 0; i < n; i++) {
		if (i < n - 1 && arr2[i] == arr2[i + 1])
			continue;
		arr3[j++] = arr2[i];
	} // 정렬된 배열에서 중복을 제거

	for (int i = 0; i < n; i++) {
		printf("%d ", BinarySearch(arr3, 0, j - 1, arr[i]));
	} // 이진 탐색으로 크기 순서 파악 후 출력
}

void HeapSort(int* arr, int end) {

	BuildHeap(arr, end);

	for (int i = end - 1; i >= 0; i--) {
		Swap(&arr[0], &arr[i + 1]);
		Heapify(arr, i, 0);
	}
}

void BuildHeap(int* arr, int end) {
	
	for (int i = (end - 1) / 2; i >= 0; i--)
		Heapify(arr, end, i);
}

void Heapify(int* arr, int n, int idx) {
	int left = idx * 2 + 1, right = idx * 2 + 2, maxidx = idx;

	if (left <= n && arr[left] > arr[maxidx])
		maxidx = left;
	if (right <=n && arr[right] > arr[maxidx])
		maxidx = right;
	if (maxidx != idx) {
		Swap(&arr[maxidx], &arr[idx]);
		Heapify(arr, n, maxidx);
	}
}

void Swap(int* a, int* b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int BinarySearch(int* arr, int start, int end, int obj) {
	int idx = (start + end) / 2;

	if (obj > arr[idx])
		start = idx + 1;
	else if (obj == arr[idx])
		return idx;
	else 
		end = idx - 1;
	BinarySearch(arr, start, end, obj);

}

rhdqor213 2년 전 1

C99로 그대로 제출하니까 맞았습니다를 받습니다.

0207free 2년 전 1

일단 자체 해결에 성공했습니다.

동적할당의 크기 때문에 메모리 초과가 나는건 아니라는 판단에서 다른 경우의 수를 찾아보고, 의심해보니

이진탐색에서 재귀함수를 사용할 때 n이 커지면 메모리에 많은 부담을 주지 않을까 하는 판단이 들었습니다.

이진탐색을 재귀함수 형식이 아니라 while 반복문 형태로 만들어주니까 정상적으로 문제가 풀렸습니다.

@rhdqor213 오 그렇군요. C99에서 성공하는 것은 또 왜일까요? 할당된 메모리 조건이 다른건지..

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

문제

문제

출처

ICPC

C언어) 메모리 초과가 왜 나오는지 모르겠습니다.

0207free 2년 전 0

rhdqor213 2년 전 1

0207free 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말