글 읽기 - 메모리 초과가 뜨는 이유를 모르겠습니다.

tddhot2 7년 전 0

가장 큰 데이터 자료구조라고 하면

벡터형인데 벡터도 100000*2 크기거든요.

그럼 100000*2*4byte해서 800,000bytes인데 이는 MB로 환산하면 0.2MB밖에 안되더군요..

근데 왜 자꾸 메모리 초과가 나는지 모르겠습니다 ㅠㅠ

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

​

#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;

/* Type 유형
1: 왼쪽에 호랑이를 배치할 경우
2: 오른쪽에 호랑이를 배치할 경우
3: 호랑이를 양쪽에 배치하지 않을 경우
*/

int DPrograming2(int type, vector<vector<int>> dp, int n, int x, int y)
{
/*cout << "Type is " << type << endl;
cout << "X좌표 : " << x << "      Y좌표 :" << y << endl;*/

if (x == n - 1)
{
/*cout << "최종 끝 위치 1 반환" << endl;
cout << "\n";*/
return 1;
}

if (dp[x][y] != -1)
{ 
cout << "{ " << x << " , " << y << " }";
cout << "저장된 DP값이 존재" << endl;
cout << "\n";
return dp[x][y];
}
else
{
int ret=0;
if (type == 1)
{
ret = DPrograming2(2, dp, n, x + 1, 1) + DPrograming2(3, dp, n, x + 1, 0);
dp[x][0] += ret;
/*cout << "ret 값 : " << ret << endl;
cout << "\n";*/
return ret;
}
else if(type == 2)
{
ret = DPrograming2(1, dp, n, x + 1, 0) + DPrograming2(3, dp, n, x + 1, 0);
dp[x][1] += ret;
/*cout << "ret 값 : " << ret << endl;
cout << "\n";*/
return ret;
}
else
{
ret += DPrograming2(1, dp, n, x + 1, 0);
ret += DPrograming2(2, dp, n, x + 1, 1);
ret += DPrograming2(3, dp, n, x + 1, 0);
dp[x][0] += ret;
dp[x][1] += ret;
/*cout << "ret 값 : " << ret << endl;
cout << "\n";*/
return ret;
}
}
}
int main()
{
int N;
cin >> N;

vector<vector<int>> DP(N, vector<int>(2, -1));

int Result = DPrograming2(1, DP, N, 0, 0) + DPrograming2(2, DP, N, 0, 1) +
DPrograming2(3, DP, N, 0, 0);

cout << Result%9901;
    return 0;
}

jwg8679 7년 전 1

재귀호출은 스택 메모리에 쌓입니다.

메모리 초과가 나시는 이유는 아마 재귀함수를 너무 많이 사용하셔서 스택메모리가 터진 것이라고 생각이 되네요

예외처리를 하셔서 스택메모리에 쌓이는 재귀함수의 양을 줄여주시면 메모리 초과가 나지 않을것같습니다.

아니면 재귀 말고 iterative 하게 DP를 사용하시면 해결 될 거 같네요

백준에서 말하는 메모리 제한은 보통 힙 메모리를 말하는 것이지만 이 경우는 재귀호출을 많이 해서 스택 오버플로우가 난거같습니다

tddhot2 7년 전 0

답변 감사합니다 한 번 확인해보겠습니다!

jaydoubluel 7년 전 2

함수 parameter타입을

vector<vector<int> >& dp

로 고치세요.

tddhot2 7년 전 0

헐 아랫분 말씀이 맞았네요;;;

감사합니다...

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

문제

문제

출처

ICPC

메모리 초과가 뜨는 이유를 모르겠습니다.

tddhot2 7년 전 0

jwg8679 7년 전 1

tddhot2 7년 전 0

jaydoubluel 7년 전 2

tddhot2 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말