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

안녕하세요 성욱님 ㅎㅎ

	while (q.size()) {
		now = q.front(); q.pop();
		v[now].push_back(now);

지금 보시면 정답이 될 수 있는 모든 경우의 수를 담고 있습니다.

1 2 3

1 2 3 5 ..

그리고 이러한 가짓수가 매번 경우의 수 3개마다 발생되니까 n^3 만큼 커지게 되서 많은 양의 요소를 담은 벡터가 되게 되고 -> 메모리초과가 발생하는 것이죠.

이부분을 고쳐보시겠어요?

감사합니다.

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

조성욱님, 백준 13913번 문제에서 메모리 초과 문제를 겪고 계시는군요. 메모리 초과는 보통 데이터 구조의 크기가 너무 크거나, 자료를 비효율적으로 관리할 때 발생합니다. 주로 이중 벡터 등 크기가 큰 동적 자료구조를 사용할 때 나타날 수 있습니다.

해결 방안:

1. 경로 저장 최적화:
   이중벡터를 사용하는 경우, 경로까지의 모든 가능한 경로를 저장하는 방식이라면 메모리를 많이 사용하게 됩니다. 경로를 저장할 때, 필요한 최소한의 정보만 유지하고 불필요한 중복 저장을 피해야 합니다. 예를 들어, 경로를 역추적(backtracking)하면서 필요한 때에만 삽입/삭제를 수행하는 방식으로 전환해 보세요.

2. 참조자를 이용한 메모리 최적화:
   함수에 인자를 전달할 때 값 복사 방식이 아니라 참조자를 사용하기도 권장드립니다. 특히 이중 벡터처럼 큰 데이터 구조의 경우는 복사를 매번 피할 수 있도록 합니다.

3. 큐를 활용한 BFS 구현:
   경로 탐색 알고리즘에서는 BFS(너비 우선 탐색)를 사용할 때 큐 자료구조를 이용하면 메모리 사용을 효율적으로 줄일 수 있습니다. 큐에 필요한 현재의 상태만을 저장하고 이를 통해 경로를 추적하세요.

아래는 관련하여 참고할 만한 링크입니다:
- 3-H 메모리 초과 질문에서는 비슷한 메모리 초과 오류를 처리하기 위한 조언이 제공되고 있습니다.

이 방법들을 고려하여 메모리 문제를 해결해 보시기 바랍니다.

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