글 읽기 - c++ 메모리초과 합병정렬

suby00 3년 전 0

메모리 초과가 뜹니다 ㅜㅜ 너무 어렵네요 .. 메모리가 어디에서 많이 잡아먹는지 잘 모르겠습니다

메모리 보는방법을 검색해서 대충은 알게되었는데

arr의 최대 40mb *bd의 최대 40mb 로 알고있는데 메모리 초과가 나네요 ..

메모리초과를 보는방법을 알려주실수있을까요 죄송합니다 ㅜ

#include <iostream>
#include <vector>
using namespace std;

void merge(int* arr,int n,int m, int r ){
    int i = n;
    int j = m +1;
    int k = n;
    int *b = new int[r+1]; // 임시 배열
    while(i <= m && j <= r){
        if(arr[i] <= arr[j]) 
            b[k++] = arr[i++];
        else 
            b[k++] = arr[j++];
    }
    //나머지
    if(i > m){
        for(int l = j; l <=r; l++){
            b[k++] = arr[l];
        }
    }
    else {
        for(int l=i;l<=m;l++){
            b[k++] = arr[l];
        }
    }
    //원래 배열로 넘겨주기
    for(int t = n;t <=r; t++){
        arr[t] = b[t];
    }

}

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

int main(){
    int n;
    cin >> n;

    int* arr = new int[n];
    for(int i=0; i<n; i++){
        cin >> arr[i];
    }

    merge_sort(arr,0,n-1);

    for(int i=0; i<n; i++){
        cout << arr[i] <<endl;
    }
    return 0;
}

djm03178 3년 전 0

https://www.acmicpc.net/board/... 의 3번과 같습니다.

이 코드에서는 할당받은 배열을 delete를 하지 않고 있기 때문에 시간이 초과되기 이전에 메모리가 먼저 O(N^2)이 되어 메모리 초과가 됩니다.

suby00 3년 전 0

너무 감사합니다 메모리 보는눈을 더 길러가네요 감사합니다

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

문제

문제

출처

ICPC

c++ 메모리초과 합병정렬

suby00 3년 전 0

djm03178 3년 전 0

suby00 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말