글 읽기 - C++ 메모리 초과, 정성껏 제 의견을 작성해뒀는데 조언 부탁드리겠습니다!

goonbamm 3년 전 1

제가 만든 예시로는 잘 돌아가는데, N = 100000에 가까워질 만큼 거대한 예시를 만들 실력이 없습니다.

제가 시도한 방법은 아래와 같습니다. 참고로 문제 메모리 제한 512MB 입니다.

1. 값이 변하지 않는 함수 인자들은 모두 call by reference 로 변경했습니다.

2. 제가 선언한 vector 들의 크기를 계산해봤습니다. 기본 자료형은 굳이 구하지 않았습니다.

N 의 최대 크기인 100000 로 가정하고 구해봤습니다.

- 181번 라인 → rmq : 1MB (232144 * 4 Bytes), 21번 라인에서 크기가 결정됨.

- 75번 라인 → 총 5개의 1차원 벡터 (parent, depth, heavy, head, pos)

크기는 106번 라인에서 모두 크기가 N이 되어, 약 2MB (5 * 100000 * 4 Bytes) 다.

- 158번 라인 → 클래스 Edge 벡터 (e)

structure member alignment 에 의해 1개 크기는 16 Bytes, 총 N - 1 개이므로 약 1.6MB 다.

클래스 함수의 크기는 모르겠으나, 생성자와 GET 함수만 선언했으므로 미미할 것으로 예상한다.

사실 제 짧은 추리로는 이 녀석이 문제를 일으키는 것인지 궁금합니다.

- 157번 라인 -> vector<vector<int>> adj(N) ;

N^2 가 되는 순간, 메모리 제한을 가볍게 뛰어넘을 것이나 160 ~ 164번 라인에 적어뒀듯,

push_back() 함수를 사용하여 값을 저장하고 있으므로, 실제 저장되어야 하는 크기는 2 * (N - 1) * 4 Bytes 다.

그러므로 0.8MB 다.

모두 다 해봤자, 5.4 MB라 아무리 제가 계산을 근삿값으로 했다고 해도 초과될 리 없다고 생각합니다.

제 나름 구글링을 해봐도 도저히 밝힐 수 없는데다가, 제가 군인이라 온라인 컴파일러로 돌리고 있어서

해답을 얻기 힘든데, 혹시라도 도와주신다면 정말 감사드리겠습니다!!

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

// segment tree

int N, MAXN = 1000000;
vector<int> rangeMax(MAXN); // segment tree by array

// make segment tree

int sg_init(const vector<int> &arr, int left, int right, int node){
  if (left == right) return rangeMax[node] = arr[left];
  
  int mid = (left + right) / 2;
  int leftMax = sg_init(arr, left, mid, node * 2);
  int rightMax = sg_init(arr, mid + 1, right, node * 2 + 1);
  return rangeMax[node] = max(leftMax, rightMax);
}

int sg_init(const vector<int> &arr){
    return sg_init(arr, 0, N - 1, 1);
}

int sg_query(int left, int right, int node, int nodeLeft, int nodeRight){
  if (right < nodeLeft || nodeRight < left) return 0;
  if (left <= nodeLeft && nodeRight <= right) return rangeMax[node];

  int mid = (nodeLeft + nodeRight) / 2;
  return max(sg_query(left, right, 2 * node, nodeLeft, mid),
             sg_query(left, right, 2 * node + 1, mid + 1, nodeRight));
}

int sg_query(int left, int right){
  return sg_query(left, right, 1, 0, N - 1);
}

int sg_update(int index, int newValue, int node, int nodeLeft, int nodeRight) {
  if (index < nodeLeft || nodeRight < index) return rangeMax[node];
  if (nodeLeft == nodeRight) return rangeMax[node] = newValue;

  int mid = (nodeLeft + nodeRight) / 2;
  return rangeMax[node] = max(sg_update(index, newValue, 2 * node, nodeLeft, mid),
                    sg_update(index, newValue, 2 * node + 1, mid + 1, nodeRight));
}

int update(int index, int newValue) {
  return sg_update(index, newValue, 1, 0, N - 1);
}

// heavy - light decompostion

vector<int> parent, depth, heavy, head, pos;
int cur_pos;

int dfs(int v, const vector<vector<int>> &adj){
  int size = 1;
  int max_c_size = 0;

  for (int c : adj[v]) {
    if (c != parent[v]) {
      parent[c] = v, depth[c] = depth[v] + 1;
      int c_size = dfs(c, adj);
      size += c_size;
      
      if (c_size > max_c_size)
        max_c_size = c_size, heavy[v] = c;
    }
  }

  return size;
}

int decompose(int v, int h, const vector<vector<int>> &adj){

  head[v] = h, pos[v] = cur_pos++;
  if (heavy[v] != -1) decompose(heavy[v], h, adj);

  for (int c: adj[v])
    if (c != parent[v] && c != heavy[v])
      decompose(c, c, adj); // head is changed -> decomposition
}

