글 읽기 - 메모리 초과 질문입니다.

eldpswp99 4년 전 0

문제는 해결했지만, 해결하기 전에 발생했던 메모리 초과 문제때문에 질문드립니다.

올린 코드는 메모리 초과때문에 통과하지 못했습니다.

그리디 + DFS로 해서 위로부터 시작해서 최대한 경로가 위쪽을 따라가도록 DFS를 돌려서 맨 오른쪽에 도달한경우 ans의 값을 증가시키는 방식으로 알고리즘을 구상하였고,

지금와서 보니 불필요해 보이지만 각 지점 별 간선의 정보를 미리 저장해두기 위해 edge 3차원벡터를 만들었습니다.

지점마다 간선은 최대 3개가 나올수 있으므로 edge[n][m][3]의 형태로 크기를 맞춰주었고, 전처리 과정을 통해 edge를 만들어주었는데, 제출을 하면 계속 메모리초과가 나왔습니다

그래서 edge배열을 없애고, DFS에서 각 지점을 들어갈때마다 edge 전처리 과정에서 했던 것처럼 for문 3번 돌려서 간선들을 확인해 주었는데, AC를 받았습니다.

후에 AC받은 코드에 int edge[10001][501][3]의 형태로 추가를 했음에도 통과를 했습니다.

bool 3차원벡터 edge의 크기는 10000*500*3*1byte = 15mb라고 생각이 되는데

왜 3차원벡터 edge를 사용하면 메모리 초과가 나는지 알 수 있을까요?

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
#include <string>

using namespace std;

typedef pair<int,int> pii;

const int INF = 987654321;
const int MAX = 18;

vector<string> table;
vector<vector<vector<bool>>> edge;
vector<vector<bool>> visit;
queue<pii> q;
int ci[] = {-1,0,1};
int cj[] = {1,1,1};

int n,m;
int ans = 0;

bool isvalid(int i,int j)
{
	return (i >= 0 && j >= 0 && i < n && j < m);
}

bool DFS(int curi,int curj)
{	
	if(curj == m-1) 
	{
		ans++;
		return true;	
	}
	
	for(int x = 0;x<3;x++)
	{
		if(edge[curi][curj][x])
		{
			int ti = curi + ci[x];
			int tj = curj + cj[x];
			
			if(!visit[ti][tj]) 
			{
				visit[ti][tj] = true;
                //DFS 도달했으면 바로 종료
				if(DFS(ti,tj)) return true;	
			}
		}
	}
	
	return false;
}


int main(int argc, char** argv) {
	scanf("%d %d",&n,&m);
	
	edge = vector<vector<vector<bool>>>(n,vector<vector<bool>>(m,vector<bool>(3,false)));
	visit = vector<vector<bool>>(n,vector<bool>(m,false));
	
	for(int i = 0;i<n;i++)
	{
		string str;
		
		cin>>str;
		
		table.push_back(str);
	}
	
	for(int i = 0;i<n;i++)
	{
		for(int j = 0;j<m;j++)
		{
			if(table[i][j] != 'x')
			{
				for(int x = 0;x<3;x++)
				{
					int ti = i + ci[x];
					int tj = j + cj[x];
					
					if(isvalid(ti,tj) && table[ti][tj] != 'x')
					{
						edge[i][j][x] = true;
					}
				}
			}	
		}
	}
	
	
	for(int i = 0;i<n;i++)
	{
		visit[i][0] = true;
		DFS(i,0);
	}
	
	printf("%d",ans);
	return 0;
}

djm03178 4년 전 2

vector라는 것은 그냥 배열과는 달리 그 배열에 대한 추가 정보를 담고 있습니다. 배열의 크기, 할당된 메모리의 크기, 원소가 저장된 주소의 포인터 등이 있습니다.

실제로 gcc에서 크기가 3인 vector<bool>의 capacity는 64나 되고, 원소가 저장된 공간을 제외한 객체 자체의 크기도 40이나 되는 것을 볼 수 있습니다. http://ideone.com/S6KCh8

eldpswp99 4년 전 0

친절한 설명 감사합니다. 추석 즐겁게 보내세요!

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