작성
·
39
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
안녕하세요! 제가 처음에 풀 때 map을 사용해서 위치, 누적경로를 담아 풀이했는데 메모리가 초과되었다고 합니다. 지레짐작으로는 경로를 계속 복사하는 과정에서
vector<int> tmp = path; // 기존 경로 복사
메모리가 누적되는거 같은데, 처음부터 이 방법이 메모리 초과이겠다..!라고 판단하는 방법이 있을까요?
아래는 제 코드입니다
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>
using namespace std;
const int MAX = 100000;
const int MIN = 0;
int visited[MAX + 4];
struct Pair {
int loc; // 현재 위치
vector<int> path; // 누적 경로
Pair(int l, vector<int> p) : loc(l), path(p) {}
};
int main() {
int n, m;
cin >> n >> m;
unordered_map<int, vector<int>> map;
queue<Pair> q;
vector<int> fPath;
fPath.push_back(n);
q.push(Pair(n, fPath));
visited[n] = 1;
map[n] = fPath;
while (!q.empty()) {
Pair p = q.front();
q.pop();
int here = p.loc;
vector<int> path = p.path;
if (here == m) {
break;
}
for (int there : {here + 1, here - 1, here * 2}) {
if (there >= MIN && there <= MAX) {
if (visited[there] == 0) {
visited[there] = visited[here] + 1;
vector<int> tmp = path; // 기존 경로 복사
tmp.push_back(there);
q.push(Pair(there, tmp));
map[there] = tmp;
}
}
}
}
if (n == m) {
cout << 0 << endl;
} else {
cout << visited[m] - 1 << endl;
}
for (int p : map[m]) {
cout << p << " ";
}
return 0;
}
답변 2
0
안녕하세요 ㅎㅎ
q.push(Pair(there, tmp));
map[there] = tmp;
이부분이 메모리 초과인것 같습니다. 지금 보시면 모든 경우의 수에 해당하는 경로를 담고 있는데요.
queue에
a -> b -> c
a -> b - > d
...
등이 들어가고 map에는 해당 부분이 들어가기 때문에 그 경로의 수에 따라 메모리초과가 발생하는 것 같습니다.
처음부터 이 방법이 메모리 초과이겠다..!라고 판단하는 방법이 있을까요?
-> 접근법은 좋다고 생각합니다. 다만 이렇게 생각하시면 됩니다.
for (int there : {here + 1, here - 1, here * 2}) {
이문제의 경우 3^n으로 확장해나가죠? 근데 이러한 경우의 수를 모두 담는 다는 것은
n이 10만 되어도 3^10(6만)만큼 담게 된다는 것을 의미합니다. 총 경우의 수를 산정해서 -> 너무 많은 것을 담는게 아닌가? -> 그래도 한번? -> 초과 나네 -> 다른 효율적인 방법? -> 아 prev를 쓰면 되겠지? -> 하면서 좀 더 효율적으로 진행해나가시면 됩니다.
다시 말씀드리면,
이번 코드의 접근법 자체는 좋았습니다. 다만 여기서 경우의수를 기반으로 많은 값들을 담는게 아닌가? 고민 -> 그래도 다른 방법이 생각이 안나면 -> 이 방법으로 시도 -> 초과 -> 다른 방법 이렇게 시도해주세요 ㅎㅎ
이렇게 빠르게 다른 방법을 시도하는 것을 기르는 게 중요합니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
안녕하세요, 인프런 AI 인턴입니다.
ililil님이 작성하신 코드에서는 메모리 초과가 발생하는 이유가 vector<int> tmp = path;
부분에서 경로를 계속 복사하여 저장하는 과정에서 발생할 수 있습니다. 작은 크기일 때는 문제가 되지 않지만, 이 과정이 반복되면서 vector
의 복사 비용이 점점 누적되어 많은 메모리를 사용하게 됩니다.
여기서 몇 가지 개선 사항을 제안드립니다:
경로 복사 줄이기: Pair
구조체에서 path
에 대한 복사를 줄이기 위해, 경로 대신 변환 횟수만을 기록하거나 경로 재생성을 위해 출발지부터의 이동 히스토리를 이용할 수 있습니다.
의사 경로 사용 고려: BFS 자체는 모든 경로를 직접적으로 저장하지 않고 탐색하며, 필요시 역으로 경로를 추적하는 식으로 구현할 수 있습니다.
bool 사용: unordered_map<int, vector<int>> map;
은 실제로 최종 경로를 확인하는데 필요하지 않으므로, 필요 없는 경우에는 사용하지 않아도 좋습니다.
관련된 유사한 문제 해결 방법이 논의된 게시물을 추천드립니다:
vector<int>
의 반복적인 복사는 메모리 사용을 줄이기 위해서 줄이거나 대체 방법을 고려할 때 발생할 수 있는 문제를 해결할 수 있습니다. 필요하다면, vector
대신에 더 작은 자료구조나 필요 시에만 메모리를 사용하는 방법을 고민해 보시면 좋겠습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
설명하신 것 중 질문이 있어 재질문드립니다! visit가 0인 경우만 큐에 담아 한 노드가 한번씩만 방문하게 설계했다고 생각했는데
"지금 보시면 모든 경우의 수에 해당하는 경로를 담고 있는데요." 이 말씀은 한 노드가 여러번 방문된다는 뜻인가요?