글 읽기 - 런타임에러 free() : InvalidNextSize 도와주세요!!ㅠㅠㅠ

projung0722 2년 전 0

free()부분에서 에러가 나는 것같은데 해결을 못하겠습니다. 동적할당한 크기를 벗어나는가를 확인했는데 아닌거같고 넉넉히 더 크게 동적할당하니 메모리초과가 나옵니다. ㅠㅠ 도와주세요!!ㅠㅠ

#include <stdio.h>
#include <stdlib.h>
#define ll long long
#define min(a,b) ((a<b)?(a):(b))
#define INF 1000000000

typedef struct {
	int num, index;
}MIN;

MIN init(int* arr, MIN* seg, int node, int s, int e);
MIN query(MIN* seg, int node, int s, int e, int l, int r);
void divideandconquer(int* arr, int* seg, int start, int end, int n);
ll maxarea;

int main()
{
	int n;
	while (1) {
		maxarea = 0;
		scanf("%d", &n);
		if (n == 0)
			break;
		MIN* seg;
		seg = (MIN*)malloc(sizeof(MIN) * (n * 2));
		int* arr;
		arr = (int*)malloc(sizeof(int) * n);
		for (int i = 0; i < n; i++)
			scanf("%d", arr + i);
		init(arr, seg, 1, 0, n - 1);
		divideandconquer(arr, seg, 0, n - 1, n);
		printf("%lld\n", maxarea);
		free(seg);
		free(arr);
	}
	return 0;
}
MIN init(int * arr, MIN* seg, int node, int s, int e)
{
	if (s == e) {
		seg[node].index = s;
		seg[node].num = arr[s];
		return seg[node];
	}
	int mid = (s + e) / 2;
	MIN tmp1, tmp2;
	tmp1 = init(arr, seg, 2 * node, s, mid);
	tmp2 = init(arr, seg, 2 * node + 1, mid + 1, e);
	if (tmp1.num < tmp2.num)
		return seg[node] = tmp1;
	else
		return seg[node] = tmp2;
}
MIN query(MIN* seg, int node, int s, int e, int l, int r)
{
	if (e < l || r < s) {
		MIN tmp;
		tmp.num = INF;
		return tmp;
	}
	if (l <= s && e <= r) return seg[node];
	int mid = (s + e) / 2;
	MIN tmp1, tmp2;
	tmp1 = query(seg, 2 * node, s, mid, l, r);
	tmp2 = query(seg, 2 * node + 1, mid + 1, e, l, r);
	if (tmp1.num < tmp2.num)
		return tmp1;
	else
		return tmp2;
}
void divideandconquer(int* arr, int* seg, int start, int end, int n)
{
	MIN min;
	min = query(seg, 1, 0, n - 1, start, end);
	if (maxarea < (ll)min.num * (end - start + 1)) 
		maxarea = (ll)min.num * (end - start + 1);
	if (start == end)
		return;
	if (min.index == start)
		divideandconquer(arr, seg, start + 1, end, n);
	else if (min.index == end)
		divideandconquer(arr, seg, start, end - 1, n);
	else {
		divideandconquer(arr, seg, start, min.index - 1, n);
		divideandconquer(arr, seg, min.index + 1, end, n);
	}
}

zenith82114 2년 전 1

세그트리 길이를 2n으로 주면 모자라는 경우가 있습니다.

일례로 n=6일 때 1번 노드가 구간 [0:5]를 담당할 경우 구간 [4:4]에 해당하는 노드는 13번입니다.

projung0722 2년 전 0

말씀해주신거 듣고 찾아보고 고쳤는데, 메모리초과가 납니다. 이게 구조체를 사용해서 그럴까요?

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define ll long long
#define min(a,b) ((a<b)?(a):(b))
#define INF 1000000000

typedef struct {
	int num, index;
}MIN;

MIN init(int* arr, MIN* seg, int node, int s, int e);
MIN query(MIN* seg, int node, int s, int e, int l, int r);
void divideandconquer(int* arr, int* seg, int start, int end, int n);
ll maxarea;

int main()
{
	int n;
	while (1) {
		maxarea = 0;
		scanf("%d", &n);
		if (n == 0)
			break;
		int* arr;
		arr = (int*)malloc(sizeof(int) * n);
		int height = (int)ceil(log2(n));
		int node_cnt = 1 << (height + 1);
		MIN* seg;
		seg = (MIN*)malloc(sizeof(MIN) * (node_cnt));
		for (int i = 0; i < n; i++)
			scanf("%d", arr + i);
		init(arr, seg, 1, 0, n - 1);
		divideandconquer(arr, seg, 0, n - 1, n);
		printf("%lld\n", maxarea);
		free(seg);
		free(arr);
	}
	return 0;
}
MIN init(int* arr, MIN* seg, int node, int s, int e)
{
	if (s == e) {
		seg[node].index = s;
		seg[node].num = arr[s];
		return seg[node];
	}
	int mid = (s + e) / 2;
	MIN tmp1, tmp2;
	tmp1 = init(arr, seg, 2 * node, s, mid);
	tmp2 = init(arr, seg, 2 * node + 1, mid + 1, e);
	if (tmp1.num < tmp2.num)
		return seg[node] = tmp1;
	else
		return seg[node] = tmp2;
}
MIN query(MIN* seg, int node, int s, int e, int l, int r)
{
	if (e < l || r < s) {
		MIN tmp;
		tmp.num = INF;
		return tmp;
	}
	if (l <= s && e <= r) return seg[node];
	int mid = (s + e) / 2;
	MIN tmp1, tmp2;
	tmp1 = query(seg, 2 * node, s, mid, l, r);
	tmp2 = query(seg, 2 * node + 1, mid + 1, e, l, r);
	if (tmp1.num < tmp2.num)
		return tmp1;
	else
		return tmp2;
}
void divideandconquer(int* arr, int* seg, int start, int end, int n)
{
	MIN min;
	min = query(seg, 1, 0, n - 1, start, end);
	if (maxarea < (ll)min.num * (end - start + 1))
		maxarea = (ll)min.num * (end - start + 1);
	if (start == end)
		return;
	if (min.index == start)
		divideandconquer(arr, seg, start + 1, end, n);
	else if (min.index == end)
		divideandconquer(arr, seg, start, end - 1, n);
	else {
		divideandconquer(arr, seg, start, min.index - 1, n);
		divideandconquer(arr, seg, min.index + 1, end, n);
	}
}

