인프런 영문 브랜드 로고
인프런 영문 브랜드 로고

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

ililil님의 프로필 이미지

작성한 질문수

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

3-H

메모리초과 질문

작성

·

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점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.


 

 

ililil님의 프로필 이미지
ililil
질문자

설명하신 것 중 질문이 있어 재질문드립니다! visit가 0인 경우만 큐에 담아 한 노드가 한번씩만 방문하게 설계했다고 생각했는데

"지금 보시면 모든 경우의 수에 해당하는 경로를 담고 있는데요." 이 말씀은 한 노드가 여러번 방문된다는 뜻인가요?

큰돌님의 프로필 이미지
큰돌
지식공유자

음.. 아닙니다 한노드는 한번 방문되지만 여러 경우의 수가 있고 해당 경로가 매번 큐에 담겨진다는 의미입니다 그리고 그 경로의 수가 너무나 많습니다

큰돌님의 프로필 이미지
큰돌
지식공유자

예를 들어 *2, +1만 있다고 했을 때 한번만 방문하더라도 2^n에 해당하는 경우의 생기고 해당 경우의 수를 각각 다 더하게 된다면 n이 30일 때 2^30 - 1의 해당하는 수만큼의 벡터가 생기게 되는 셈입니다.

 

감사합니다.

0

인프런 AI 인턴님의 프로필 이미지

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

ililil님이 작성하신 코드에서는 메모리 초과가 발생하는 이유가 vector<int> tmp = path; 부분에서 경로를 계속 복사하여 저장하는 과정에서 발생할 수 있습니다. 작은 크기일 때는 문제가 되지 않지만, 이 과정이 반복되면서 vector의 복사 비용이 점점 누적되어 많은 메모리를 사용하게 됩니다.

여기서 몇 가지 개선 사항을 제안드립니다:

  1. 경로 복사 줄이기: Pair 구조체에서 path에 대한 복사를 줄이기 위해, 경로 대신 변환 횟수만을 기록하거나 경로 재생성을 위해 출발지부터의 이동 히스토리를 이용할 수 있습니다.

  2. 의사 경로 사용 고려: BFS 자체는 모든 경로를 직접적으로 저장하지 않고 탐색하며, 필요시 역으로 경로를 추적하는 식으로 구현할 수 있습니다.

  3. bool 사용: unordered_map<int, vector<int>> map;은 실제로 최종 경로를 확인하는데 필요하지 않으므로, 필요 없는 경우에는 사용하지 않아도 좋습니다.

관련된 유사한 문제 해결 방법이 논의된 게시물을 추천드립니다:

vector<int>의 반복적인 복사는 메모리 사용을 줄이기 위해서 줄이거나 대체 방법을 고려할 때 발생할 수 있는 문제를 해결할 수 있습니다. 필요하다면, vector 대신에 더 작은 자료구조나 필요 시에만 메모리를 사용하는 방법을 고민해 보시면 좋겠습니다.

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

ililil님의 프로필 이미지

작성한 질문수

질문하기