글 읽기 - c언어 메모리초과가 왜 뜨는지 좀 알려주세요

skiwer98 2년 전 0

일단 메모리초과가 뜨는 코드는 아래에 있습니다.

저기서 temp를 그냥 전역변수로

temp[100000][2] = { 0, }; 로 설정하니까 맞다고 뜨긴한데 왜그런지 납득이 안갑니다.

merge함수안에서 free로 해제도 해주었고 설령 해제를 안한다 하더라도 100000 * 4 (int 포인터 크기) * 2 (int값 2개) * 2 (temp와 ar) byte니까

메모리 초과가 안떠야 하는 것 아닌가요?

전역변수로 설정하면 왜 메모리초과가 안 뜨고

아래 malloc으로 했을 때는 왜 메모리초과가 뜨는지 좀

알려주시면 감사하겠습니다.

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

void merge(int **ar, int left, int mid, int right)
{
    int p = left, q = mid + 1, k = left;
    int **temp = malloc(sizeof(int *) * (right + 1));
    for (int i = 0; i <= right; i++)
    {
        temp[i] = malloc(sizeof(int) * 2);
    }

    while (p <= mid && q <= right)
    {
        if (ar[p][0] < ar[q][0])
        {
            temp[k][0] = ar[p][0];
            temp[k++][1] = ar[p++][1];
        }

        else if (ar[p][0] == ar[q][0])
        {
            if (ar[p][1] <= ar[q][1])
            {
                temp[k][0] = ar[p][0];
                temp[k++][1] = ar[p++][1];
            }

            else
            {
                temp[k][0] = ar[q][0];
                temp[k++][1] = ar[q++][1];
            }
        }

        else if (ar[p][0] > ar[q][0])
        {
            temp[k][0] = ar[q][0];
            temp[k++][1] = ar[q++][1];
        }
    }

    while (p <= mid)
    {
        temp[k][0] = ar[p][0];
        temp[k++][1] = ar[p++][1];
    }

    while (q <= right)
    {
        temp[k][0] = ar[q][0];
        temp[k++][1] = ar[q++][1];
    }

    for (int a = left; a <= right; a++)
    {
        ar[a][0] = temp[a][0];
        ar[a][1] = temp[a][1];
        free(temp[a]);
    }

    free(temp);
}

void mergesort(int **ar, int left, int right)
{
    int mid = (left + right) / 2;
    if (left < right)
    {
        mergesort(ar, left, mid);
        mergesort(ar, mid + 1, right);
        merge(ar, left, mid, right);
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    int **ar = malloc(sizeof(int *) * n);

    for (int i = 0; i < n; i++)
    {
        ar[i] = malloc(sizeof(int) * 2);
        scanf("%d %d", &ar[i][0], &ar[i][1]);
    }

    mergesort(ar, 0, n - 1);

    for (int i = 0; i < n; i++)
    {
        printf("%d %d\n", ar[i][0], ar[i][1]);
        free(ar[i]);
    }

    free(ar);

    return 0;
}

djm03178 2년 전 1

9번째 줄에서는 0번부터 right번까지 할당하는데, 56번째 줄에서는 left부터만 해제하고 있습니다.

merge시마다 0~right를 순회하는 것은 전체 과정에서 O(N^2)가 됩니다. 반면에 left~right의 순회는 O(NlogN)입니다. 할당받는 양과 해제하는 양이 복잡도부터 다르기 때문에 최종적으로 할당받은 상태로 남는 메모리 역시 O(N^2)으로 제한을 초과하게 됩니다.

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

문제

문제

출처

ICPC

c언어 메모리초과가 왜 뜨는지 좀 알려주세요

skiwer98 2년 전 0

djm03178 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말