zenith82114 2년 전 1

이 문제에서는 최대 넓이만 구하면 되고, 그게 어디인지는 몰라도 됩니다.

index를 저장할 필요가 있을까요?

projung0722 2년 전 0

분할해줄때 필요하다고 생각하고 코드를 작성해주었습니다. 인덱스를 모르면 어디서 어떻게 분할할 지 모르지 않나요?

projung0722 2년 전 0

최솟값을 가져오도록 하지않고 최솟값의 인덱스만 가져오도록 했는데도 메모리초과가 납니다ㅠ

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define ll long long
#define min(a,b) ((a<b)?(a):(b))
#define INF 1000000000

int init(int* arr, int* seg, int node, int s, int e);
int query(int* arr, int* seg, int node, int s, int e, int l, int r, int n);
void divideandconquer(int* arr, int* seg, int start, int end, int n);
ll maxarea;

int main()
{
	int n;
	while (1) {
		maxarea = 0;
		scanf("%d", &n);
		if (n == 0)
			break;
		int* arr;
		arr = (int*)malloc(sizeof(int) * (n+1));
		arr[n] = INF;
		int height = (int)ceil(log2(n));
		int node_cnt = 1 << (height + 1);
		int* seg;
		seg = (int*)malloc(sizeof(int) * (node_cnt));
		for (int i = 0; i < n; i++)
			scanf("%d", arr + i);
		init(arr, seg, 1, 0, n - 1);
		divideandconquer(arr, seg, 0, n - 1, n);
		printf("%lld\n", maxarea);
		free(seg);
		free(arr);
	}
	return 0;
}
int init(int* arr, int* seg, int node, int s, int e)
{
	if (s == e) return seg[node] = s;
	int mid = (s + e) / 2;
	int tmp1, tmp2;
	tmp1 = init(arr, seg, 2 * node, s, mid);
	tmp2 = init(arr, seg, 2 * node + 1, mid + 1, e);
	if (arr[tmp1] < arr[tmp2])
		return seg[node] = tmp1;
	else
		return seg[node] = tmp2;
}
int query(int * arr,int* seg, int node, int s, int e, int l, int r, int n)
{
	if (e < l || r < s) return n;
	if (l <= s && e <= r) return seg[node];
	int mid = (s + e) / 2;
	int tmp1, tmp2;
	tmp1 = query(arr, seg, 2 * node, s, mid, l, r, n);
	tmp2 = query(arr, seg, 2 * node + 1, mid + 1, e, l, r, n);
	if (arr[tmp1] < arr[tmp2])
		return tmp1;
	else
		return tmp2;
}
void divideandconquer(int* arr, int* seg, int start, int end, int n)
{
	int min;
	min = query(arr, seg, 1, 0, n - 1, start, end, n);
	if (maxarea < (ll)arr[min] * (end - start + 1))
		maxarea = (ll)arr[min] * (end - start + 1);
	if (start == end)
		return;
	if (min == start)
		divideandconquer(arr, seg, start + 1, end, n);
	else if (min == end)
		divideandconquer(arr, seg, start, end - 1, n);
	else {
		divideandconquer(arr, seg, start, min - 1, n);
		divideandconquer(arr, seg, min + 1, end, n);
	}
}

zenith82114 2년 전 0

테스트 케이스를 랜덤으로 만들어서

제가 짰던 코드와 같이 돌려 보니 답이 계속 똑같이 나오네요.

게다가 제 코드는 segment tree 말고 sparse table을 썼기 때문에

메모리 사용량은 오히려 저보다 적어야 합니다.

이러면 제 생각에 남은 가능성은 동적 할당 overhead밖에 없어 보입니다.

동적 할당 대신 필요한 최대 크기만큼 한번만 선언하고 테스트 케이스마다 초기화하는 방식으로 고쳐 보세요.

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

문제

문제

출처

ICPC

런타임에러 free() : InvalidNextSize 도와주세요!!ㅠㅠㅠ

projung0722 2년 전 0

zenith82114 2년 전 1

projung0722 2년 전 0

zenith82114 2년 전 1

projung0722 2년 전 0

projung0722 2년 전 0

zenith82114 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말