void init(const vector<vector<int>> &adj){
  parent = vector<int>(N);
  depth = vector<int>(N);
  heavy = vector<int>(N, -1);
  head = vector<int>(N);
  pos = vector<int>(N);
  cur_pos = 0;

  dfs(0, adj);
  decompose(0, 0, adj);
}

int query(int a, int b){
  int res = 0;
  
  for (; head[a] != head[b]; b = parent[head[b]]) {
    if (depth[head[a]] > depth[head[b]]) swap(a, b);
      
    int cur_heavy_path_max = sg_query(pos[head[b]], pos[b]);
    res = max(res, cur_heavy_path_max);
  }

  if (depth[a] > depth[b]) swap(a, b);
  
  if(a != b){
      int last_heavy_path_max = sg_query(pos[a] + 1, pos[b]); // think about the meaning of arr value.
      res = max(res, last_heavy_path_max);
  }
    
  return res;
}

// edge

class Edge{
    
  private:
    int u, v, w;

  public:
    Edge(){ u = 0, v = 0, w = 0; }
    Edge(int a, int b, int c) { u = a, v = b, w = c; }
    int getU() { return u; }
    int getV(){ return v; }
    int getW(){ return w; }
};

int main(void){

  int M, u, v, w, a, b, c;
  scanf("%d", &N);

  vector<vector<int>> adj(N, vector<int>()); // [0, N - 1][0, N - 1] -> the N : 2N Bytes
  vector<Edge> e(N - 1); // [0, N - 2]

  for (int i = 0; i < N - 1; ++i) {
    scanf("%d %d %d", &u, &v, &w);
    adj[u - 1].push_back(v - 1), adj[v - 1].push_back(u - 1); // to analyze the graph
    e[i] = Edge(u - 1, v - 1, w); 
  }

  init(adj); // heavy - light decomposition

  // make segment tree
  vector<int> arr(N); // [0, N - 1]
  
  for(int i = 0; i < N - 1; ++i){ // i : index of edges
    u = e[i].getU(), v = e[i].getV(), w = e[i].getW();
    
    if(u == parent[v]) 
        arr[pos[v]] = w;
    
    else // v == parent[u]
        arr[pos[u]] = w;
  }
  
  sg_init(arr);
  
  scanf("%d", &M);

  for (int i = 0; i < M; i++){
    scanf("%d %d %d", &a, &b, &c);

    if (a == 1){ // update
        u = e[b - 1].getU(), v = e[b - 1].getV(), w = c;
        
        if(u == parent[v])
            update(pos[v], w); // the value of V needed to update

        else // V == parent of U    
            update(pos[u], w); // the value of U needed to update
    } 

    else // query
        printf("%d\n", query(b - 1, c - 1));
  }
  
  return 0;
}

goonbamm 3년 전 0

아무리 생각해도 메모리 초과는 변수에 의해 발생하지 않다고 생각했어요.

함수인자도 call by reference를 사용했기 때문에 문제가 없다고 생각했는데,

혹시나 함수의 재귀적 호출에 의한 것은 아닐까 하고 틀렸습니다 10번을 통해 알아냈습니다.

95번째줄에 위치한 decompose 함수에 들어가고 난 뒤에 "메모리 초과"가 나타난 것입니다.

어떻게 재귀적 호출이 일어나는지는 잘 모르겠으나. 일단 원인을 찾아냈습니다!!

저 코드는 cp-algorithm을 그대로 가지고 왔는데도 어떤 부분에서 재귀를 일으키나 봅니다.

goonbamm 3년 전 0

추가로 발견한 것인데, decompose의 반환형이 int로 돌렸을 때는 메모리 초과가 발생하는데

void 형으로 바꾸니 메모리 초과가 발생하지 않았습니다. 그 이유는 모르겠지만 신기하네요.

pill27211 1년 전 0

조금 늦은 감이 있지만, 반환형이 특정된(void형이 아닌) 함수에서 값을 반환하지 않는다는 건 엄연히

Undefined Behavior입니다.

간단한 코드에서는 문제 발생 확률이 적을 수야 있겠지만,

특히 재귀적 호출이 있는 상황에선 더욱 어떠한 결과를 낳을지 알 수 없게 되죠.

(메모리 초과는 물론 시간초과가 발생할 수도 있고 아주 우연히 AC 판정을 받을 수도 있습니다. -> 어떤 결과가 나와도 이상하지 않음)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

C++ 메모리 초과, 정성껏 제 의견을 작성해뒀는데 조언 부탁드리겠습니다!

goonbamm 3년 전 1

goonbamm 3년 전 0

goonbamm 3년 전 0

pill27211 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말