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

안녕하세요 정재님 ㅎㅎ

사실 메모리초과나 시간초과에 있어서 지역변수를 전역변수로 바꾸는 등의 행위는 그렇게 도움이 되지 않습니다. 불필요한 부분들을 제거하는게 중요합니다.

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

1.계속되는 초기화와 중복되는 탐색

	while (true) {
		fill(&visited_s[0][0], &visited_s[0][0] + 1500 * 1500, 0);

		ice();

지금 보시면 방문배열을 초기화하고 계속해서 중복되는 탐색이 일어납니다.

a -> b

a -> b -> c

a -> b -> c -> d

...

즉, 이부분을 제거하셔야 메모리초과나 시간초과가 나지 않게 됩니다.

2. 계속해서 중복되서 추가되는 정점들

			if (ny < 0 || nx < 0 || ny >= R || nx >= C) continue;
			//if (visited[ny][nx])continue;
			if (a[ny][nx] == 'X') {

앞의 코드는 다음과 같이 되어있을 때

.XX.

XX 두개의 정점 모두 v2에 넣게 됩니다.

이 문제는 시간초과나 메모리초과가 굉장히 타이트한 문제입니다.

해당 부분들을 없애고 다시 해보시겠어요?

감사합니다.

안녕하세요, 인프런 AI 인턴입니다. 이정재님.

백조 문제에서 메모리 초과가 발생하는 경우, 이는 일반적으로 프로그램의 자료구조나 알고리즘 설계에서 불필요하게 커다란 메모리를 사용하는 경우 발생할 수 있습니다. 주로 고려해야 할 사항들은 다음과 같습니다.

1. 자료구조 최적화: 큰 크기의 배열이나 리스트가 반복적으로 생성되는 경우, 이를 주의 깊게 살펴봐야 합니다. 불필요한 데이터 또는 중복된 데이터가 저장되고 있는지 확인해 보세요.

2. 큐 또는 스택의 사용: BFS나 DFS 알고리즘에서 큐나 스택이 너무 크게 확장되지는 않는지 점검해 보세요. 특히, 중복되는 좌표를 큐에 몇 번씩 푸시하고 있는 경우가 없는지 확인할 필요가 있습니다.

3. 중복 방문 방지: 이미 방문한 좌표를 다시 방문하지 않도록 visited 배열이나 유사한 구조를 활용해 중복 방문을 방지하는 전략이 필요할 수 있습니다.

관련된 유사 질문을 가지고 있는 링크도 함께 확인하시기 바랍니다:

• 3-K 메모리 초과 질문에서는 두 번째 이미지에 언급된 것처럼 불필요한 중복 처리를 피하는 코드를 제안하고 있습니다.

• 3-K 메모리 초과 관련 질문에서는 강사님의 피드백으로 메모리 사용을 최적화하는 전략에 대한 힌트가 있었습니다.

링크된 답변에서도 언급된 것처럼 여러 수강생들이 공통적으로 겪는 문제들에 대해 숙고하시고, 코드를 조정한 후 시도해 보세요. 위의 조언을 토대로 프로그램을 최적화하면, 아마도 문제가 해결될 것으로 기대합니다.

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