인프런 커뮤니티 질문&답변

안녕하세요 ㅎㅎ

무엇때문에 메모리 초과가 난걸까요?

>> 비효율적인 부분 때문에 배열을 많이 생성 or 함수를 많이 생성 하는 로직 때문에 그럴 가능성이 큽니다.

코드리뷰는 다음과 같습니다.

다음과 같은 비효율적인 부분을 개선해주시면 됩니다.

void spread(vector<pair<int,int>> &fire, vector<vector<int>>& mp)
{
	int x,y;
	vector<pair<int,int>> nfire;

spread에서 nfire 이 계속 생성이 됩니다.

void dfs(int sum, pair<int,int> pos, vector<pair<int,int>> mfire, vector<vector<int>> mp)

call by reference로 넘겨주세요(교안참고)

		if(nx<0||ny<0||nx>=M||ny>=N)
		{
			answer=answer==0?sum+1:min(sum+1,answer);
			continue;
		}

이 로직 자체가 bfs가 아닌 dfs로 구현했기 때문에 발생합니다. 탈출 -> 종료하는게 훨씬 더 효율적인 코드겠죠? bfs로 하게 되면 최단거리임이 자명하기 때문에 이부분을 비효율적으로 할 필요성이 없어집니다.

		spread(mfire,mp);
		visit[ny][nx]=1;
		dfs(sum+1, {nx,ny},mfire, mp);
		visit[ny][nx]=0;

모든 경우의 수를 잡아내기 위해 이렇게 하셨는데 이거는 정말 많은 시간복잡도를 발생시킵니다.

4^n*m이라고 볼 수 있어요.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴입니다.

geonwlee22님, 메모리 초과 문제로 고민하시는 군요. 메모리 초과는 대부분 자료구조의 크기가 너무 크거나, 필요 이상으로 메모리를 사용하는 로직, 특히 깊은 재귀로 인한 스택 오버플로우, 혹은 큰 크기의 변수 및 자료구조를 불필요하게 복사하는 경우에 발생할 수 있습니다.

벡터를 계속 복사한다고 언급하셨는데, 그것이 주요 원인일 가능성이 높습니다. 벡터와 같은 동적 자료구조를 함수의 인자로 넘길 때는 주소를 넘기거나(포인터 사용), 참조자(&)를 사용하여 복사를 최소화하는 것이 좋습니다. 이는 메모리 사용을 크게 줄이고 성능을 개선할 수 있는 방법입니다.

실제로 이와 유사한 문제를 다룬 기존 답변이 있어, 해당 케이스와 관련하여 참고하실 수 있습니다.

• 2-D (백준2573 영역구하기) 백터사용시 메모리 초과의 경우, 함수 인자로 2차원 벡터를 복사하지 않고 참조자 &를 사용하여 메모리 초과 문제를 해결하였습니다.
  

이 내용을 기반으로, geonwlee22님의 경우도 벡터를 함수 인자로 넘길 때 복사 대신 참조를 사용하는 방식으로 변경해 보시는 것을 추천드립니다.

이와 관련하여 코드 수정 예시는 다음과 같습니다.

기존 코드:

void dfs(vector<vector<int>> map);

수정 후:

void dfs(const vector<vector<int>>& map); //읽기 전용 참조로 전달

효과적인 메모리 관리를 위해, 불필요한 복사를 줄이고 필요할 때만 최소한의 데이터만 넘기는 방식을 채택하는 것이 중요합니다. 이를 통해 메모리 초과 없이 문제를 해결하실 수 있기를 바랍니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.